Методи розв’язування олімпіад них завдань

Методи розв’язування олімпіад них завдань

Метод доведення від супротивного.

Суть цього методу можна передати слідуючими пунктами:

1. Спочатку робиться припущення протилежне тому, яке потрібно довести.
2. Тоді виясняється, що випливає їз даного припущення (на основі теорем, аксіом і т.п.)
3. Встановлюємо протиріччя нашого припущення із геометричними даними.
4. Робиться висновок про те, що наше припущення є хибним, а вірне твердження протилежне тому, тобто те   що потрібно було довести.

Принцип Діріхлє

В комбінаториці принцип Діріхлє  ( принцип ящиків) твердження, зформульоване німецьким математиком в 1834 році, яке встановлює зв’язок між об’єктами («кроликами») і контейнерами («клітками») при виконанні певних умов. В англійській або інших мовах дане твердження відомо, як «принцип голубів і ящиків».

Принцип Діріхлє застосовується в теорії діофантових наближень при аналізі системи лінійних нерівностей. Найбільш найпоширенішим формуванням цього принципу: якщо кролики розмістити в клітки, число кроликів більше числа кліток, то хоча б в одній із кліток буде знаходитись більше одного кролика.

Загальне формулювання звучить так: якщо M кроликів розмістити в N кліток, то хоча б в одній із кліток знаходитимиться не менше кроликів, а також хоча б одній клітці знаходитиметься не більше M/N кроликів.

Має право на існування і таке формулювання: якщо число кліток більше за число кроликів, то як мінімум одна клітка порожня.

Контрприклад

Контрприклад – який заперечує вірність деякого твердження. Побудова контрприкладів – звичайний спосіб заперечення гіпотези. Якщо маємо твердження « Для будь якого Х з множини М виконується властивість А» , то контрприкладом для даного твердження буде: «Існує об’єкт  із множини М,  для якого властивість А не виконується».

Щоб знайти контрприклад  трапляється певні складності. В таких випадках на допомогу приходить комп’ютер.

Інваріант

Інваріант в математиці – це властивість деякого класу (множини) математичних об’єктів залишатися незмінними при перетвореннях деяких типів.

При розв’язуванні деяких  завдань потрібно розглядати крайні випадки (правило крайнього). Більш природніше ситуація виникає тоді, коли потрібно знайти число елементів скінченної множини, а відповідь неоднозначна. При подальшому вивченні властивості елементів числової множини, бажано вивчати чи вірні умови для більшого або найменшого елемента множини (при умові, що існує найбільший і найменший елемент). Якщо мова іде про множину точок площини, то бажано розглядати крайню ліву (праву) або верхню (нижню) точки цієї площини.

Метод перебору

Метод перебору застосовується при розв’язуванні завдань в яких доводиться перебирати різні варіанти. Перебор повинен бути вірним, тобто таким, при використанні якого розглядаються всі випадки, які можуть відкинути завідомо непотрібні варіанти, що дає зменшити об’єм роботи. Застосовуються в основному тоді, коли значення шуканої величини може бути тільки цілим числом. А множина значень є скінченною. Метод перебору широко застосовується при розв’язанні задач на відновлені запису при виконанні дій над числами і близьких завдань на числові ребуси.

Графи

Графом на площині називають скінченну множину точок площини, деякі з них з’єднані лініями. Ці точки називають вершинами графа, а з’єднання їх лініями – ребрами. Число ребер, яка слідує із вершин графа, називають степенем цієї вершини. Прикладом графів може бути будь-яка карта  доріг, електросхема, креслення многокутників і т.п. Довгий час панувала деяка думка, що теорія графів застосовувалась тільки при розв’язанні логічних задач.

Індукція

Індукція – метод отримання загального твердження із окремих спостережень. Метод доведення, при якому перевіряється твердження для кінцевого числа випадків, які вичерпують усі можливі варіанти називають повною індукцією. Цей метод називають методом – математичної індукції. Цей термін з’явився у 1838 році в статті де Моргана  в британській енциклопедії. Цей метод вперше був розроблений в 1665 році Б.Паскалем. Зараз він широко використовується в математиці для доведення тотожностей, нерівностей та інших математичних тверджень.

Спосіб доведення методом математичної індукції полягає в слідуючому:

1. створити базу індукції  ( доводять або безпосередньо перевіряють твердження, формули для n=1);
2. здійснюють індуктивний перехід (пропонують справедливість для деякого натурального числа n= n=1);
3. доводять справедливість твердження для n=k+1.