Типи олімпіадних задач з математики

    

    

    

Олімпіадні задачі в математиці - термін для позначення кола задач, для вирішення яких обов'язково потрібно несподіваний і оригінальний підхід.

Олімпіадні задачі отримали свою назву від популярних змагань школярів і студентів, так званих математичних олімпіад. Мета створення задач цієї категорії - виховання в майбутніх математиків таких якостей як творчий підхід, нетривіальне мислення та вміння вивчити проблему з різних сторін. Не випадково академік А. Н. Колмогоров у своїй промові на відкритті порівняв роботу математика з «низкою розв'язання (часом великих і важких) олімпіадних задач».

Рішення олімпіадних задач може зажадати істотної кількості часу навіть від сильного (але нетренованих на їх розв'язання) професійного математика.

Олімпіадні задачі можна знайти в Інтернеті, в періодичних виданнях (журнали Квант , Математическоее просвещение ), а також у вигляді окремих збірок. Вони широко використовуються в роботі математичних гуртків, заочних шкіл і для таких математичних змагань як олімпіади, турніри міст і математичні бої .

Великий внесок у популяризацію методів вирішення олімпіадних завдань внесли публікації журналу «Квант», книги серій « Популярні лекції з математики »,« Бібліотека математичного гуртка » , Збірники олімпіадних завдань, що випускалися видавництвами « Наука »,« Просвещение », перекладені - видавництвом« Мир », і інші книги, а також численні веб-сайти, присвячені олімпіадних задачах.

Завдання олімпіадного типу, відома з часів Евкліда , наприклад:

Довести, що існує нескінченно багато простих чисел .

Задача розв'язується методом від супротивного . Припустивши, що простих чисел скінченне число N, розглядаємо число, наступне за їх добутком   SHAPE  \* MERGEFORMAT  . Очевидно, що воно не ділиться ні на одне з використаних у добутку простих чисел, даючи в залишку 1. Значить, або воно саме просте, або воно ділиться на просте число, не враховане в нашому (імовірно повному) списку. У квсякому разі, простих чисел, принаймні, N+1. Протиріччя з припущенням про скінченність.[37]

Незважаючи на унікальність олімпіадних завдань, можна все-таки виділити кілька типових ідей, які складають  суть задач.  Зрозуміло, за визначенням, такий список буде неповним.

·        Задачі на інваріант

·        Задача – гра

·        Комбінаторика

·        Теорія графів

·        Геометрія  

Не існує єдиного методу розв’язання  олімпіадних задач.  Навпаки, кількість методів постійно поповнюється. Деякі зазачі можна розв`язати   кількома різними методами або комбінацією методів. Характерна особливість олімпіадних задач в тому, що розв’язання  з вигляду нескладної проблеми може зажадати застосування методів, що використовуються в серйозних математичних дослідженнях. Нижче наводиться (за визначенням) неповний список методів розв’язання олімпіадних задач:

·        Доведення выд супротивного

·        Принцип Діріхле

·        Метод розмальовки

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

·        Математична індукція

·        Рекурсія

·        Метод додаткової побудови

·        Метод Гауса

1.1. Інваріант

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

Задача 1.1. У файлі зберігаються 2003 одиниці і 232 нуля. Програма читає з файлу два довільних числа, видаляє, і записує на їх місце 0, якщо вони були рівні, і 1, якщо ні. Програма запускається багаторазово. Наприкінці у файлі залишається тільки одне число. Чому воно дорівнює, 0 або 1?

Розвязання: Незважаючи на те, що варіантів дії програми дуже багато, ми можемо встановити відповідь однозначно. Що може прочитати програма за кажний окремий  запуск? Або 0 і 0 (і записати 0), або 0 і 1 (і записати 1), або 1 і 1 (і записати 0). У перших двох випадках сума всіх чисел у файлі не змінюється, в останньому - зменшується на 2. У кожному разі, парність цієї суми залишається колишньою. Початково сума була      2003 * 1 +232 * 0 = 2003 - непарна, значить, і в кінці буде непарна. Але наприкінці залишається тільки одне число - воно і дорівнює сумі всіх - тому воно непарне. А так як у файлі бувають тільки нулі й одиниці, то це 1.

Задача 1.2. Є три числа, які можна замінювати за такими правилами: числа a, b і c стираються і замість них записуються (a + b) / 2, (b + c) / 2 і (a + c) / 2.Можно Чи з чисел 101, 73, 125 отримати 77, 79 і 83?

Розвязання: А давайте так, "про всяк випадок", подивимося, як міняється сума чисел. Було a + b + c, а стало ... замість них записуються (a + b) / 2 + (b + c) / 2 + (a + c) / 2 = (2a +2 b +2 c) / 2 = a + b + c - не змінилася. Тобто, як не крути, а сума трьох чисел не змінюється. Але 101 +73 +125 = 299, а 77 +79 +83 = 239 - суми вихідної та кінцевої трійки різні. Тому з однієї не можна отримати іншу.

(!) А ті, хто захоче взяти в якості інваріанта парність суми або її залишок по якомусь модулю, швидше за все, помиляться, так як початкова та кінцева суми розрізняються на 60, а дільників у 60 ох як багато.

Задача 1.3. Знову є три числа, які можна замінювати вже за іншими правилами: a, b і c - на ab/c, ac/b і bc/a. Чи можна з 5, 17/6 і 3/5 отримати 16/5, 9/4 та 7/6?

Розв’язання: Ну, про те, куди тут переходить сума чисел, навіть думати не хочеться. Що ще буває, крім суми? Добуток, наприклад. Перед операцією добуток  чисел - abc, а після: (ab/c) * (ac/b) * (bc/a) = a2b2c2/abc=abc - не змінилося!З начить, добуток трьох чисел залишається постійним при всіх операціях. Але на початку воно було рівним 5*(17/6)*(3/5)= 8,5, а наприкінці (16/5)*(9/4)*(7/6) = 8,4 - не рівні. Тому відповідь "не можна".

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

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

Інваріант як характеристика нечислових об'єктів. У всіх попередніх прикладах в задачі фігурували числа, від яких ми в якості інваріанта брали якусь функцію. Але, звичайно, у початковому формулюванні може не бути ніяких чисел! Що тоді робити? Звичайно, ці числа придумати.

Задача 1.4. У мові програмування MustDie всього дві команди, для стислості званих M і D. Через збій в компіляторі, дія програми не зміниться, якщо з неї викинути шматок коду MDDM, а також якщо в будь-яке її місце вставити шматок коду DMMDMD або MDMD. Чи можуть програми MMDMD і DMMDD виконуватися однаково?

Розв’язанная: Наше кажучи: чи існує таке рівнозначне перетворення коду, яке переводить одну програму в іншу? Ні, звичайно, і ви вже здогадалися що інваріант тільки треба придумати. В одному шматку 2 команди M 2 команди D, у другому тих і інших по 3, у третьому - знову по 2. Здається, ясно: у будь-якому вставленомк або видаленому шматку команд M і D порівну. Значить не змінюється, правильно, різниця між числом тих і інших команд. Вона буде нашим інваріантом - і дуже добре, так як в одній програмі на одну більше команд M, а в інший на одну більше команд D (значення різниці помінялося в 1 на -1).

Вправа 1.1. Доведіть, що всі білки можуть зібратися на одній ялинки тоді і тільки тоді, коли їх непарне число. (Тобто, для парних чисел узагальнити дане вище рішення, для непарних - придумати приклад.)

(!) Різниця якихось кількостей і набір попарних різниць - теж типові інваріанти. Після суми і твори наступним справою треба перевіряти саме різниці.

Розв’язання: Де ж шукати інваріант? Із сумою чисел у файлі якось складно, тому що третя програма змінює її чорт знає як. В тому сенсі, що знаючи суми чисел у двох вхідних файлах ми не можемо визначити суму чисел у вихідному файлі. Зрізницею чисел у файлі все краще: перша програма не змінює різницю ((X+1)-(Y +1) =XY), друга -ділить її на 2 

(X/2-Y/2 = (XY) / 2) , а третя - складає різниці (XZ = (XY) + (YZ)). Що ж не змінюється при всіх цих перетвореннях - так відразу і не збагнеш ...

Поставимо ескперімент (так, математика - наука експериментальна!).

Вихідний файл (5, 19) можна пропустити тільки через першу програму і отримати файл (6, 20). З нього можна далі робити послідовність (7, 21), (8, 22) і т.д., а можна запустити другу програму і отримати файл (3, 10). З нього можна зробити послідовність (4, 11), (5, 12) ... (19, 26). Потім можна запустити третю програму на (5, 19) і (19, 26) і отримати файл (5, 26) ...

Порахуємо різниці: 5-19 = -14 = 6-20 = 7-21 = 8-22 = ...; 3-10 = -7 = 4-11 = 5-12 = ... = 19-26; 5-26 = -21. Що ж спільного у чисел -14, -7, -21? Звичайно, вони всі на 7 діляться. От нехай ця подільність і буде інваріантом.

Дійсно, коли різниця не змінюється, то й подільність збережеться; коли різниця ділиться на 2, то подільність на 7 не зникне (2 і 7 взаємно прості); а коли різниці, що діляться на 7, складаються, то сума теж ділиться на 7.Зрозуміло, що, маючи на початку файл з різницю чисел, що ділиться на 7, ми тільки такі різниці і будемо отримувати. Але різниця 1-2004 = -2003 на 7 не ділиться, і такий файл ми отримати не зможемо.

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

Глибокий сенс тут у чому: інваріант може залежати не тільки від правил, за якими проводяться перетворення, але і від початкових даних. Як тут: значення різниці за модулем 7, взагалі кажучи - не інваріант при вироблених перетвореннях. Але при конкретних початкових умовах, коли це значення з самого початку дорівнює 0 - тоді воно стає інваріантом.

Безумовно, якщо типові інваріанти (сума, добуток, різниці та їх значення за якимось,зразу помітним, модулем) не підходять, то корисно поставити експеримент: проробити кілька перетворень і пошукати деякі закономірності в тому, що при цьому буде виходити.

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

Задача 1.5. На дошці 3x5 всі клітини білі, а один кут чорний. За хід можна поміняти колір всіх клітин в одному рядку або стовпці. Чи можна всі клітини зробити білими?

Розв’язання: Парність числа чорних клітин на всій дошці, на жаль, змінюється дуже часто, а тому нам не допоможе. Де б знайти таку частину дошки, на якій ця парність незмінна? У нас тут в умові нерегулярність в кутку - так візьмемо 4 кута. При операції перефарбування змінює колір рівно два кути, або жоден - тобто парність числа чорних кутів - інваріант. Але на початку такий кут один, а наприкінці хочеться нуль - не можна.

Задача 1.6. На колі стоїть 12 точок, в одній написано -1, в інших +1. Можна змінити знак у трьох одиниць підряд. Чи можна здвинути єдину -1 до сусідньої вершину?

Розв’язання: Нехай, для визначеності, ми зрушили -1 до сусідньої проти годинникової стрілки вершину (інакше можна всю картинку дзеркально відобразити і отримати саме таку). Давайте занумеруем вершини, починаючи з вихідної -1, вже за годинниковою стрілкою (тоді те місце, куди зрушила -1 - це вершина 12). Давайте виділимо таку частину (безліч вершин), де є перша вершина, немає 12-й, а парність кількості-1 - інваріант (тоді ця кількість в даній частині треба буде змінити з 1 до 0, а це неможливо з- за парності).

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

- Шахова (два кольори чергуються так, що будь-які дві сусідні по стороні клітини - різних кольорів);

- "матрас" (чередування строк, викрашенних у два кольори - або стовбців);

- "Матрац" (чергування рядків, пофарбованих у два кольори - або стовпців);

- Збільшена шахова (у шаховому порядку фарбуються не окремі клітини, а цілі блоки 2x2, 3x3 і т.д.);

- Збільшений"матрац" (чергуються не рядки, а однакові по товщині блоки з рядків);

- "Матрац" в N кольорів: чергуються рядки, пофарбовані у кольори, 1-й, 2-й, ... N-й, 1-й, 2-й і т.д.

- Шахова в N кольорів - легше показати, ніж написати; приклад для 3-х кольорів; можна і по-іншому, щоб одноколірні діагоналі були нахилені в інший бік.

close