Інваріант в задачах.

Інваріант в задачах.

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

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

Числові задач, в яких інваріантом є остача від ділення на ціле число.

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

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

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

Задача 1. Чи може остача від ділення квадрата цілого числа на 5 дорівнювати 3?

Розв’язання. Спочатку прослідкуємо остачі від ділення квадрата цілого числа на 10. Квадрати натуральних чисел закінчуються цифрами: 0; 1; 4; 5; 6; 9.(колонка 2) то при їх діленні  на 5 одержуємо 0, 1 або 4. Це є інваріантна властивість квадрата цілого числа. Отже, не може остача від ділення квадрата цілого числа на 5 дорівнювати 3. Задача 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?

Розв’язання. Будь-яке натуральне число, більше двох, можна записати у такому вигляді або 3k-1,  або 3k,  або 3k+1. Піднесемо до квадрату дані вирази:  (3k±1)²=9k²±6k+1= 3∙k(3k±2)+1 та  (3k)²=9k². Отже, 0 та 1 остачі  можуть мати точні квадрати при діленні на 3. 

Відповідь: 0; 1.

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

Розв’язання. Будь-яке натуральне число можна записати у такому вигляді або 2k або 2k+1. Піднесемо до квадрату дані вирази: (2k)²=4k²,

(2k+1)²=4k²+4k+1= 4k(k+1) +1. Отже, 0 та 1 остачі  можуть мати точні квадрати при діленні на 4.  Серед чотирьох можливих остач відсутні 2 та 3.

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

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

 Розв’язання. Будь-яке натуральне число можна записати у такому вигляді або 5k-2,  або 5k-1, або 5k, або 5k+1, 5k+2. Піднесемо до квадрату дані вирази: (5k)²=25k²+0,  (5k±1)²=25k²±10k+1,  (5k±2)²=25k²±20k+4. Отже, 0, 1 та 4 остачі  можуть мати точні квадрати при діленні на 4.  Серед чотирьох можливих остач відсутні 2 та 3.

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

Задача 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, тому він ділиться на добуток 3 та 8, таким чином, все число ділиться на 24.

2.    12n(n-3) ділиться на 12 і 2, бо n(n-3)- добуток чисел різної парності, отже, один з множників обов’язково поділиться на 2. Таким чином все число ділиться на 24.

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

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

Задача 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, і змінюючи в неї знаки, ми змінюємо весь вираз на парне число.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 27. Старовинні перекази розповідають, що в Дніпрі поблизу Києва живе Жахлива Потвора, яка інколи прокидається та з'їдає всіх, хто розв'язує цю задачу, а потім спить та перетравлює свої жертви стільки років, як сума цифр року її останнього пробу­дження. Перша згадка про Жахливу Потвору датована 513 роком. Любі друзі, не хвилюйтесь! Зберіться з думками та до­ведіть, що у 2007 р. Жахлива Потвора вам не загрожує!

Розв’язання. Натуральні числа, в які пробуджується потвора обов’язково діляться на 9.  Перший рік 513 ділиться на 9 націло, отже сума цифр цього числа ділиться на 9 без остачі(інваріант для даної задачі). Усі наступні роки пробудження можна отримати за формулою 513+9n, де n – натуральне число.  Для чотирицифрового числа, кратного 9 і меншого, ніж 2007,  можливі такі випадки суми цифр числа: 9, 18, 27.  Проаналізуємо три попередні числа,  які кратні 9 та менші, ніж 2007. Це такі числа: 1998, 1989, 1980. Отже, щоб прокинутися Жахливій Потворі у 2007, йому треба прокинутися або у 1980(сума цифр 18), або у 1989(сума цифр 27),  або у 1998(сума цифр 27) роках. Проте потвора може прокинутися або у 

1980+18=1998 році, або у 1989+27=2016 році, або у 1998+27=2025 році.  Таким чином, у 2007 р. Жахлива Потвора нам не загрожує!

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