Операції та інваріанти

Теоретичні відомості

В задачах, де потрібно з'ясувати, чи можна за допомогою заданих операцій перейти від одного об'єкта до другого, часто корисно знайти "інваріант" - числову характеристику об'єктів (або функцію з якимись іншими значеннями на множині об'єктів),-яка не змінюється при вказаних операціях. Якщо при цьому значення інваріанта на двох об'єктах різні, то перетворити один в інший неможна. В цілочисельних та інших «дискретних» задачах інваріантом часто може бути остача від ділення на 2 (парність) або на інший натуральний дільник.

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

В задачах, де потрібно оцінити кількість операцій чи довести, що їх не можна виконувати безліч разів (наприклад, впевнитись у відсутності "циклу"), іноді буває корисно придумати функцію, яка після кожної дії (операції) монотонно зростає (чи спадає).

Задачі

1.(7-8) Було 5 аркушів паперу. Деякі з них розрізали на 5 кусків кожний, Потім деякі з одержаних кусків знову розрізали на 5 кусків і так зробили декілька разів. Чи могло в результаті виконання таких дій одержатись 1975 кусків?

Відповідь: ні. Вказівка: при розрізані одного куска кількість кусків збільшується на 4. Тому остача від ділення кількості всіх кусків на 4 не змінюється. Але 5 при ділення на 4 дає остачу 1, а 1975 - остачу 3.

2. (8) В одній вершині куба написали число 1, в інших нулі. Можна додавати по 1 до чисел, які записані на кінцях довільного ребра. Чи можна добитися того, щоб всі  числа ділились на 3?

Вказівка: пофарбуємо вершини в шаховому порядку. Після цього сума чисел в білих вершинах завжди буде відрізнятись на 1 від суми цифр в чорних вершинах, бо до тих і других кожен раз додається 1.

Відповідь: ні

3. (8) 1989 чоловік вишикувані в шеренгу. Чи завжди їх можна вишукувати по росту, якщо дозволяється міняти місцями двох людей, які стоять через одного?

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

4. (8-9) В кутку квадрата 3x3 стоїть знак мінус, в усіх інших - плюси. Можна змінити всі знаки в довільному рядку чи довільному стовпчику на протилежні. Чи можна одержати таблицю лише з одних плюсів?

Відповідь: ні. Вказівка: кількість мінусів у кутовому квадраті
2x2 завжди буде непарною.

5.(8-9) Круг поділили на 6 секторів, в кожному лежить по цукерці. За один хід одну цукерку можна перемістити в сусідній сектор. Чи можна зібрати всі цукерки в одному секторі рівно за 20 ходів?

Відповідь:  ні.  Вказівка:  пофррбуйте сектори в  шаховому порядку.

6.(9) На дошці виписали числа 2,3,... 1975. Дозволяється стерти будь-які два числа, записавши замість них їх різницю. Довести, що багатократним повторенням такої операції не можна досягти того, щоб  на дошці залишився один нуль.

         Вказівка: вказана операція не змінює парності суми написаних
чисел.     Оскільки     сума     заданих     чисел      2 + 3 + ... +1975 =

=1977∙987  - непарна, то в кінці залишиться непарне число.