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

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

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

Задача 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.