Приклад 4.1. Кенгуру стрибає уздовж прямої. Довжина кожного стрибка дорівнює 1 м. Чи може кенгуру, перебуваючи в деякій точці прямої, за 101 стрибків знову повернутися у цю ж точку?
Розв’язання. Якби кенгуру повернувся у початкову точку, то кількість стрибків в один бік дорівнювала б кількості стрибків у протилежний бік і загальна кількість стрибків була б парною. Число 101 непарне, тому кенгуру за 101 стрибків повернутися у ту саму точку не може. ■
Приклад 4.2. На дошці написані числа 1, 2, 3, …, 11. Дозволяється стерти будь-які два числа і написати їхню суму, зменшену на 1, тобто, якщо стерли числа а і b, то можна написати число а + b – 1. Повторивши таку операцію 10 разів, одержимо одне число. Знайти це число.
Розв’язання. Якщо замість чисел а і b написати число а + b – 1, то сума усіх чисел на дошці зменшиться на 1. Знайшли інваріант: сума усіх чисел на дошці після кожної операції зменшується на 1.
Початкова сума: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 = 66. За 10 операцій сума зменшиться на 10 і дорівнюватиме 56.
Отже, єдине число, яке залишиться на дошці, — число 56. ■
Приклад 4.3. На столі стоять 9 чашок — усі догори дном. Дозволяється за один хід перевернути будь-які 4 чашки. Чи можна за кілька таких ходів домогтися того, щоб усі чашки стояли дном донизу?
Розв’язання. Якщо перевернути 4 чашки, то для них можливі такі варіанти:
|
Було догори дном |
Стане догори дном |
|
4 |
0 |
|
3 |
1 |
|
2 |
2 |
|
1 |
3 |
|
0 |
4 |
Кількість чашок, які стоять догори дном або не змінюється, або збільшується чи зменшується на парне число. Отже, парність кількості таких чашок не змінюється. Оскільки спочатку їх була непарна кількість (9), то одержати парну кількість (0) неможливо. ■
|
Приклад 4.4. Від шахової дошки розміром 8 ´ 8 вирізали крайню верхню ліву і крайню нижню праву клітинки. Чи можна решта дошки замостити кісточками доміно, покриваючи однією кісточкою рівно дві клітинки дошки? |
|
Розв’язання. Щоб покрити 62 клітинки решта дошки, потрібні 31 кісточки доміно, які можуть покрити однакову кількість чорних і білих клітинок. Оскільки вирізані клітинки мають однаковий колір, то залишилася різна кількість чорних і білих клітинок. Отже, решта дошки замостити кісточками доміно не можна. ■
Приклад 4.5. На чудо-дереві ростуть 25 ананасів та 10 кокосів. Протягом одного дня дозволяється одночасно зірвати з нього два плоди. Якщо зірвати два ананаси або два кокоси, то відразу виростає ще один кокос, а якщо зірвати один ананас та один кокос, то виростає один ананас. Через скільки днів на дереві залишиться один плід? Який це плід?
Розв’язання. Кожного дня кількість плодів зменшується на 1, тому на 35-й день залишиться один плід. За один день число ананасів або зменшується на 2, або не змінюється. Спочатку була непарна кількість (25) ананасів, тому непарною має бути кількість ананасів і на 35-й день. Отже, єдиний плід, який на залишиться дереві, — ананас. ■
Приклад 4.6. Дано 10 чисел ― одна одиниця і 9 нулів. Дозволяється вибирати два числа і замінювати кожне з них їх середнім арифметичним. Яке найменше число може виявитися на місці одиниці?
Розв’язання. Зрозуміло, найвигідніша стратегія ― кожен раз замінювати те число, що опиняється на місці одиниці, на середнє арифметичне його і найменшого з решти чисел. Зрозуміло, якщо найменше з решти чисел менше від самого числа.
Дев’ять разів ми з цього алгоритму будемо вибирати другим числом нуль і замінювати обидва числа на їх середнє арифметичне, тобто на половину першого числа. В результаті замість одиниці буде стояти 129 = 1512 , а замість нулів ― степені двійки від мінус першого до мінус дев’ятого. Далі зменшувати вже нікуди.
Відповідь. 1512
Приклад 4.7. У трьох клітинках квадратної таблиці 4 ´ 4 стоять знаки «–», а в інших — знаки «+»:
|
+ |
+ |
+ |
+ |
|
+ |
+ |
− |
+ |
|
+ |
− |
+ |
+ |
|
+ |
+ |
− |
+ |
Дозволяється одночасно міняти знаки на протилежні в усіх клітинках, розташованих в одному рядку або в одному стовпці. Довести, що, скільки б ми не проводили таких змін знаків, нам не вдасться одержати таблицю з одних знаків «+».
Розв’язання. Замінимо знак «+» на число 1, знак «–» на число –1 і покажемо, що, скільки б ми не проводили змін знаків чисел рядків або стовпців, нам не вдасться одержати таблицю з одних одиниць.
|
1 |
1 |
1 |
1 |
|
1 |
1 |
−1 |
1 |
|
1 |
−1 |
1 |
1 |
|
1 |
1 |
−1 |
1 |
Якщо у рядку (стовпці) стоять числа a, b, c, d, то при зміні знаків добуток чисел рядка (стовпця) не змінюється, бо (–a)(–b)(–c)(–d) = abcd. Тому при зміні знаків чисел одного рядка або стовпця не змінюється й добуток усіх чисел таблиці. Спочатку маємо таблицю, в якій добуток усіх чисел дорівнює –1. У таблиці з одних одиниць такий добуток дорівнює 1. Тому перехід до таблиці з одних одиниць неможливий.
Отже, перехід від заданої таблиці до таблиці з одних знаків «+» також неможливий. ■
Приклад 4.8. Дано три числа: 2, 2, 12 . Дозволяється будь-які два з них замінити двома такими: сумою, поділеною на 2 , та різницею, поділеною на 2 . Чи можливо, виконавши процедуру декілька разів, дістати трійку чисел: 1, 2 , 1 + 2 ?
Розв’язання. Неважко помітити, що
a + b22 + a - b2 2= a2 + b2 ,
тобто при виконанні таких процедур не змінюється сума квадратів трійки чисел. Початкова сума квадратів дорівнює 132 , а кінцева має дорівнювати 6+22 .
Відповідь. Неможливо. ■
Приклад 4.9. В одній клітинці квадратної таблиці 8 ´ 8 стоїть знак мінус, а в інших стоять плюси. Дозволяється за один хід в якомусь із квадратів 2 ´ 2 змінювати знаки на протилежні. Довести, що за допомогою таких ходів не можна отримати таблицю з одних плюсів.
Розв’язання. При заміні знаків у квадраті 2 ´ 2 на протилежні кількість мінусів може змінитись лише на 2 або на 4, тобто в усій таблиці кількість мінусів зберігає свою парність, а тому змінитись з 1 на 0 не може. ■
Приклад 4.10. На кожному з 44 дерев, що розміщені по колу, сидять по одному горобцю. Час від часу якісь два горобці перелітають на сусіднє дерево ― один за годинниковою стрілкою, а другий ― проти. Чи можуть усі горобці зібратися на одному дереві?
Розв’язання. Пронумеруємо дерева по колу з 1-го по 44-е. Сума номерів дерев, на яких сидять горобці, при їхньому перелітанні або не змінюється, або змінюється на 44, тому остача відділення цієї суми на 44 не змінюється. Спочатку ця остача дорівнювала 22, а якщо всі горобці сядуть на одне дерево, ця остача дорівнюватиме нулю. Отже, горобці не можуть зібратись на одному дереві. ■
Приклад 4.11. На координатній площині є чотири точки з цілими координатами. Дозволяється замінити будь-яку з цих точок на точку, симетричну їй відносно будь-якої іншої з цих точок. Чи можна за декілька таких операцій перейти від точок (0, 0), (0, 1), (1, 0), (1, 1) до точок з координатами (0, 0), (1, 1), (3, 0), (2, −1).
Розв’язання. Очевидно, що можливість переходу від першої четвірки точок до другої рівносильна можливості переходу від другої четвірки точок до першої.
У другій четвірці точок різниця координат кожної точки дорівнює 0 або 3, тобто ділиться на 3. Якщо точка М2(x2, y2) симетрична точці М1(x1, y1) відносно точки М0(x0, y0), то їхні координати пов’язані рівностями x0=x1 + x22, y0=y1 + y22 , звідки отримуємо:
x2=2x0-x1, y2=2y0-y1, x2-y2=2x0-y0-x1-y1.
Звідси видно, що коли різниця координат x – y у якихось двох точок діляться на 3, то й різниця координат третьої точки теж ділиться на 3. Тому, виходячи з другої четвірки точок, не можна отримати точки (0, 1), (1, 0).
Відповідь. Ні. ■
Приклад 4.12. Числова послідовність a1, a2, a3, … , в якій a1=2, a2= = 500 та a3 = 2000, при всіх натуральних n ≥ 2 задовольняє умову
an + 2 + an + 1an + 1 + an - 1 = an + 1an - 1 .
Довести, що всі члени цієї послідовності є натуральними числами, причому a2001 ділиться без остачі на 22001.
Розв’язання. Елементарними перетвореннями отримаємо, що при всіх натуральних n ≥ 2 виконується рівність
an + 2an + 1=an + 1an - 1 , або an + 2an + 1an=an + 1anan - 1 .
Отже, значення виразу an + 1anan - 1 не залежить від n (є інваріантом), а тому
an + 2an + 1an=an + 1anan - 1= … =a3a2a1=2.
Отже, дана послідовність задовольняє рекурентне співвідношення: a1 = 2, a2 = 500, an + 1 = 2anan - 1 при n ≥ 2 . Тому всі члени послідовності є натуральними числами, причому для будь-якого n ≥ 1 число an + 1an є парним. Враховуючи рівність
a2001=a2001a2000·a2000a1999·… ·a2a1·a1 ,
отримуємо, що a2001 ділиться без остачі на 22001. ■
Приклад 4.13. На шаховій дошці стоїть чорний слон і біла тура. Білі, як водиться, ходять першими. Довести, що при правильній грі біла тура ніколи не опиниться під боєм чорного слона.
Розв’язання. Слон завжди залишатиметься на полях одного кольору (це і є інваріант даної задачі). Тому якщо тура кожним своїм ходом буде зупинятися на полі іншого кольору, її неможливо буде побити. ■
Приклад 4.14. На дошці написані числа 2, 6, −5, 3. Дозволяється: 1) збіль-шити будь-яке з цих чисел на 2 і зменшити будь-яке інше на 6; 2) збільшити будь-яке з цих чисел на 3, збільшити будь-яке інше на 1 і збільшити будь-яке третє на 4. Виконуючи в будь-якому порядку ці дві операції (якщо потрібно ― багаторазово), зрівняти написані на дошці числа. Або довести, що зробити це неможливо.
Розв’язання. Ми можемо виконувати операції 1) і 2) скільки завгодно разів і в будь-якому порядку, однак зрівняти числа на дошці нам не вдасться. Але як довести, що спроби зрівняти числа на дошці марні? Ось тут нам і знадобиться поняття «інваріант». У даному конкретному випадку інваріантом буде остача від ділення на 4 суми записаних на дошці чисел. Операція 1) зменшує суму записаних на дошці чисел на 4. Операція 2) збільшує суму записаних на дошці чисел на 8. Виходить, обидві ці операції не змінюють остачу від ділення суми записаних на дошці чисел на 4. У вихідній комбінації чисел залишок від ділення суми чисел на 4 дорівнює 2. Якщо всі чотири числа дорівнюють один одному, то остача від ділення суми чисел на 4 дорівнює 0. Це і доводить, що операціями 1) і 2) зрівняти записані на дошці числа не можна. ■
Приклад 4.15. На шаховій дошці дозволяється перефарбувати з чорного кольору на білий і з білого ― на чорний колір одразу всі клітинки якої-небудь горизонталі чи вертикалі. Чи може через кілька таких перефарбувань утворитися дошка, у якої є рівно одна чорна клітинка?
Розв’язання. При перефарбуванні горизонталі чи вертикалі, яка містить k чорних та 8 – k білих клітинок, отримаємо 8 – k чорних та k білих клітинок. При цьому кількість чорних клітинок зміниться на парне число, бо
8- k- k = 8-2k = 24-k.
Оскільки парність чорних клітинок зберігається, то із початкових 32 чорних клітинок ми не можемо отримати одну чорну клітинку.
Відповідь. Не можна. ■
Приклад 4.16. Було 5 аркушів паперу. Деякі з них розрізали на 5 кусків кожний. Потім деякі з одержаних кусків знову розрізали на 5 кусків і так зробили декілька разів. Чи можна в результаті виконання таких дій отримати 1975 кусків паперу?
Розв’язання. Після розрізання одного куска кількість кусків збільшується на 4. Тому остача від ділення кількості всіх кусків на 4 не змінюється. Але 5 при діленні на 4 дає остачу 1, а 1975 ― остачу 3.
Відповідь. Не можна. ■
Приклад 4.17. В одній вершині куба написали число 1, в інших нулі. Можна додавати по 1 до чисел, які записані на кінцях довільного ребра. Чи можна добитися того, щоб всі числа ділились на 3?
Розв’язання. Пофарбуємо вершини куба в шаховому порядку. Після цього сума чисел в білих вершинах завжди буде відрізнятись на 1 від суми цифр в чорних вершинах, бо до тих і других кожен раз додається 1. Ці суми одночасно ділитися на 3 не можуть.
Відповідь. Не можна. ■
Приклад 4.18. 1989 чоловік вишикувані в шеренгу. Чи завжди їх можна вишукувати по росту, якщо дозволяється міняти місцями двох людей, які стоять через одного?
Розв’язання. При перестановках зберігається парність номера місця. Тому, коли самий високий стоїть на парному місці, він ніколи не стане першим.
Відповідь. Не завжди. ■
Приклад 4.19. У кутку квадрата 3 ´ 3 стоїть знак мінус, в усіх інших клітинках ― плюси. Можна змінювати всі знаки в довільному рядку чи довільному стовпчику на протилежні. Чи можна одержати таблицю лише з одних плюсів?
Розв’язання. Кількість мінусів у кутовому квадраті 2 ´ 2 завжди буде непарною.
Відповідь. Не можна. ■
Приклад 4.20. Чи можна круг розрізати на декілька частин, з яких скласти квадрат? (Розрізи ― це частинки прямих і дуги кіл.)
Розв’язання. Розглянемо інваріант: різниця сум довжин увігнутих і опуклих граничних дуг всіх частин. Ця величина не змінюється при розрізанні однієї частини на дві і при складанні однієї частини з двох.
Для одиничного круга цей інваріант дорівнює 2