З сірих і М малинових хамелеонів на 3 та перевірте, що попарні різниці у цих залишків не змінюються.
16. Доведіть, що в грі В«15В» не можна поміняти місцями фішки В«15В» і В«14В», залишивши інші на місці.
Ідея рішення.
Розглянемо В«порожнє поле В»як окрему фішку. Ми можемо тільки міняти В«порожню фішкуВ» з сусідніми. Оскільки порожня фішка повинна потрапити на вихідне поле, число наших операцій повинно бути парним. Тому ми можемо отримати конфігурації, що відрізняються від початковій тільки парним числом перестановок.
17. На 44 деревах, розташованих по колу, сиділи по веселому Чижу. Час від часу якісь два чижа перелітають на сусіднє дерево - один за годинниковою стрілкою, а інший - проти. Чи можуть усі чижі зібратися на одному дереві?
Рішення.
Пронумеруємо дерева по колу з 1-го по 44-е. Сума номерів дерев, на яких сидять чижі або не змінюється, або зменшується на 44, або збільшується на 44. Тим самим, залишок від ділення цієї суми номерів на 44 не змінюється. Спочатку цей залишок дорівнює 22, а якщо все чижі сядуть на одне дерево, то він буде дорівнює нулю. Тому чижі не зможуть зібратися на одному дереві.
18. Чи розрізати опуклий 17-кутник на 14 трикутників?
Загальна постановка задачі.
За допомогою інваріантів вирішуються завдання наступного типу : дано безліч М (елементи його ми будемо називати В«позиціямиВ») і правило, за яким дозволяється переходити від однієї позиції до іншої; чи можна з цієї позиції а перейти за кілька кроків в іншу дану позицію p ? Більш спільне завдання: як. для довільної пари позицій а , p встановити, чи можна з а за кілька кроків перейти в р ?
Очевидно, описані ситуації володіють наступним властивість: якщо з позиції a можна перейти в позицію р і з p можна перейти в позицію h , то з a можна перейти в h . Це властивість називається Транзитивні.
Розглянемо конкретну задачу.
Задача 1. Коло розділений на n секторів, в яких якось розставлені n фішок. Дозволяється одночасно пересунути будь-які дві фішки: одну - на один сектор за годинниковою стрілкою, іншу - на один сектор в протилежному напрямку. Чи можна з позиції M, в якій в кожному секторі варто 'по одній фішці, перейти до позиції V , в якій всі фішки зібрані в якомусь одному секторі?
У цьому завданню, крім властивості транзитивності, має місце також наступне важлива властивість: якщо з позиції a можна перейти в позицію р , то й з р можна перейти в a . Це властивість називається симетричністю.
Властивість симетричност...
