Задача зі скянками на інваріант

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

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

Задача 1. На столі стоять вверх дном сім склянок. Дозволяється перевертати одночасно будь-які дві склянки (зрозуміло, можна перевернути будь-які стакан, що стоїть догори дном, так, щоб він стояв на дні, а можна перевернути будь-який  не перевернений  стакан так, щоб він став стояти догори дном). Чи можна добитися того, щоб всі сім склянок на столі стояли на дні?  

Розв′язання

Звичайно ж, спочатку потрібно спробувати перевернути  стакани. Однак досить швидко стає зрозуміло, що так просто ця задачка не вирішується. Тоді виникає бажання довести, що домогтися необхідної розстановки склянок неможливо. Як це зробити? Давайте порівняємо кількості склянок, що стоять на дні і догори дном. Спочатку ми маємо 7 склянок, які стоять вверх дном і 0 склянок, що стоять на дні. Ми можемо перевернути будь-які дві склянки. Які б стакани ми не вибрали, у нас буде 5 склянок догори дном і 2 склянки, що стоять правильно. Наступного разу ми можемо перевернути стакани різними способами. Так, ми можемо поставити на дно дві склянки, що стоять вверх дном. Тоді у нас залишиться 3 склянки, що стоять вверх дном, а 4 склянки стоятимуть правильно. Ми можемо перевернути один стакан, що стоїть догори дном, і один стакан, що стоїть правильно. Тоді нічого не зміниться, і в нас залишиться 5 склянок, що стоять вверх дном, і 2 склянки, що стоять на дні. І останній варіант: ми можемо перевернути дві склянки, які стоять на дні. Тоді отримаємо вихідну ситуацію, а саме 7 склянок догори дном і 0 склянок, що стоять правильно.

Давайте подивимося, що спільного у всіх цих ситуаціях. Знайдемо різниця числа склянок, що стоять вверх дном, і числа склянок, що стоять на дні. У вихідному варіанті ця різниця дорівнює семи. Після першого перевертання вона стає дорівнює трьом. А далі, в залежності від обраного варіанту перевертання склянок, вона стане рівною -1, 3 або 7. Ми бачимо, що ця різниця може змінитися тільки на 4. І в даному випадку неважливо, що початково ми розглядали 7 склянок, які були перевернуті догори дном. Якщо ви розглянете випадок, коли a склянок стоять на дні, а b склянок - догори дном, ви прийдете до того ж самого висновку. Як корисного і простого вправи спробуйте зробити це самі. Припустимо, що нам вдалося, перевертаючи стакани, домогтися їх правильного розташування. Тоді в кінцевій ситуації різниця між числом склянок, що стоять вверх дном, і числом склянок, що стоять правильно, дорівнює -7. І ми бачимо, що число -7 відрізняється від 7 на 14 - це число не кратне 4. Отже, діючи описаним в умові завдання способом, домогтися того, що всі 7 склянок стоятимуть на дні, неможливо.

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

У розглянутим завданню інваріантом був залишок від ділення на 4 різниці числа склянок, що стоять вверх дном, і числа склянок, що стоять на дні. Він повинен завжди залишатися рівним 3.