Інваріанти

Задача 4.1. На острові Сіробуромалин живуть хамелеони: 13 сірих, 15 бурих і 17 малинових. Якщо два хамелеони різних кольорів зустрічаються, то вони обидва міняють свій колір на третій. Чи може трапитися, що в деякий момент всі хамелеони на острові стануть одного кольору?

Задача 4.2. На дошці написано числа 1, 2, 3, …, 19, 20. Дозволяється стерти будь-які два числа a та b і замість них написати число a + b – 1. Яке число може залишитись на дошці після 19 таких операцій?

Задача 4.3. На дошці написано числа 1, 2, …, 19, 20. Дозволяється стерти будь-які два числа a та b і замість них написати число ab + a + b. Яке число може залишитись на дошці після 19 таких операцій?

Задача 4.4. На дошці написано числа 1, 2, 3, …, 1989. Дозволяється стерти будь-які два числа a та b (a ≤ b) і написати замість них різницю b − a . Чи можна добитись того, щоб на дошці всі числа дорівнювали нулю?

Задача 4.5. Обмінний автомат міняє одну монету на п’ять інших. Чи можна за його допомогою розміняти металеву гривню на 26 монет?

Задача 4.6. У вершинах куба розставлено числа: 7 нулів і одна одиниця. За один хід дозволяється додавати по одиниці до чисел у кінцях будь-якого реб-ра куба. Чи можна добитись того, щоб усі числа стали рівними? А чи можна добитись того, щоб усі числа ділились на 3?

Задача 4.7. У кожній клітинці таблиці 8 ´ 8 записано по одиниці. Дозволяється за один хід додати по одиниці до всіх чисел будь-якого квадрата 3 ´ 3. Чи можна за допомогою скінченної кількості таких ходів отримати у вершинах деякого квадрата 4 ´ 4 суму чисел, що дорівнює 2001?

Задача 4.8. Біля річки лежить купа з 1001 каменя. Хід полягає в тому, що з якоїсь купи, що містить більше одного каменя, викидають у річку один камінь, а потім одну з цих куп ділять на дві. Чи можна через кілька ходів залишити на березі лише купки, що складаються з трьох каменів?

Задача 4.9. Було чотири аркуші паперу. Деякі з них розрізали на 8 частин, потім деякі з цих частин розрізали знову на 8 частин і т. д. Коли підрахували за-гальну кількість аркушів, то виявилось, що їх усього є 1986. Доведіть, що підрахунок був неправильним.

Задача 4.10. На дошці записані натуральні числа від 1 до 20. За один крок дозволяється довільну пару чисел x, y замінити на число x + y + 5xy. Чи можна наприкінці отримати число 20002002?

Задача 4.11. Матч між двома футбольними командами закінчився з рахунком 7 : 4. Доведіть, що був момент, коли перша команда забила стільки м’ячів, скільки другій залишалось забити.

Задача 4.12. Деяке число x замінили на число x² – 210, з одержаним числом зробили теж саме і так 100 разів. Одержали знову число x. Знайдіть число x.

Задача 4.13. На дошці записано n одиниць. Із записаними на дошці числами дозволяється проводити наступну дію: витерти будь-які два з них, нехай це a та b, і замість них написати число 2aba + b . Цю операцію повторюють, поки на дошці не залишиться одне число. Доведіть, що це число буде меншим від 1n  .

Задача 4.14. Дано одну купу із 2001 сірника. Двоє грають в наступну гру. Вони по черзі роблять такі ходи ― вибирають довільну купу, що містить більше одного сірника, і ділять на дві менші. Гра продовжується до тих пір, поки кожна купа не буде складатися з одного сірника. При кожному поділі купи на дві записують добуток чисел сірників в отриманих двох нових купах. Мета гравця, який ходить першим, зіграти так, щоб сума всіх записаних чисел ділилася на 1000. Чи може другий гравець йому завадити?

Задача 4.15. Квадратне поле розбито на 100 однакових квадратних ділянок, 9 з яких заросли бур’яном. Відомо, що бур’ян за рік поширюється на ті і тільки ті ділянки, в яких не менше двох сусідніх ділянок заросли бур’яном (сусідніми вважають ті ділянки, які мають спільну сторону). Доведіть, що поле ніколи не заросте бур’яном повністю.

Задача 4.16. 1) Є 4 картки, на яких записані числа 1, 2, 3, 4. Дозволяється виконувати таку операцію: взяти довільні дві картки і помножити записані на них числа на деяке натуральне число (це число може бути різним для різних операцій). Чи можна за допомогою таких операцій добитись того, щоб усі числа стали рівними?

2. Та ж задача для карток, на яких записані числа 1, 2, 3, 6.
3. Та ж задача для карток, на яких записані числа 1, 2, 3, 2, 5.

Задача 4.17. У таблиці (2n + 1) ´ (2n + 1) у кожну клітинку записано по одному плюсу чи мінусу. Можна одночасно змінювати знаки в будь-якому рядку чи стовпчику. Доведіть, що за скінчену кількість таких операцій можна добитись того, щоб кожному рядку і кожному стовпчику плюсів було більше, ніж мінусів.

Задача 4.18. Автомат працює з картками, на яких написані пари чисел. Із картки (a, b) він може зробити картку a2,  b2 , якщо числа a і b парні, або картку (a + 1, b + 1). Із карток (a, b) і (b, c) він може зробити картку (a, c). Попередні картки він також повертає. Спочатку є картка (3, 10).

а) Чи можна отримати картку (1, 100)?

б) Чи можна отримати картку (1, 50)?

в) Для яких натуральних n можна отримати картку (1, n)?

Задача 4.19. Дано многочлени f(x) = x² + x + 2 та g(x) = x³ – x. Чи можна за допомогою скінченної кількості операцій додавання, віднімання та множення над даними многочленами та многочленами, які є результатами цих операцій, отримати многочлен h(x) = x² – 2x?

Задача 4.20. Із чотирицифровим числом можна виконувати наступну операцію: довільні дві цифри a (a > 1) і b його десяткового запису замінити на цифри a – 1 і b + 1 та переставити цифри нового запису. При цьому цифра 0 на першому місці замінюється на цифру 9. Чи можна за допомогою скінченної кількості таких операцій із числа 2008 отримати число 2009?

Задача 4.21. На дошці записано кілька (не менше двох) відмінних від нуля чисел. Дозволяється стерти будь-які два числа x, y і написати замість них числа x + y2009  та y − x2009 . Доведіть, що після довільної кількості таких операцій не можна отримати початковий набір чисел.

Задача 4.22. На чарівній яблуні ростуть 55 яблук. З неї дозволяється зривати 2, 4, 6 або 8 яблук, замість них на яблуні виростають відповідно 4, 10, 8 або 2 нових яблук. Чи може на яблуні в деякий момент часу рости 70 яблук? Чи можна з неї зірвати всі яблука?

Задача 4.23. У двійковій системі числення є лише дві цифри 0 та 1. Чи можна від числа 10101 перейти до числа 11110000, замінюючи записані підряд цифри 01 на 111, 10 — на 001, 11 — на 000? (Заміну можна робити кілька разів.)

Задача 4.24. Чи можна між деякими цифрами числа 123450 вставити три однакові цифри так, щоб одержати просте число?

Задача 4.25. Доведіть, що як би ми не переставляли цифри числа 123579, завжди одержуватимемо складені числа.

Задача 4.26. У клітинках квадратної таблиці 3 ´ 3 розставлені знаки «–» та «+» так:

Дозволяється одночасно міняти знаки на протилежні в усіх клітинках, розташованих в одному рядку або в одному стовпці. Чи можна, провівши кілька таких змін знаків, прийти до таблиці

Задача 4.27. В одній клітинці квадратної таблиці 4 × 4 стоїть знак мінус, а в інших стоять плюси. Дозволяється за один хід в усіх клітинках якогось квадрата 2 × 2 міняти знак на протилежний. Чи можна за кілька таких кроків одержати таблицю з одних плюсів?

Задача 4.28. Дано шість чисел: 1, 2, 3, 4, 5, 6. Дозволяється до будь-яких двох з них додавати по 1. Чи можна за кілька таких кроків зробити всі числа рівними?

Задача 4.29. Чи можна вибрати деяких 5 аркушів підручника з математики так, щоб сума номерів вибраних 10 сторінок дорівнювала 100?

Задача 4.30. Чи можна всі натуральні числа від 1 до 10 поділити на кілька груп так, щоб найбільше число в кожній групі дорівнювало сумі інших чисел цієї групи?

Задача 4.31. На полиці стоять 28 книжок. Дозволяється міняти місцями будь-які дві книжки, що стоять через одну. Чи можна у такий спосіб переставити всі книжки у зворотному порядку?

Задача 4.32. Мама помила 5 склянок і поставила їх на столі догори дном. Дозволяється за один хід перевернути будь-які 2 склянки. Чи можна за кілька таких ходів поставити склянки дном донизу?

Задача 4.33. Чи можна в записі * 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 поставити замість зірочок знаки «+» або «–» так, щоб значення одержаного числового виразу дорівнювало: а) 5;  б) 20?

Задача 4.34. На дошці написані числа 1, 2, 3, …, 9. Дозволяється стерти будь-які два числа і написати їхню суму. Повторивши таку операцію 8 разів, одержимо одне число. Знайдіть це число.

Задача 4.35. Дано числа: 21, 22, 23, 24, 25. Дозволяється будь-яку пару чисел а, b замінити числом а + b + 5аb. Чи можна, виконавши 5 таких замін, отримати число 20002002?

Задача 4.36. Кожну із 5 палиць розламали на 6 частин. Потім деякі з одержаних частин знову розламали на 6 частин і так декілька разів. Чи можна в результаті таких дій одержати 2012 частин?

Задача 4.37. Було 4 аркуші паперу. Деякі з них розрізали на 8 частин, потім деякі з цих частин розрізали знову на 8 частин і т. д. Коли підрахували загальну кількість частин, то їх виявилося 1986. Доведіть, що підрахунок був неправильним.

Задача 4.38. Знайдіть усі натуральні числа х та у, які задовольняють рівність

ху(х + 5у) = 81.

Задача 4.39 Чи існують натуральні числа х та у, для яких виконується рівність

х(х + 1) + 4у = 2001.