Метод інваріантів

В деяких олімпіадних задач з математики зустрічається така ситуація. Деяка динамічна система послідовно переходе з одного стану в другий. І треба з’ясувати про деяку властивість цієї  систему в кінцевому стані. Однак повністю прослідкувати за усіма переходами виявляється складно, проте відповісти на це питання допомогає  обчислення деякої величини, яка характерна для всіх станів  системи, тобто ця величина зберігається постійною(інваріантною). Зрозуміло, що набагато легше перевірити значення інваріанту у початковому стані системи і у кінцевому кінцевому, аби дати відповідь на запитання задачі.

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

Найчастіше вживаний інваріант – це парність числа. Проте інваріантом може бути також і остача від ділення не тільки на 2, а на довільне натуральне число.

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

Інваріант –  це величина, яка не змінюється в результаті деяких операцій (наприклад, розрізання і перестановка частин фігур не міняє сумарної площі). Якщо інваріант розрізняє два положення, то від одного не можна перейти до іншого. Як інваріант може використовуватися парність або розфарбовування. У завданнях про суму цифр використовуються залишки від ділення на 3 або 9.

 Напівінваріант – величина, що змінюється тільки в один бік (тобто яка може тільки збільшуватися або тільки зменшуватися). Поняття напівінваріанта часто використовується при доведеннях зупинки процесів.

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

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

Зразки задач на знаходження інваріантних властивостей.

Блок 1. Парність і непарність

Задача 7. Чи можна розміняти 25 карбованців за допомогою десяти купюр вартістю 1, 3 та 5 карбованців?

Розв'язання цієї задачі грунтується на простому спостереженні:   сума парної кількості непарних чисел є парною. Узагальнення цього факту виглядає так: парність суми кількох чисел залежить лише від парності числа непарних доданків: якщо кількість непарних доданків є (не)парна, то і сума також є (не)парною.

Задача 8. Чи можливо шахівницю розміру 8х8 обійти конем, почавши обхід з поля h8, закінчивши його на полі а1 так, щоб на кожному полі побувати рівно один раз.

 Розв’язання: За 63 ходи кінь опиниться в чорній клітинці а1, але непарні ходи коня  завжди закінчуються на білій клітинці. Протиріччя доводить неможливість.

Відповідь: не можна.

Задача 9. Петро купив загальний зошит на 96 аркушів і пронумеру­вав всі його сторінки по порядку числами від 1 до 192. Василь вирвав з цього зошита 25 аркушів і додав всі 50 чисел, що на них були написані. Чи міг він дістати 1990?

Задача 10. В ряд записано числа від 1 до 10. Чи можна розставити між ними знаки "+" та "-" так, щоб значення отриманого виразу дорівнювало нулю?

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

Задача 11. Коник-стрибунець стрибає вздовж прямої, причому пер­шого разу він стрибнув на 1 см в якийсь бік, другого — на 2 см і так далі. Доведіть, що після 1985 стрибків він не може зупинитися там, де починав.

Задача 12. На дошці виписано числа 1,2,3,..., 1984, 1985. Дозволя­ється стерти з дошки будь-які два числа і замість них записати модуль їх різниці. Врешті-решт на дошці залишається одне число. Чи може воно дорівнювати нулю?

Блок 2. Олімпіадні задачі на інваріант.

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

Розв’язання. При перефарбуванні горизонталі чи вертикалі, яка містить  к  чорних та 8-к білих клітинок, отримаємо 8-к чорних та к білих клітинок. При цьому кількість чорних клітинок зміниться на парне число, тобто (8-к)- к = 8-2к = 2(4-к). Так як парність чорних клітинок зберігається, із початкових 32 чорних клітинок ми не можемо отримати одну чорну клітинку. Відповідь: не можна.

Задача 2. Було 5 аркушів паперу. Деякі з них розрізали на 5 кусків кожний, Потім деякі з одержаних кусків знову розрізали на 5 кусків і так зробили декілька разів. Чи можна в результаті виконання таких дій отримати 1975 кусків паперу?

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

Відповідь: не можна

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

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

Відповідь: не можна.

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

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

Відповідь: не завжди

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

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

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

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

Блок 3.  Цікаві задачі на інваріант.

Приклад 1. На чудо-дереві ростуть банани і ананаси. За один раз дозволяється зірвати з неї два плоди. Якщо зірвати два банани або два ананаси, то виросте ще один ананас, а якщо зірвати один банан і один ананас, то виросте один банан. У результаті залишився один  плід. Який це плід, якщо відомо, скільки бананів і ананасів росло спочатку?

Розв’язання. Парність числа бананів не міняється, тому, якщо число бананів було парним, то плід, що залишився, –  ананас, якщо число бананів було непарним, то – банан.

Приклад 2. У одній клітці квадратної таблиці 4x4  стоїть знак мінус, а в інших стоять плюси. Дозволяється одночасно міняти знак у всіх клітках, розташованих в одному рядку або в одному стовпці. Доведіть, що, скільки б ми не проводили таких змін знаку, нам не вдасться отримати таблицю з одних плюсів.

Розв’язання. Замінимо знак «+» на число 1 і знак «—» на число  – 1. Відмітимо, що добуток всіх чисел в таблиці не міняється при зміні знаку у всіх чисел стовпця або рядка. У початковому положенні цей добуток рівний - 1, а в таблиці з одних плюсів добуток рівний  +1, чим і доведена неможливість переходу.

Приклад 3. На прямій розташовано дві фішки: зліва червона, справа синя. Дозволяється проводити будь-яку з двох операцій: вставку - двох фішок одного кольору підряд (між фішками або з краю) і видалення пари сусідніх одноколірних фішок (між якими немає інших фішок). Чи можна за допомогою таких операції залишити на прямій рівно дві фішки: зліва синю, а справа червону?

Розв’язання. Розглянемо число різноколірних пар (не тільки сусідніх), де ліва фішка червона, і відмітимо, що парність цього показника не міняється. Але в початковій ситуації наш показник рівний 1, а в бажаній ситуації –  нулю. Тому перейти до бажаної  ситуації неможливо.

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

Розв’язання. Позначимо кількості хамелеонів кожного кольору С, Б і М відповідно. Доведіть, що залишки від ділення на 3 різниць  Б-С, С-М і М - В не міняються.

Приклад 5. На 44 деревах, розташованих по кругу, сиділи по одному веселому чижеві. Час від часу якісь два чижі перелітають один за годинниковою стрілкою, а інший проти,  кожен – на сусіднє дерево. Чи можуть всі чижі зібратися на одному дереві?

Розв’язання. Пронумеруємо дерева по кругу від 1 до 44. Сума номерів дерев, на яких сидять чижі, або не міняється, або зменшується на 44. або збільшується на 44. Тим самим, залишок від ділення цієї суми номерів на 44 не міняється. Спочатку цей залишок рівний 22, а якщо всі чижі всядуться на одне дерево, то він буде рівний нулю. Тому чижі не зможуть зібратися на одному дереві.

Приклад 6. Чи можна круг розрізати на декілька частин, з яких скласти квадрат? (Розрізи – це ділянки прямих і дуги кіл.)

Розв’язання. Розглянемо інваріант: (різниця сум довжин увігнутих і опуклих розрізаних дуг всіх частин. Ця величина не змінюється при розрізанні однієї частини на дві і при складанні однієї частини з двох. Для одиничного круга цей інваріант рівний; два помножити на число «пі», а для квадрата – нулю( немає опуклих і випуклих частин). Тому квадратура круга  неможлива.

Задачі початкового рівня на інваріант для самостійного осмислення ІНВАРІАНТА.

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.  Число х замінили на х² - 210, з одержаним числом зробили те саме і так 100 разів. Одержали знову число х. Знайти число х.

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

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

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

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

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

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

Задачі підвищеної складності для самостійного розв'язування

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

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

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

Задача 4. (7-8). Обмінний автомат міняє одну монету на п'ять інших. Чи можна за його допомогою розміняти металеву гривню на 26 монет?

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

Задача 6. (7-9). У кожній клітинці таблиці 8x8 записано по одиниці. Дозволяється за один хід додати по одиниці до всіх чисел будь-якого квадрата 3x3 . Чи можна за допомогою скінченої кілько­сті таких ходів отримати у вершинах деякого квадрата 4x4 суму чи­сел, що дорівнює 2001?

Задача 7. (8-9). На столі лежить купа з 1001 каменя. Хід поля­гає в тому, що з якоїсь купи, що містить більше одного каменя, вики­дають камінь, а потім одну з цих куп ділять на дві. Чи можна через кілька ходів залишити на столі лише купки, що складаються з трьох камінців?

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

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

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

Теореми  про інваріантні  остачі при діленні степенів на натуральні числа.

Варто мати на увазі, що квадрати цілих чисел при діленні на 3 або 4 можуть давати остачі лише 0 та 1, куби при діленні на 9 - лише 0,  1 та 8. (Перевірте це са­мостійно). Подібні факти в поєднанні з вдалим вибором числа, остачі при діленні на яке ми розглядаємо, часто допомагають розв'язуванню. З допомогою такого вдалого вибору можна доводити, що число не є простим, можна розв'язувати рівняння в цілих числах.

Квадратні лишки

Остачі при діленні квадратів на натуральні числа.

Якщо квадрат натурального числа, тобто,  m² = m∙m, поділити на:

2, то отримаємо остачі 0, 1;

3, то отримаємо остачі 0, 1

4, то отримаємо остачі 0, 1;

5, то отримаємо остачі 0, 1, 4;

6, то отримаємо остачі 0, 1, 3, 4;

7, то отримаємо остачі  0, 1, 2, 4;

8, то отримаємо остачі  0, 1, 4;

9, то отримаємо остачі 0, 1, 4, 7;

10, то отримаємо остачі 0, 1, 4, 5, 6, 9;

11, то отримаємо остачі 0, 1, 3, 4, 5, 9;

12, то отримаємо остачі 0, 1, 4, 9;

13, то отримаємо остачі 0, 1, 3, 4, 9, 10, 12;

14, то отримаємо остачі 0, 1, 2, 4, 8, 9;

15, то отримаємо остачі 0, 1,4, 6,  9, 10;

16, то отримаємо остачі 0, 1, 4, 9;

17, то отримаємо остачі 0, 1, 4, 8, 9,15.

Кубічні лишки

Остачі при діленні кубів на натуральні числа.

Якщо куб натурального числа, тобто,  m³ = m∙m∙m, поділити на:

2, то отримаємо остачі 0, 1;

3, то отримаємо остачі 0, 1, 2;

4, то отримаємо остачі 0, 1, 3;

5, то отримаємо остачі 0, 1, 2, 3, 4;

6, то отримаємо остачі 0, 1, 2, 3, 4, 5;

7, то отримаємо остачі  0, 1, 6;

8, то отримаємо остачі  0, 1, 3, 5, 7;

9, то отримаємо остачі  0, 1, 8;

10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9

Таблиця остач при діленні кубів на цифри

	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1
23	0	0	2	0	3	2	1	0	8
33	0	1	0	3	2	3	6	3	0
43	0	0	1	0	4	4	1	0	1
53	0	1	2	1	0	5	6	5	8
63	0	0	0	0	1	0	6	0	0
73	0	1	1	3	3	1	0	7	1
83	0	0	2	0	2	2	1	0	8
93	0	1	0	1	0	3	1	1	0

Четвіркові лишки

Остачі при діленні четвертих степенів на натуральні числа.

Якщо четверту степінь натурального числа, тобто,  m⁴ = m∙m∙m∙m, поділити на:

2, то отримаємо остачі 0, 1;

3, то отримаємо остачі 0, 1

4, то отримаємо остачі 0, 1;

5, то отримаємо остачі 0, 1;

6, то отримаємо остачі 0, 1, 3, 4;

7, то отримаємо остачі  0, 1, 2, 4;

8, то отримаємо остачі  0, 1;

9, то отримаємо остачі 0, 1, 4, 7;

10, то отримаємо остачі 0, 1, 5, 6;

П’ятіркові лишки

Остачі при діленні п’ятих степенів на натуральні числа.

Якщо п’яту степінь натурального числа, тобто,  m⁵ = m∙m∙m∙m∙m, поділити на:

2, то отримаємо остачі 0, 1;

3, то отримаємо остачі 0, 1, 2;

4, то отримаємо остачі 0, 1, 3;

5, то отримаємо остачі 0, 1, 2, 3, 4;

6, то отримаємо остачі 0, 1, 2, 3, 4, 5;

7, то отримаємо остачі  0, 1, 2, 3, 4, 5, 6;

8, то отримаємо остачі  0, 1, 3, 5, 7;

9, то отримаємо остачі  0, 1, 2, 4, 5, 7, 8;

10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9.

Розв’язування числових задач

n	n2	n3	n4	n4k	nk
...1	1	1	1	1	1
2	4	8	6	6	2,4,8,6
3	9	7	1	1	3,9,7,1
4	6	4	6	6	4,6
5	5	5	5	5	5
6	6	6	6	6	6
7	9	3	1	1	7,9,3,1
8	4	2	6	6	8,4,2,6
9	1	9	1	1	9,1
0	0	0	0	0	0

 У цій таблиці наведено останні цифри натуральних чисел, квадратів, кубів, четвертих степенів і так далі.

Використовуємо цю таблицю для розв’язування задач.

Задача 1. Знайти остачу від ділення квадрата цілого числа на 5.

Розв’язання:

Квадрати натуральних чисел закінчуються цифрами: 0; 1; 4; 5; 6; 9.(колонка 2) то при їх діленні  на 5 одержуємо 0, 1 або 4.

Задача 2. Чи може число виду 1^k+5^m+6ⁿ, де k, m, n – довільні натуральні числа, бути довільним квадратом.

Розв’язання: Кожний доданок закінчується відповідно цифрами: 1, 5 і 6 (колонка 6) і тому їх сума закінчується цифрою 2, а таке число не може бути точним квадратом.

Задача 3. Довести, що число 53⁵³- 33³³ ділиться на 10.

Розв’язання: При виділенні показників степенів 53 і 33 на 4 в остачі одержуємо в кожному випадку 1. Отже, остання цифра числа 55⁵³ така сама, як числа 33³³, бо 53^4∙13+1 і 33^4∙8+1, отже, остання цифра різниці 0, і ця різниця ділиться на 10.

 Задача 4. Які остачі можуть мати точні квадрати при діленні на 3?

Відповідь: 0; 1; (3k±1)²=9k²±6k+1.    (3k)²=9k.

Задача 5. Які остачі не можуть мати точні квадрати при діленні на 4?

(2k)²=4k²

(2k+1)²=4k²+4k+1

Відповідь: 2; 3.

Задача 6. Які остачі не можуть мати точні квадрати при діленні на 5?

Відповідь:2 і 3. (5k)²=25k²+0

(5k±1)²=25k²±10k+1

(5k±2)²=25k²±20k+4

Задача 7. Довести, що при будь-якому цілому n число n(n-3)(n²-3n+14) ділиться на 24?

Доведення:

n (n-3)(n2-n-2n+2+12)=n(n-3)(n(n-1)-2(n-1)+12=n(n-3)(n-1)(n-2)+12n(n-3). Це число ділиться на 24, бо:

1.      n(n-1)(n-2)(n-3) ділиться на 3і 8 Þділиться на 24.

2.      12n(n-3) ділиться на 12 і 2, бо n(n-3)- просте число, отже, ділиться на 24.

3.       

Властивості квадратних лишків

Теорема 1. Завжди знайдеться натуральний дільник  n, більшого 1,  для  довільного степеня натурального числа m^k, який при ділення степеня на цей дільник n дає остачу 1, (або завжди можна знайти такі  натуральні числа, що (m^k– 1):n – натуральне число).

Тобто рівняння з двома невідомими завжди має  розв’язки в натуральних числах

m^k - 1º0(mod m-1). 

Теорема 2. Завжди знайдеться натуральний дільник n, більший 5, для  довільного квадрату натурального числа, який при ділення квадрата на цей дільник дає остачу 4.

Тобто, рівняння з двома невідомими завжди має  розв’язки в натуральних числах

m² º4(mod m+2) або m² º4(mod m-2)  .

Теорема 3. Завжди знайдеться такий натуральний дільник n для  довільного квадрату натурального числа, який при ділення на цей натуральний дільник дає остачу 0.

Тобто рівняння з двома невідомими m i n завжди має  розв’язки в натуральних числах

m² º 0(mod n).

Теорема 4. Завжди знайдеться такий натуральний дільник n, більший 9,  для  довільного квадрату натурального числа, який при ділення на цей натуральний дільник n дає остачу 0.

Тобто рівняння з двома невідомими завжди має  розв’язки в натуральних числах

m² º9(mod n).

Тобто рівняння з двома невідомими m i n завжди має  розв’язки в натуральних числах

m² º9(mod m+3) або m² º9(mod m-3).

Розглянемо де­кілька прикладів.

Задача. Чи існують чотири  натуральних числа,  що йдуть підряд, кожне з яких можна подати у вигляді суми двох квадратів?

Розв'язання.

Ні, не існують. Розглянемо остачі при діленні на 4. Квадрат може дати остачу 0 або 1, сума двох квадратів - 0, 1 або 2. серед чотирьох підряд чисел знай­деться таке, що має остачу 3. Воно на суму двох квадратів не розкладається.

Задача. Знайти всі такі р, що числа р, р + 10 та р + 14 прості.

Розв'язання.

Єдина відповідь p=3. Якщо p не ділиться на 3, то при p=3k + 1 число p+14 ділиться на 3, при p=3k+2 число p+10 ділиться на 3.

Задачі для самостійного осмислення

1. Рівняння з двома невідомими

m² º 3(mod n).

 має  розв’язки в цифрах тільки один розв’язок  m = 3, n = 6.

(Умова задачі на це рівняння. Знайти двоцифрове число, у якого квадрат цифри десятків при діленні на цифру одиниць дає остачу, що дорівнює половині цифри  одиниць. Відповідь: 36.)

2. Рівняння з двома невідомими

m² º2(mod n).

 має  розв’язки в цифрах тільки два розв’язки:  m = 3, n = 7. m = 4, n = 7.

(Умова задачі на це рівняння.  Знайти двоцифрові число, у яких  квадрат цифри десятків при діленні на цифру одиниць дає остачу 2. Відповідь: 37 та 47.)

3. Чи існує магічний квадрат 3х3 , складений з натуральних чисел так, щоб виконувалася умова на парність чисел? (У магічного квадрату суми чисел по двох діагоналях, трьох вертикалях та трьох горизонталях рівні).

2n	2k-1	2r
2d-1	2t-1	2m-1
2c	2a-1	2k

Відповідь: існує, це магічний квадрат 3х3, з цифр 1, 2, 3, 4, 5, 6, 7, 8, 9.

4. Чи існує магічний квадрат 3х3, складений з натуральних чисел так, щоб виконувалася умова на парність чисел?(У магічного квадрату суми чисел по двох діагоналях, трьох вертикалях та трьох горизонталях рівні).

2n	2k-1	2r
2d-1	2t	2m-1
2c	2a-1	2k

 Відповідь: не існує.

4.Чи існує така цифра, більша 1, яка ділиться на число вигляду m² – 8. Відповідь: не існує.

5. Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу 5. Відповідь: 58, 56.

6. Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу, що дорівнює цифрі одиниць, зменшеній на 1. Відповідь: 12, 32, 52, 72, 92. 23, 53, 83, 34, 74, 45, 56, 57, 78,  29, 89, 59.

7. Знайти двоцифрові числа, у яких куб цифри десятків  при діленні на цифру одиниць, дає остачу, що дорівнює цифрі десятків. Відповідь: 12, 23, 34, 45, 56, 67, 78, 89.

8. (Теорема: m³ = m(mod m +1) та m³ = m(mod m -1), де m >1 )Доведіть, що всі двоцифрові числа, у яких цифри розташовані послідовно у порядку зростання, володіють такою властивістю: «куб цифри десятків  при діленні на цифру одиниць, дає остачу, що дорівнює цифрі десятків.»

9.   Знайти  усі двоцифрові числа, у яких куб цифри десятків  ділиться на цифру одиниць без остачі. Відповідь: 22,  42,  62,  82,  33,  44, 63,  93,  84,  64, 55,  66, 77, 88, 28, 48, 68,39, 69, 99.

10.               Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу 6, що дорівнює цифрі одиниць, зменшеній на 1. Відповідь: 57, 67.

Інваріантні величини

в задачах на перетворення об’єктів

У розв'язанні цих задач  нам допоможе те, що ми знайдемо величину, яка не змінюється при заданих операціях над об’єктом чи перетвореннях  об’єкта. Число або властивість, що не змінюється при дозволених перетвореннях, називається інваріантом. Інваріант

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

Задача 8.  На дошці написано десять плюсів та п'ятнад­цять мінусів. Дозволяється стерти будь-які два знаки та написати замість них плюс, якщо вони однакові, і мінус, якщо вони різні. Який знак лишиться на дошці після виконання двадцяти чотирьох таких операцій?

 Розв'язання. Замінимо кожен плюс числом 1, а мінус числом -1. Тоді наша операція полягає в тому, що замість двох чисел пишемо їх добуток. Добуток всіх чисел на дошці не змінюється. На початку він дорівнював -1, тому і в кінці він буде дорівнювати -1. В нас залишається мінус.

Задача 9. На дошці написані числа 1, 2, ..., 1991. Кожний раз стирається якісь два числа і замість них пишеться остача від ділення суми цих двох чисел на 13. Яке єдине число залишиться після виконання всіх цих операцій?

Розв'язання. Залишиться число 3. Інваріантна величина - остача від ділення суми всіх чисел на 13.

Задача 10. Газету розрізали на 7 шматків. Потім вибрали деякі шматки газети і їх теж розрізали на 7 шматків. І продовжили так розрізати ще  кілька разів.  Чи можна в результатів таких розрізань отримати 2017 шматків газети?

Розв'язання. Внаслідок розрізання одного шматка газети на сім частин, загальна кількість шматків газети збільшиться на 6. Це є інваріантна величина. Наприклад, внаслідок розрізання цілої газети отримали 1+ 6 шматків.  Отже, якщо ми виконаємо  n розрізань шматків газети, то в результаті отримаємо 1+6∙n шматків газети. Залишилося розв’язати в  цілих числах рівняння 1+6∙n=2017.  Отже після 336 розрізань отримаємо  2017.

Вілповідь. Можна.

+	+	–	+
+	+	+	+
+	+	+	+
+	+	+	+

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

+	+	–	+
+	+	+	+
+	+	+	+
+	+	+	+

Розв'язання.  Ні, не можна. Будемо вважати плюси числами 1, а мінуси числами -1. При наших операціях не змінюється добуток чисел в клітинках, зафарбованих на малюнку. В початковій таблиці цей добуток дорівнює -1, в таб­лиці без мінусів 1.

Відповідь. Ні, не можна.

+	+	–
–	+	+
+	–	+

Задача 12. Дано таблицю 3x3 (див. мал.). Дозволяється змінювати знак одночасно у всіх клітинках одного рядка, або одного стовп­чика. Чи можна отримати таблицю з самими плюсами?

Розв'язання.  Якщо замінити плюси на 1, а мінуси на -1, то інваріантом буде добуток чисел у чотирьох кутових клітинках.

Відоповідь. Ні, не можна.

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

Розв'язання. Неважко перевірити, що довжина границі області, яка поросла бур'яном, не може зростати. Спочатку ця довжина не перевищувала 36 (вважаємо, що сторона кожної ділянки дорівнює 1), тому вона ніколи не зможе зрівнювати 40 - периметру поля.

Зауваження. Відмітимо, що тут ми використовуємо не інваріант в його стандартному розумінні. Довжина границі області з бур'яном може змінюватися. Для нас важливо, що вона  не може зростати.

Відповідь. Не може.

Однією з таких якісних характеристик може бути парність.

Використаємо ще такі властивість парності чисел:

  2∙n + 2∙k + … + 2∙f + 2∙q = 2∙(n + k + … + f  + q) = 2∙m

СУМА БУДЬ-ЯКОЇ КІЛЬКОСТІ ПАРНИХ ЧИСЕЛ ЗАВЖДИ ПАРНА.

2∙n – 2∙k – … – 2∙f – 2∙q = 2∙(n – k – … – f  – q) = 2∙m

РІЗНИЦЯ БУДЬ-ЯКОЇ КІЛЬКОСТІ ПАРНИХ ЧИСЕЛ ЗАВЖДИ ПАРНА.

(2∙n -1)+ (2∙k-1)+ … + (2∙f-1) + (2∙q-1) = 2∙(n + k + … + f  + q)- 2s = 2∙(m-s)

СУМА ПАРНОЇ КІЛЬКОСТІ НЕПАРНИХ ЧИСЕЛ ЗАВЖДИ ПАРНА.

(2∙n -1)+ (2∙k-1)+ … + (2∙f-1) + (2∙q-1) = 2∙(n + k + … + f  + q)- 2s -1 = 2∙(m-s) - 1

СУМА НЕПАРНОЇ КІЛЬКОСТІ НЕПАРНИХ ЧИСЕЛ ЗАВЖДИ ПАРНА.

Таким чином, парність результату суми та різниці натуральних чисел не залежить від розстановки плюсів і мінусів, а залежить тільки від кількості непарних чисел в початковому наборі. Зрозуміло, що сума будь-якої кількості парних чисел є  завжди парним числом.

Задача 14. Чи можна розміняти 25 карбованців за допомогою десяти купюр вартістю 1, 3 та 5 карбованців?

 Розв’язання. Сума десяти непарних чисел завжди парна. Отже, не можна так розміняти.

Задача 15. Петро купив загальний зошит на 96 аркушів і пронумеру­вав всі його сторінки по порядку числами від 1 до 192. Василь вирвав з цього зошита 25 аркушів і додав всі 50 чисел, що на них були написані. Чи міг він дістати 1990?

 Розв’язання. На кожному аркуші сума номерів сторінок непарна, а сума 25 непарних чисел непарна.

Відповідь: ні, не могло. 

Задача 16. Добуток 22 цілих чисел дорівнює 1. Чи може статися так, що їх сума не дорівнює нулю.

Розв’язання. Серед цих чисел – парне число "мінус одиниць", а для того, щоб сума дорівнювала нулю, їх має бути рівно 11.

Задача 17. Чи можна скласти магічний квадрат з перших 36 простих чисел?

Розв’язання. Серед цих чисел одне (це 2) – парне, а інші непарні. Тому в тому рядку, де стоїть двійка, сума чисел непарна, а в інших — парна.

Відповідь: ні, не можна.

Задача 18. В ряд записано числа від 1 до 10. Чи можна розставити між ними знаки "+" та "–" так, щоб значення отриманого виразу дорівнювало нулю?

Розв’язання. І справді, сума чисел від 1 до 10 дорівнює 55, і змінюючи в неї знаки, ми змінюємо весь вираз на парне число. Адже парність результату суми та різниці натуральних чисел не залежить від розстановки плюсів і мінусів, а залежить тільки від кількості непарних чисел в початковому наборі.

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

Відповідь: Ні, не можна.

Задача 19. Коник-стрибунець стрибає вздовж прямої, причому пер­шого разу він стрибнув на 1 см в якийсь бік, другого – на 2 см і так далі. Доведіть, що після 1985 стрибків він не може зупинитися там, де починав.

Вказівка. Доводиться так само, як і в задачі 18, бо сума 1 + 2 + … + 1985 непарна.

Задача 20. На дошці виписано числа 1,2,3,..., 1984,1985. Дозволя­ється стерти з дошки будь-які два числа і замість них записати модуль їх різниці. Врешті-решт на дошці залишається одне число. Чи може воно дорівнювати нулю?

Розв’язання.  Перевірте, що при зазначених операціях парність суми всіх написаних на дошці чисел не змінюється. Адже парність результату суми та різниці натуральних чисел не залежить від розстановки плюсів і мінусів, а залежить тільки від кількості непарних чисел в початковому наборі.

Відповідь: ні, не може.

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

Задача 21. Чи можна покрити шахматну дошку доміношками розмі­ром 1x2 так, щоб вільними залишились тільки клітинки а1 і, h8?

Розв’язання. Кожна доміношка покриває одне чорне і одне біле поле, а при викиданні полів а1 і h8 чорних полів залишається на 2 менше, ніж білих.

Відповідь: не можна.

Задача 22. До 17-цифрового числа додали число, яке записано тими ж цифрами, але в зворотному порядку. Доведіть, що хоча б одна цифра суми, що отримана, є парною.

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

Задача 23. В народній дружині є 100 чоловік, і кожного вечора троє з них йдуть чергувати.   Чи може після деякого часу виявитися, що кожен чергував з кожним рівно один раз?

Розв’язання. У   кожному чергуванні, в якому бере участь дана людина, вона чергує з двома іншими, отже, всіх інших можна розбити на пари. Проте 99 — непарне число.

Відповідь: ні, не може.

Задача 24 .  На прямій відмічено 45 точок, що лежать зовні відрізка АВ. Доведіть, що сума відстаней від цих точок до точки А не дорівнює сумі відстаней від цих точок до точки В.

Вказівка. Зрозуміло, що комбінація з дев'яти одиниць раніше, ніж з дев'яти нулів, утворитися не може.   Якщо ж утворилося дев'ять нулів,   то в попередньому ході нулі і одиниці повинні були чергуватися,    не можливо, бо їх всього непарна кількість.

Задача 25. По колу розставлено 9 чисел – 4 одиниці і 5 нулів. Кожну секунду над числами роблять таку операцію: між сусідніми числами ставлять нуль, якщо вони різні, та одиницю, якщо вони рівні. Чи можуть усі числа через деякий час стати рівними?

Вказівка. Зрозуміло, що комбінація з дев'яти одиниць раніше, ніж з дев'яти нулів, утворитися не може.   Якщо ж утворилося дев'ять нулів,   то в попередньому ході нулі і одиниці повинні були чергуватися,  не можливо, бо їх всього непарна кількість.

Задача 26. 25 хлопчиків і 25 дівчаток сидять за круглим столом. До­ведіть, що у когось із сидячих обидва сусіди – хлопці.

Доведення. Зрозуміло, у противному випадку, різниця між кількістю хлопців та дівчат повинна дорівнювати непарному числу, що не відповідає умові задачі. Тому проведемо наше доведення від супротивного. Пронумеруємо всіх, що сидять за столом, по порядку, починаючи з якогось місця. Якщо на к-му місці сидить хлопчик, то ясно, що на (к - 2)-му і на (к+ 2) му місцях сидять дівчатка. Але оскільки хлопчиків і дівчаток порівно, то і для будь-якої дівчинки, що сидить на n-му місці, вірно, що на (n – 2)-му і на (n + 2)-му місцях сидять хлопчики. Якщо ми тепер розглянемо тільки тих 25 чоловік, що сидять на "парних" місцях, то одержимо, що серед них хлопчики і дівчатка чергуються, якщо обходити стіл в якомусь напрямі. Але 25 – непарне число.

Задачі, в яких для знаходження інваріантної величини для наочності використовують певні види розфарбування клітинкових фігур.

Задача 27. Чи можна шахову дошку 8х8 покрити 11 пря­мокутниками 1x4 та 5 квадратами 2x2 так, щоб їхні сторони йшли по сторонах клітинок?

Розв'язання. Використаємо діагональне  розфарбування клітинок дошки в чотири кольори, які позначимо числами 0, 1, 2 та 3. Кожний квадрат 2x2 покриває клітинки з сумою чисел 4 або 8. Кожний прямокутник 1х4 покриває клі­тинки з сумою чисел 6,  для 11 прямокутників сума чисел дорівнює 66. Тому сума чисел, покритих 5 квадратами та 11 прямокутниками у нас не може ділитися на 4. З іншого боку, для дошки 8x8 сума всіх чисел дорівнює 96. Тому дошку покрити не можна.

Задача 28. Доведіть, що прямокутниками 1х3 не можна покрити дошку 8х8, в якій з лівого нижнього кута вирізаний прямокутник 1х4.

Розв’язання. Пронумеруємо вертикалі повної дошки 8x8 цифрами від 0 до 7 та горизонталі цими ж цифрами, починаючи з лівого нижнього кута. В кожну клітину поставимо лишок від ділення на 3 суми відповідних їй горизонталі та вертикалі. Кожна фігура 1х3 покриває числа 0, 1 та 2. А сума чисел на всій дошці з вирізаним нашим прямокутником не ділиться на 3.

Задача 29.   На дошці розміром 10x10 роставлено 50 шашок:

25 у лівій нижній чверті дошки, 25-у правій верхній чверті. За один хід будь-яка шашка може перестрибнути через шашку, сусідню з нею по горизонталі, вертикалі або діагоналі на наступне поле, якщо воно вільне. Чи зможуть за кілька ходів всі шашки опинитися на одній половині дошки?

Розв'язання. Нехай клітинки дошки пофарбовані у білий та чорний колір у шаховому порядку. Тоді кожна шашка при переміщеннях не змінює кольору клітинки, на якій вона стоїть. В початковій розстановці у нас на чорних клітинках стоять 24 або 26 шашок  (в залежності від кольору лівої нижньої клітинки). А на половині дошки 25 чорних клітинок.

Відповідь. Ні, не зможуть.

Задача 30. Довести, що шахову дошку, розміром 1989x1991 з вирізаною центральною клітинкою не можна обійти турою, побувавши в кожній клітинці точно один раз.

Розв’язання. Розфарбуємо клітинки дошки у білий та чорний колір у шаховому порядку. Тоді тура по черзі проходить білі та чорні клітинки. їх у нас парна кількість, але кількість білих клітинок не перевищує кількості чорних.

Задача 31. У Змія Горинича 1000 голів. Ілля Муромець одним уда­ром меча може відрубати точно 1, 17, 21 або 33 голови, але при цьому в Змія виростає відповідно 10, 14, 0 або 48 голів. Чи зможе богатир перемогти Змія Горинича?

Розв’язання. Кожного разу кількість голів Змія змінюється на число, кратне трьом.

Відповідь. Ні, не зможе.

Задача 32. Доведіть, що шашкову дошку розміром 10X10, не можна розбити на фігурки у формі букви Т, що складається з чотирьох клітинок.

Доведення. Кожна фігурка у формі букви Т покриває 1 або 3 чорних клітинки. Нам потрібно 25 фігурок. На дошці парна кількість чорних клітинок. Отже, парне число чорних клітинок вказує на не можливість такого розбиття.

Задача 33. Якщо в нас є кілька многочленів, то дозволяється із них записати добуток, суму або різницю двох із них. Спочатку нам задано f(х) та g(х). Чи зможемо ми отримати х, якщо:

а)         f(х)=х²+х, g(х)=х²+2;

б)         f(х)=х²+х; g(х)=х²-2;

в)         f(х)-2х²+х; g(х)=2х;

г)         f(х)=2х³+х; g(х)=х².

Розв’язання. а) Ні, не зможемо. Оскільки f(-1)=0, g(-1)=3, значення в (-1) многочленів, що ми можемо отримати, ділиться на 3.

б)         Зможемо. x=(f-д)2-2(f-д)-f.

в)         Ні. При х = 0,5∙f(х), g(х) та всі многочлени, що ми

можемо отримати, приймають цілі значення.

г)         Ні.   Значення  будь-якого  отриманого  нами
многочлена в точці х-2^0,5 має вигляд m+5∙2^0,5∙n; m, n – цілі.

Задача 34. Дано 77 однакових брусків розміром 3х3х1. Чи можна їх усіх укласти в коробку з кришкою розміром 7х9х11?

Розв’язання. Розглянемо в коробці шар товщиною 1, розташований біля грані розміром 7x11. Кожен брусок займає в ньому 3 або 9 кубиків 1х1х1. Але 77 не ділиться на 3.

Відповідь. Ні, не можна.

Задача 35. "Дельфін"- фігура, що ходить на одне поле вгору, вправо або по діагоналі вліво вниз. Чи зможе "дельфін" обійти дошку 8x8, починаючи з лівого нижнього кута і побувавши в кожній клітині один раз?

Розв’язання. Розставимо числа 0, 1, та 2 в клітинках дошки так, як при розв'язанні вправи 9.4. Тоді "дельфін" по черзі буде проходити числа 0, 1, 2, 0, 1, 2, ... Але в нас на дошці кількість одиниць не дорівнює кількості двійок.

Відповідь. Ні, не можна.

Задача 36. Нескінченна послідовність цифр починається цифрами 1,0, 1,0, 1,0. Далі кожна цифра - це остання цифра суми шістьох попередніх. Чи зустрінуться колись в цій послідовності підряд цифри 0, 1, 0, 1, 0, 1?

Розв’язання. Інваріантом буде остання цифра числа 2х₁+4х₂+6х₃+8х₄ + 10х₅ + 12х₆, де х₁,… , х₆, шість цифр, що йдуть підряд.

Відповідь. Ні, не зустрінуться.

Задача 37. На площині задано правильний шестикутник. Кожна його сторона поділена на 1000 рівних частин, і точки поділу з'єднані відрізками, паралельними сторонам шестикутника. В утвореній сітці оберемо три вузла, що є вершинами правильного трикутника (будь-якого розміру та розташування), і пофарбуємо їх. Продовжуємо такий вибір та фарбування, поки це можливо. Доведіть, що якщо залишиться непофарбованим один вузол, то він не є вершиною початкового шестикутника.

Доведення.  Розставимо  у вузлах    сітки числа  0,   1,   2,
так,  щоб:  а)  у вершинах будь-якого маленького трикутника стояли всі три числа; б) у вершинах  шести­кутника стояли 0 та 1 (див.  мал. ).  Розставляти числа треба симетрично відносно осей симетрії шестикутника, що проходять через вершини. Тоді сума чисел у вершинах будь-якого правильного трикутника ділиться на 3, а сума всіх розставлених чисел при діленні на 3 дає остачу 2.

Задача 38. Для числа 1997¹⁹⁹⁷ підрахували суму його цифр. В одержаному числі знову підрахували суму цифр, і т.д. аж поки не одержали одноцифрове число. Визначити це останнє число.

Розв 'язання. При діленні на 9 число 1997 дає остачу 8. Тому остача від ділення на 9 числа 1997¹⁹⁹⁷ така ж, як і числа 8¹⁹⁹⁷. Але числа 8ⁿ при діленні на 9 дають таку послідовність остач: 8, 1, 8, 1, 8, ..., елементи якої повторюються з періодом 2. Тому число 8¹⁹⁹⁷, а з ним і число 1997¹⁹⁹⁷, при діленні на 9 дає остачу 8. Оскільки, крім того, остача від ділення на 9 довільного числа на суми цифр цього числа однакові, то скільки разів не застосовувати описану в умові задачі операцію, кожного разу одержуватимемо числа, які при діленні на 9 дають остачу 8. А тому одноцифрове число, яке дістаємо на останньому етапі, дорівнюватиме 8.

Комбінаторні обчислення значною

мірою базуються на міркуваннях, пов'язаних з інваріантами.

Задача 39. План міста має схему, зображену на мал. На всіх вулицях введено односторонній рух: можна їхати (див.план) тільки вправо, або тільки вгору. Скільки є різних маршрутів, які ведуть із т.А в т.В? (Один із таких маршрутів показано на плані).

А
				В

Розв 'язання. Назвемо вулицею відрізок зображеної сітки, який з'єднує два сусідні вузли. Для того, щоб попасти в т.В, очевидно, необхідно проїхати 5  "вертикальних" та 7  "горизонтальних вулиць".

            Отже,  кожний такий  маршрут складається із   12

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

вибрати 5 етапів із 12 етапів для руху в цьому напрямку.   Отже, всього дістаємо комбінацію 5 із 12 різних маршрутів, тобто 8∙9∙11=792.

Задача 40. Задано числа 2^0,5 , 2,  1/2^0,5  . Дозволяється будь-які два з них

замінити їх сумою та різницею, поділеною на 2^0,5. Чи можна, провівши цю операцію декілька разів, дістати трійку 1, 2^0,5,1+2^0,5?

Розв 'язання. Припустимо, що на якомусь кроці ми дістали трійку чисел а, b, с. Тоді після виконання наступних перетворень дістанемо трійку (а+b)/ 2^0,5, (а-b)/ 2^0,5, с. Оскільки

((а+b)/2^0,5)² + ( (а-b)/ 2^0,5)² + с² = а² + b² + с²,

то сума квадратів  заданих чисел є інваріантом для таких перетворень. Але (2^0,5)² + 2² +(1 + 2^0,5)² ¹(2^0,5)² + 2² +(1 / 2^0,5)².

Тому із трійки 2^0,5 , 2,  1/2^0,5  трійку 1, 2^0,5, 1+2^0,5дістати не вдається.

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

Задача 41. Для участі в розиграші кубка країни з футболу подало заявки 1997 команд. Як скласти календар зустрічей між ними, щоб для визначення володаря кубка провести найменшу кількість ігор? (Між собою команди зустрічаються по одному разу. Нічиїх не буває. Команда, що програла, вибуває із змагань).

Розв 'язання. Для визначення володаря кубка необхідно, щоб із розиграшу вибули 1996 команд. Тому, як не складай календар зустрічей, для виявлення переможця доведеться провести 1996 (інваріант!) ігор.

Задача 42. В першості країни бере участь 16 команд. Кожна команда має свій стадіон і повинна зіграти з усіма своїми суперниками, в кожному із 15 турів відбувається одночасно всі 8 матчів. Чи можна скласти календар зустрічей так, щоб усі команди почергово проводили ігри вдома та на виїзді.

Розв 'язання. Виділимо дві команди, які розпочинали чемпіонат іграми вдома, тоді ці команди, проводячи почергово ігри вдома та на виїзді, в жодному з турів не змогли б зустрітися між собою. Отже, такий календар скласти не можна.

Задача 43.  Встановити, скінченною чи нескінченною є множина чисел, які є точними квадратами, мають суму цифр 9 і не закінчуються нулем.

Розв'язання.  Шуканими є, наприклад, числа вигляду (10^к + 2)² та (2 ∙ 10^к + 1)², де к - довільне натуральне число, тому така множина нескінченна. В даному випадку інваріантом є форма запису чисел із шуканої множини.

При обчисленні сум інваріанти можна одержати шляхом групування додатків.

Задача 44. Обчислити суму усіх натуральних чисел від 1 до 1996 включно.

Розв 'язання. Згрупуємо доданки на пари 1 + 1996,  2 + 1995, 998 + 999. В кожній парі сума чисел дорівнює 1997 (інваріант). Оскільки таких пар є 998, то шукана сума дорівнює 1997∙ 998 = 1993006.

Звернемо увагу на те, що при сумування непарної кількості доданків буває зручно добавити ще один нульовий доданок. Таким способом для обчислення суми натуральних чисел від 1 до 1997 дістанемо 999 пар: 0 + 1997,1 + 1996, ..., 998 + 999. Звідси находимо суму 1997 х 999 = 1995003.

Теорема про остачі

Відмітимо спочатку, що для будь-яких натуральних чисел а і b послідовності а, а², а³, а⁴, ..., аⁿ, ... остачі від ділення цих чисел на b будуть періодично повторюватись, починаючи з деякого місця. Адже за принципом Діріхле в нескінченній послідовності остач, які дають числа аⁿ при діленні на b, обов'язково знайдуться дві однакові остачі. А якщо а^k  та a^s дають однакові остачі, то однаковими будуть остачі чисел а^k+1 та а^s+1, а^k+2 та а^s+2 і т.д. І якщо ми знайдемо закон періодичності остач в послідовності а, а², а³, а⁴, ..., аⁿ, ... , то легко зможемо вказати остачу для будь-якого числа аⁿ.

Якщо остача від ділення числа а на b дорівнює с,  то остача від ділення числа аⁿ на b дорівнює остачі від ділення числа сⁿ на b.

Приклад 1. 13 : 5 = 2 (ост. 3), тоді 13ⁿ :5 дає таку саму остачу, як і 3ⁿ: 5.

Розв'язання.

1) n = 2, 13²:5 = 169:5 = 33 (ост. 4) і  3²:5 = 9:5 = 1 (ост. 4);

2) n = 3, 13³:5 = 2197:5 = 439 (ост. 2) і 3³:5 = 27:5 = 5 (ост. 2);

3) n = 4, 13⁴:5 = 28 561:5 = 5712 (ост. 1) і 3⁴:5 = 81:5 = 16(ост. 1);

4) n = 5, 13⁵:5 = 371 293:5 = 74 258 (ост. 3) і 3⁵:5 = 243:5 = 48 (ост. 3).

Приклад 2. Знайти остачу від ділення числа 2222ⁿ на 7.

Розв'язання.

1)         Знайдемо остачу від ділення 2222 на 7:  2222 : 7 = 317 (ост. 3).

2)         Остача від ділення 2222ⁿ на 7 така сама, як остача від ділення 3⁴ на 7, тобто 4, бо

3⁴:7 = 81:7 = 11 (ост. 4).

 Відповідь. 4.

Задача 1. Знайти остачу від ділення числа 2222⁵⁵⁵⁵  на 7.

Розв'язання.

1) Знайдемо остачу від ділення 2222 на 7: 2222 : 7 = 317 (ост. 3).

Остача від ділення 22225555 на 7 така сама, як остача від ділення 35555 на 7.

Знайдемо остачі від ділення 3n на 7 для різних значень n:

n=1, 3¹:7 = 3:7 = 0 (ост. 3);

n = 2, 3²:7 = 9:7 = 1 (ост. 2);

n = 3, 3³:7 = 27:7 = 3 (ост. 6);

n = 4, 3⁴:7 = 81:7 = 11 (ост. 4);

n = 5, 3⁵:7 = 243:7 = 34 (ост. 5);

n = 6, 3⁶:7 = 729:7 = 104 (ост. 1);

 n = 7, 3⁷:7 = 2187:7 = 312 (ост. 3).

Цикл дорівнює 6.

4)         Знайдемо кількість повних циклів у числі 5555.   5555 : 6 = 925 (ост. 5).

925 повних циклів відкидаємо.

Отже, ос­тача відділення 3⁵⁵⁵⁵ на 7 така сама, як від ділення 3⁵ на 7, тобто 5.

Отже, і остача від ділення 2222⁵⁵⁵⁵ на 7 до­рівнює 5.

Відповідь. 5.

Задача 2. Знайти остачу від ділення числа 5555²²²² на 7.

Розв'язання.

1) Знайдемо остачу від ділення 5555 на 7:

5555 : 7 = 793 (ост. 4).

Остача від ділення 5555²²²² на 7 така сама, як остача від ділення 4²²²² на 7.

Знайдемо остачі від ділення 4ⁿ на 7 для різних значень n:

n = 1, 4¹:7 = 4:7 = 0 (ост. 4);

n = 2, 4²:7 = 16:7 = 2 (ост. 2);

n = 3, 4³:7 = 64:7 = 9 (ост.1);

n = 4, 4⁴:7 = 256:7 = 36 (ост. 4).

Цикл дорівнює 3.

2)         Знайдемо кількість повних циклів у числі 2222.

2222 : 3 = 740 (ост. 2).

740 повних циклів відкидаємо.

Отже, ос­тача від ділення 4²²²² на 7 така сама, як і від ділення 4² на 7, тобто 2.

Отже, і остача відділення 5555²²²² на 7 до­рівнює 2.

Відповідь. 2.

Задача 3. Довести, що (2222⁵⁵⁵⁵+5555²²²²) ділиться  на 7 без остачі.

Доведення.

Оскільки 2222⁵⁵⁵⁵ при діленні на 7 дає оста­чу 5, а 5555²²²² при діленні на 7 дає остачу 2, а сума цих остач 5+2 = 7 ділиться на 7, то (2222⁵⁵⁵⁵ +5555²²²²) ділиться на 7 без остачі, що і треба було довести.

Задача 4. Знайти остачу від ділення числа 7 ²⁰⁰³ на 10.

Розв'язання.

1) Знайдемо остачу від ділення 7 на 10: 7: 10 = 0 (ост. 7).

2)Знайдемо остачі від ділення 7ⁿ  на 10 для різних значень n:

n = 1, 7¹:10 = 7:10 = 0 (ост. 7);

n = 2, 7²:10 = 49:10 = 4 (ост. 9);

n = 3, 7³:10 = 343:10 = 34 (ост. 3);

n = 4, 7⁴:10 = 2401:10 = 240(ост. 1);

n = 5, 7⁵ : 10 = 16 807:10 = 1680 (ост. 7).

Цикл дорівнює 4.

3)Знайдемо кількість повних циклів у числі 2003.

2003 : 4 = 500 (ост. 3).

4)500 повних циклів відкидаємо. Отже, ос­тача від ділення 7²⁰⁰³ на 10 така сама, як остача від ділення 73 на 10 , тобто 3.

Відповідь. 3.

5. Якою цифрою закінчується число 7²⁰⁰³ ?

Розв'язання. 

Остача відділення числа 7²⁰⁰³ на 10 є остан­ньою цифрою цього числа. Тобто число 7²⁰⁰³ закінчується цифрою 3.

Відповідь. 3.

Самостійно виконайте дві наступні вправи.

6.Знайти остачу від ділення числа 2006²⁰⁰⁷ на 3.

7. Якою цифрою закінчується 19²⁰⁰⁸ ?

Інваріантні величини

в задачах на перетворення об’єктів

У розв'язанні цих задач  нам допоможе те, що ми знайдемо величину, яка не змінюється при заданих операціях над об’єктом чи перетвореннях  об’єкта. Число або властивість, що не змінюється при дозволених перетвореннях, називається інваріантом. Інваріант

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

Задача 8.  На дошці написано десять плюсів та п'ятнад­цять мінусів. Дозволяється стерти будь-які два знаки та написати замість них плюс, якщо вони однакові, і мінус, якщо вони різні. Який знак лишиться на дошці після виконання двадцяти чотирьох таких операцій?

 Розв'язання. Замінимо кожен плюс числом 1, а мінус числом -1. Тоді наша операція полягає в тому, що замість двох чисел пишемо їх добуток. Добуток всіх чисел на дошці не змінюється. На початку він дорівнював -1, тому і в кінці він буде дорівнювати -1. В нас залишається мінус.

Задача 9. На дошці написані числа 1, 2, ..., 1991. Кожний раз стирається якісь два числа і замість них пишеться остача від ділення суми цих двох чисел на 13. Яке єдине число залишиться після виконання всіх цих операцій?

Розв'язання. Залишиться число 3. Інваріантна величина - остача від ділення суми всіх чисел на 13.

Задача 10. Газету розрізали на 7 шматків. Потім вибрали деякі шматки газети і їх теж розрізали на 7 шматків. І продовжили так розрізати ще  кілька разів.  Чи можна в результатів таких розрізань отримати 2017 шматків газети?

Розв'язання. Внаслідок розрізання одного шматка газети на сім частин, загальна кількість шматків газети збільшиться на 6. Це є інваріантна величина. Наприклад, внаслідок розрізання цілої газети отримали 1+ 6 шматків.  Отже, якщо ми виконаємо  n розрізань шматків газети, то в результаті отримаємо 1+6∙n шматків газети. Залишилося розв’язати в  цілих числах рівняння 1+6∙n=2017.  Отже після 336 розрізань отримаємо  2017.

Вілповідь. Можна.

+	+	–	+
+	+	+	+
+	+	+	+
+	+	+	+

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

+	+	–	+
+	+	+	+
+	+	+	+
+	+	+	+

Розв'язання.  Ні, не можна. Будемо вважати плюси числами 1, а мінуси числами -1. При наших операціях не змінюється добуток чисел в клітинках, зафарбованих на малюнку. В початковій таблиці цей добуток дорівнює -1, в таб­лиці без мінусів 1.

Відповідь. Ні, не можна.

+	+	–
–	+	+
+	–	+

Задача 12. Дано таблицю 3x3 (див. мал.). Дозволяється змінювати знак одночасно у всіх клітинках одного рядка, або одного стовп­чика. Чи можна отримати таблицю з самими плюсами?

Розв'язання.  Якщо замінити плюси на 1, а мінуси на -1, то інваріантом буде добуток чисел у чотирьох кутових клітинках.

Відоповідь. Ні, не можна.

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

Розв'язання. Неважко перевірити, що довжина границі області, яка поросла бур'яном, не може зростати. Спочатку ця довжина не перевищувала 36 (вважаємо, що сторона кожної ділянки дорівнює 1), тому вона ніколи не зможе зрівнювати 40 - периметру поля.

Зауваження. Відмітимо, що тут ми використовуємо не інваріант в його стандартному розумінні. Довжина границі області з бур'яном може змінюватися. Для нас важливо, що вона  не може зростати.

Відповідь. Не може.

Однією з таких якісних характеристик може бути парність.

Використаємо ще такі властивість парності чисел:

  2∙n + 2∙k + … + 2∙f + 2∙q = 2∙(n + k + … + f  + q) = 2∙m

СУМА БУДЬ-ЯКОЇ КІЛЬКОСТІ ПАРНИХ ЧИСЕЛ ЗАВЖДИ ПАРНА.

2∙n – 2∙k – … – 2∙f – 2∙q = 2∙(n – k – … – f  – q) = 2∙m

РІЗНИЦЯ БУДЬ-ЯКОЇ КІЛЬКОСТІ ПАРНИХ ЧИСЕЛ ЗАВЖДИ ПАРНА.

(2∙n -1)+ (2∙k-1)+ … + (2∙f-1) + (2∙q-1) = 2∙(n + k + … + f  + q)- 2s = 2∙(m-s)

СУМА ПАРНОЇ КІЛЬКОСТІ НЕПАРНИХ ЧИСЕЛ ЗАВЖДИ ПАРНА.

(2∙n -1)+ (2∙k-1)+ … + (2∙f-1) + (2∙q-1) = 2∙(n + k + … + f  + q)- 2s -1 = 2∙(m-s) - 1

СУМА НЕПАРНОЇ КІЛЬКОСТІ НЕПАРНИХ ЧИСЕЛ ЗАВЖДИ ПАРНА.

Таким чином, парність результату суми та різниці натуральних чисел не залежить від розстановки плюсів і мінусів, а залежить тільки від кількості непарних чисел в початковому наборі. Зрозуміло, що сума будь-якої кількості парних чисел є  завжди парним числом.

Задача 14. Чи можна розміняти 25 карбованців за допомогою десяти купюр вартістю 1, 3 та 5 карбованців?

 Розв’язання. Сума десяти непарних чисел завжди парна. Отже, не можна так розміняти.

Задача 15. Петро купив загальний зошит на 96 аркушів і пронумеру­вав всі його сторінки по порядку числами від 1 до 192. Василь вирвав з цього зошита 25 аркушів і додав всі 50 чисел, що на них були написані. Чи міг він дістати 1990?

 Розв’язання. На кожному аркуші сума номерів сторінок непарна, а сума 25 непарних чисел непарна.

Відповідь: ні, не могло. 

Задача 16. Добуток 22 цілих чисел дорівнює 1. Чи може статися так, що їх сума не дорівнює нулю.

Розв’язання. Серед цих чисел – парне число "мінус одиниць", а для того, щоб сума дорівнювала нулю, їх має бути рівно 11.

Задача 17. Чи можна скласти магічний квадрат з перших 36 простих чисел?

Розв’язання. Серед цих чисел одне (це 2) – парне, а інші непарні. Тому в тому рядку, де стоїть двійка, сума чисел непарна, а в інших — парна.

Відповідь: ні, не можна.

Задача 18. В ряд записано числа від 1 до 10. Чи можна розставити між ними знаки "+" та "–" так, щоб значення отриманого виразу дорівнювало нулю?

Розв’язання. І справді, сума чисел від 1 до 10 дорівнює 55, і змінюючи в неї знаки, ми змінюємо весь вираз на парне число. Адже парність результату суми та різниці натуральних чисел не залежить від розстановки плюсів і мінусів, а залежить тільки від кількості непарних чисел в початковому наборі.

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

Відповідь: Ні, не можна.

Задача 19. Коник-стрибунець стрибає вздовж прямої, причому пер­шого разу він стрибнув на 1 см в якийсь бік, другого – на 2 см і так далі. Доведіть, що після 1985 стрибків він не може зупинитися там, де починав.

Вказівка. Доводиться так само, як і в задачі 18, бо сума 1 + 2 + … + 1985 непарна.

Задача 20. На дошці виписано числа 1,2,3,..., 1984,1985. Дозволя­ється стерти з дошки будь-які два числа і замість них записати модуль їх різниці. Врешті-решт на дошці залишається одне число. Чи може воно дорівнювати нулю?

Розв’язання.  Перевірте, що при зазначених операціях парність суми всіх написаних на дошці чисел не змінюється. Адже парність результату суми та різниці натуральних чисел не залежить від розстановки плюсів і мінусів, а залежить тільки від кількості непарних чисел в початковому наборі.

Відповідь: ні, не може.

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

Задача 21. Чи можна покрити шахматну дошку доміношками розмі­ром 1x2 так, щоб вільними залишились тільки клітинки а1 і, h8?

Розв’язання. Кожна доміношка покриває одне чорне і одне біле поле, а при викиданні полів а1 і h8 чорних полів залишається на 2 менше, ніж білих.

Відповідь: не можна.

Задача 22. До 17-цифрового числа додали число, яке записано тими ж цифрами, але в зворотному порядку. Доведіть, що хоча б одна цифра суми, що отримана, є парною.

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

Задача 23. В народній дружині є 100 чоловік, і кожного вечора троє з них йдуть чергувати.   Чи може після деякого часу виявитися, що кожен чергував з кожним рівно один раз?

Розв’язання. У   кожному чергуванні, в якому бере участь дана людина, вона чергує з двома іншими, отже, всіх інших можна розбити на пари. Проте 99 — непарне число.

Відповідь: ні, не може.

Задача 24 .  На прямій відмічено 45 точок, що лежать зовні відрізка АВ. Доведіть, що сума відстаней від цих точок до точки А не дорівнює сумі відстаней від цих точок до точки В.

Вказівка. Зрозуміло, що комбінація з дев'яти одиниць раніше, ніж з дев'яти нулів, утворитися не може.   Якщо ж утворилося дев'ять нулів,   то в попередньому ході нулі і одиниці повинні були чергуватися,    не можливо, бо їх всього непарна кількість.

Задача 25. По колу розставлено 9 чисел – 4 одиниці і 5 нулів. Кожну секунду над числами роблять таку операцію: між сусідніми числами ставлять нуль, якщо вони різні, та одиницю, якщо вони рівні. Чи можуть усі числа через деякий час стати рівними?

Вказівка. Зрозуміло, що комбінація з дев'яти одиниць раніше, ніж з дев'яти нулів, утворитися не може.   Якщо ж утворилося дев'ять нулів,   то в попередньому ході нулі і одиниці повинні були чергуватися,  не можливо, бо їх всього непарна кількість.

Задача 26. 25 хлопчиків і 25 дівчаток сидять за круглим столом. До­ведіть, що у когось із сидячих обидва сусіди – хлопці.

Доведення. Зрозуміло, у противному випадку, різниця між кількістю хлопців та дівчат повинна дорівнювати непарному числу, що не відповідає умові задачі. Тому проведемо наше доведення від супротивного. Пронумеруємо всіх, що сидять за столом, по порядку, починаючи з якогось місця. Якщо на к-му місці сидить хлопчик, то ясно, що на (к - 2)-му і на (к+ 2) му місцях сидять дівчатка. Але оскільки хлопчиків і дівчаток порівно, то і для будь-якої дівчинки, що сидить на n-му місці, вірно, що на (n – 2)-му і на (n + 2)-му місцях сидять хлопчики. Якщо ми тепер розглянемо тільки тих 25 чоловік, що сидять на "парних" місцях, то одержимо, що серед них хлопчики і дівчатка чергуються, якщо обходити стіл в якомусь напрямі. Але 25 – непарне число.

Задачі, в яких для знаходження інваріантної величини для наочності використовують певні види розфарбування клітинкових фігур.

Задача 27. Чи можна шахову дошку 8х8 покрити 11 пря­мокутниками 1x4 та 5 квадратами 2x2 так, щоб їхні сторони йшли по сторонах клітинок?

Розв'язання. Використаємо діагональне  розфарбування клітинок дошки в чотири кольори, які позначимо числами 0, 1, 2 та 3. Кожний квадрат 2x2 покриває клітинки з сумою чисел 4 або 8. Кожний прямокутник 1х4 покриває клі­тинки з сумою чисел 6,  для 11 прямокутників сума чисел дорівнює 66. Тому сума чисел, покритих 5 квадратами та 11 прямокутниками у нас не може ділитися на 4. З іншого боку, для дошки 8x8 сума всіх чисел дорівнює 96. Тому дошку покрити не можна.

Задача 28. Доведіть, що прямокутниками 1х3 не можна покрити дошку 8х8, в якій з лівого нижнього кута вирізаний прямокутник 1х4.

Розв’язання. Пронумеруємо вертикалі повної дошки 8x8 цифрами від 0 до 7 та горизонталі цими ж цифрами, починаючи з лівого нижнього кута. В кожну клітину поставимо лишок від ділення на 3 суми відповідних їй горизонталі та вертикалі. Кожна фігура 1х3 покриває числа 0, 1 та 2. А сума чисел на всій дошці з вирізаним нашим прямокутником не ділиться на 3.

Задача 29.   На дошці розміром 10x10 роставлено 50 шашок:

25 у лівій нижній чверті дошки, 25-у правій верхній чверті. За один хід будь-яка шашка може перестрибнути через шашку, сусідню з нею по горизонталі, вертикалі або діагоналі на наступне поле, якщо воно вільне. Чи зможуть за кілька ходів всі шашки опинитися на одній половині дошки?

Розв'язання. Нехай клітинки дошки пофарбовані у білий та чорний колір у шаховому порядку. Тоді кожна шашка при переміщеннях не змінює кольору клітинки, на якій вона стоїть. В початковій розстановці у нас на чорних клітинках стоять 24 або 26 шашок  (в залежності від кольору лівої нижньої клітинки). А на половині дошки 25 чорних клітинок.

Відповідь. Ні, не зможуть.

Задача 30. Довести, що шахову дошку, розміром 1989x1991 з вирізаною центральною клітинкою не можна обійти турою, побувавши в кожній клітинці точно один раз.

Розв’язання. Розфарбуємо клітинки дошки у білий та чорний колір у шаховому порядку. Тоді тура по черзі проходить білі та чорні клітинки. їх у нас парна кількість, але кількість білих клітинок не перевищує кількості чорних.

Задача 31. У Змія Горинича 1000 голів. Ілля Муромець одним уда­ром меча може відрубати точно 1, 17, 21 або 33 голови, але при цьому в Змія виростає відповідно 10, 14, 0 або 48 голів. Чи зможе богатир перемогти Змія Горинича?

Розв’язання. Кожного разу кількість голів Змія змінюється на число, кратне трьом.

Відповідь. Ні, не зможе.

Задача 32. Доведіть, що шашкову дошку розміром 10X10, не можна розбити на фігурки у формі букви Т, що складається з чотирьох клітинок.

Доведення. Кожна фігурка у формі букви Т покриває 1 або 3 чорних клітинки. Нам потрібно 25 фігурок. На дошці парна кількість чорних клітинок. Отже, парне число чорних клітинок вказує на не можливість такого розбиття.

Задача 33. Якщо в нас є кілька многочленів, то дозволяється із них записати добуток, суму або різницю двох із них. Спочатку нам задано f(х) та g(х). Чи зможемо ми отримати х, якщо:

а)         f(х)=х²+х, g(х)=х²+2;

б)         f(х)=х²+х; g(х)=х²-2;

в)         f(х)-2х²+х; g(х)=2х;

г)         f(х)=2х³+х; g(х)=х².

Розв’язання. а) Ні, не зможемо. Оскільки f(-1)=0, g(-1)=3, значення в (-1) многочленів, що ми можемо отримати, ділиться на 3.

б)         Зможемо. x=(f-д)2-2(f-д)-f.

в)         Ні. При х = 0,5∙f(х), g(х) та всі многочлени, що ми

можемо отримати, приймають цілі значення.

г)         Ні.   Значення  будь-якого  отриманого  нами
многочлена в точці х-2^0,5 має вигляд m+5∙2^0,5∙n; m, n – цілі.

Задача 34. Дано 77 однакових брусків розміром 3х3х1. Чи можна їх усіх укласти в коробку з кришкою розміром 7х9х11?

Розв’язання. Розглянемо в коробці шар товщиною 1, розташований біля грані розміром 7x11. Кожен брусок займає в ньому 3 або 9 кубиків 1х1х1. Але 77 не ділиться на 3.

Відповідь. Ні, не можна.

Задача 35. "Дельфін"- фігура, що ходить на одне поле вгору, вправо або по діагоналі вліво вниз. Чи зможе "дельфін" обійти дошку 8x8, починаючи з лівого нижнього кута і побувавши в кожній клітині один раз?

Розв’язання. Розставимо числа 0, 1, та 2 в клітинках дошки так, як при розв'язанні вправи 9.4. Тоді "дельфін" по черзі буде проходити числа 0, 1, 2, 0, 1, 2, ... Але в нас на дошці кількість одиниць не дорівнює кількості двійок.

Відповідь. Ні, не можна.

Задача 36. Нескінченна послідовність цифр починається цифрами 1,0, 1,0, 1,0. Далі кожна цифра - це остання цифра суми шістьох попередніх. Чи зустрінуться колись в цій послідовності підряд цифри 0, 1, 0, 1, 0, 1?

Розв’язання. Інваріантом буде остання цифра числа 2х₁+4х₂+6х₃+8х₄ + 10х₅ + 12х₆, де х₁,… , х₆, шість цифр, що йдуть підряд.

Відповідь. Ні, не зустрінуться.

Задача 37. На площині задано правильний шестикутник. Кожна його сторона поділена на 1000 рівних частин, і точки поділу з'єднані відрізками, паралельними сторонам шестикутника. В утвореній сітці оберемо три вузла, що є вершинами правильного трикутника (будь-якого розміру та розташування), і пофарбуємо їх. Продовжуємо такий вибір та фарбування, поки це можливо. Доведіть, що якщо залишиться непофарбованим один вузол, то він не є вершиною початкового шестикутника.

Доведення.  Розставимо  у вузлах    сітки числа  0,   1,   2,
так,  щоб:  а)  у вершинах будь-якого маленького трикутника стояли всі три числа; б) у вершинах  шести­кутника стояли 0 та 1 (див.  мал. ).  Розставляти числа треба симетрично відносно осей симетрії шестикутника, що проходять через вершини. Тоді сума чисел у вершинах будь-якого правильного трикутника ділиться на 3, а сума всіх розставлених чисел при діленні на 3 дає остачу 2.

Задача 38. Для числа 1997¹⁹⁹⁷ підрахували суму його цифр. В одержаному числі знову підрахували суму цифр, і т.д. аж поки не одержали одноцифрове число. Визначити це останнє число.

Розв 'язання. При діленні на 9 число 1997 дає остачу 8. Тому остача від ділення на 9 числа 1997¹⁹⁹⁷ така ж, як і числа 8¹⁹⁹⁷. Але числа 8ⁿ при діленні на 9 дають таку послідовність остач: 8, 1, 8, 1, 8, ..., елементи якої повторюються з періодом 2. Тому число 8¹⁹⁹⁷, а з ним і число 1997¹⁹⁹⁷, при діленні на 9 дає остачу 8. Оскільки, крім того, остача від ділення на 9 довільного числа на суми цифр цього числа однакові, то скільки разів не застосовувати описану в умові задачі операцію, кожного разу одержуватимемо числа, які при діленні на 9 дають остачу 8. А тому одноцифрове число, яке дістаємо на останньому етапі, дорівнюватиме 8.

Комбінаторні обчислення значною мірою базуються на міркуваннях, пов'язаних з інваріантами.

А
				В

Задача 39. План міста має схему, зображену на мал. На всіх вулицях введено односторонній рух: можна їхати (див.план) тільки вправо, або тільки вгору. Скільки є різних маршрутів, які ведуть із т.А в т.В? (Один із таких маршрутів показано на плані).

Розв 'язання. Назвемо вулицею відрізок зображеної сітки, який з'єднує два сусідні вузли. Для того, щоб попасти в т.В, очевидно, необхідно проїхати 5  "вертикальних" та 7  "горизонтальних вулиць".

            Отже,  кожний такий  маршрут складається із   12

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

вибрати 5 етапів із 12 етапів для руху в цьому напрямку.   Отже, всього дістаємо комбінацію 5 із 12 різних маршрутів, тобто 8∙9∙11=792.

Задача 40. Задано числа 2^0,5 , 2,  1/2^0,5  . Дозволяється будь-які два з них

замінити їх сумою та різницею, поділеною на 2^0,5. Чи можна, провівши цю операцію декілька разів, дістати трійку 1, 2^0,5,1+2^0,5?

Розв 'язання. Припустимо, що на якомусь кроці ми дістали трійку чисел а, b, с. Тоді після виконання наступних перетворень дістанемо трійку (а+b)/ 2^0,5, (а-b)/ 2^0,5, с. Оскільки

((а+b)/2^0,5)² + ( (а-b)/ 2^0,5)² + с² = а² + b² + с²,

то сума квадратів  заданих чисел є інваріантом для таких перетворень. Але (2^0,5)² + 2² +(1 + 2^0,5)² ¹(2^0,5)² + 2² +(1 / 2^0,5)².

Тому із трійки 2^0,5 , 2,  1/2^0,5  трійку 1, 2^0,5, 1+2^0,5дістати не вдається.

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

Задача 41. Для участі в розиграші кубка країни з футболу подало заявки 1997 команд. Як скласти календар зустрічей між ними, щоб для визначення володаря кубка провести найменшу кількість ігор? (Між собою команди зустрічаються по одному разу. Нічиїх не буває. Команда, що програла, вибуває із змагань).

Розв 'язання. Для визначення володаря кубка необхідно, щоб із розиграшу вибули 1996 команд. Тому, як не складай календар зустрічей, для виявлення переможця доведеться провести 1996 (інваріант!) ігор.

Задача 42. В першості країни бере участь 16 команд. Кожна команда має свій стадіон і повинна зіграти з усіма своїми суперниками, в кожному із 15 турів відбувається одночасно всі 8 матчів. Чи можна скласти календар зустрічей так, щоб усі команди почергово проводили ігри вдома та на виїзді.

Розв 'язання. Виділимо дві команди, які розпочинали чемпіонат іграми вдома, тоді ці команди, проводячи почергово ігри вдома та на виїзді, в жодному з турів не змогли б зустрітися між собою. Отже, такий календар скласти не можна.

Задача 43.  Встановити, скінченною чи нескінченною є множина чисел, які є точними квадратами, мають суму цифр 9 і не закінчуються нулем.

Розв'язання.  Шуканими є, наприклад, числа вигляду (10^к + 2)² та (2 ∙ 10^к + 1)², де к - довільне натуральне число, тому така множина нескінченна. В даному випадку інваріантом є форма запису чисел із шуканої множини.

При обчисленні сум інваріанти можна одержати шляхом групування додатків.

Задача 44. Обчислити суму усіх натуральних чисел від 1 до 1996 включно.

Розв 'язання. Згрупуємо доданки на пари 1 + 1996,  2 + 1995, 998 + 999. В кожній парі сума чисел дорівнює 1997 (інваріант). Оскільки таких пар є 998, то шукана сума дорівнює 1997∙ 998 = 1993006.

Звернемо увагу на те, що при сумування непарної кількості доданків буває зручно добавити ще один нульовий доданок. Таким способом для обчислення суми натуральних чисел від 1 до 1997 дістанемо 999 пар: 0 + 1997,1 + 1996, ..., 998 + 999. Звідси находимо суму 1997 х 999 = 1995003.