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

 Чому не можна нарізати рівно 60 шматків паперу, якщо будь-який кусок паперу можна розрізати або на 5 або на 7 кусків?

Осмислення нових знань.

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

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

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

1. Було 5 аркушів паперу. Деякі з них розрізали на 5 кусків кожний, Потім деякі з одержаних кусків знову розрізали на 5 кусків і так зробили декілька разів. Чи могло в результаті виконання таких дій одержатись 1975 кусків?( інваріантна властивість: кількість кусків після розрізання на п’ять кусків збільшується на чотири. 5+ 4n не рівно1975).

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

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

4. На дошці написано числа 1, 2, 3, ...,1989. Дозво­ляється стерти будь-які два числа і написати замість них різницю. Чи можна досягти того, щоб на дошці всі числа дорівнювали нулю?

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

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

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

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

  

Практична частина заняття.

Завдання для вироблення умінь та навичок використовувати властивості інавіанту.

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

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

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

4.  Число х замінили на х² - 2¹⁰, з одержаним числом зробили те саме і так 100 разів. Одержали знову число х. Знайти число х.

5.  В трьох вершинах квадрата знаходяться три коники. Вони грають в «чехарду». При цьому коли коник А стрибає через коника В, то після стрибання від попадає в точку, яка симетрична точці А відносно точки В. Чи зможе після декількох стрибків один з коників попасти в четверту вершину даного квадрата?

6.  На доійці записані числа від 1 до 20. Можна довільну пару чисел (х;у) замінити на число х + у + 5ху. Чи можна наприкінці одержати число 19901989?

7.  Фігура ходить по діагоналі прямокутника Іхп (наприклад, для коня це 1x2). При якому п вона зможе попасти з будь-якої клітинки на необмеженій шаховій дошці?

8.  На дошці записані числа від 1 до 20. Можна пару чисел (х;у) замінити на х + у + ху. Яке число залишиться після 19 операцій?

9.  В шести секторах круга лежить по "снікерсу". Можна одночасно пересунути два "снікерси" в сусідні сектори, рухаючи їх в протилежних напрямках. Чи можна одержати таке їх розташування: 5,1,0,0,0,0 ?

10.  В квадраті 8x8 стоять цілі числа. Можна додавати по одиниці до всіх чисел довільного квадрата 3x3 або 4x4. Чи завжди можна добитись того, що всі числа в таблиці ділилися на 3 ?