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

 

Задача 1.1. У файлі зберігаються 2003 одиниці і 232 нуля. Програма читає з файлу два довільних числа, видаляє, і записує на їх місце 0, якщо вони були рівні, і 1, якщо ні. Програма запускається багаторазово. Наприкінці у файлі залишається тільки одне число. Чому воно дорівнює, 0 або 1?

       

Розв’язання: Незважаючи на те, що варіантів дії програми дуже багато, ми можемо встановити відповідь однозначно. Що може прочитати програма за кажний окремий  запуск? Або 0 і 0 (і записати 0), або 0 і 1 (і записати 1), або 1 і 1 (і записати 0). У перших двох випадках сума всіх чисел у файлі не змінюється, в останньому - зменшується на 2. У кожному разі, парність цієї суми залишається колишньою. Початково сума була      2003 * 1 +232 * 0 = 2003 - непарна, значить, і в кінці буде непарна. Але наприкінці залишається тільки одне число - воно і дорівнює сумі всіх - тому воно непарне. А так як у файлі бувають тільки нулі й одиниці, то це 1.

​

Задача 1.2. Є три числа, які можна замінювати за такими правилами: числа a, b і c стираються і замість них записуються (a + b) / 2, (b + c) / 2 і (a + c) / 2.Можно Чи з чисел 101, 73, 125 отримати 77, 79 і 83?

Розв’язання: А давайте так, "про всяк випадок", подивимося, як міняється сума чисел. Було a + b + c, а стало ... замість них записуються (a + b) / 2 + (b + c) / 2 + (a + c) / 2 = (2a +2 b +2 c) / 2 = a + b + c - не змінилася. Тобто, як не крути, а сума трьох чисел не змінюється. Але 101 +73 +125 = 299, а 77 +79 +83 = 239 - суми вихідної та кінцевої трійки різні. Тому з однієї не можна отримати іншу.

(!) А ті, хто захоче взяти в якості інваріанта парність суми або її залишок по якомусь модулю, швидше за все, помиляться, так як початкова та кінцева суми розрізняються на 60, а дільників у 60 ох як багато.

​

Задача 1.3. Знову є три числа, які можна замінювати вже за іншими правилами: a, b і c - на ab/c, ac/b і bc/a. Чи можна з 5, 17/6 і 3/5 отримати 16/5, 9/4 та 7/6?

Розв’язання: Ну, про те, куди тут переходить сума чисел, навіть думати не хочеться. Що ще буває, крім суми? Добуток, наприклад. Перед операцією добуток  чисел - abc, а після: (ab/c) * (ac/b) * (bc/a) = a2b2c2/abc=abc - не змінилося!З начить, добуток трьох чисел залишається постійним при всіх операціях. Але на початку воно було рівним 5*(17/6)*(3/5)= 8,5, а наприкінці (16/5)*(9/4)*(7/6) = 8,4 - не рівні. Тому відповідь "не можна".

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

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

Інваріант як характеристика нечислових об'єктів. У всіх попередніх прикладах в задачі фігурували числа, від яких ми в якості інваріанта брали якусь функцію. Але, звичайно, у початковому формулюванні може не бути ніяких чисел! Що тоді робити? Звичайно, ці числа придумати.

​

Задача 1.4. У мові програмування MustDie всього дві команди, для стислості званих M і D. Через збій в компіляторі, дія програми не зміниться, якщо з неї викинути шматок коду MDDM, а також якщо в будь-яке її місце вставити шматок коду DMMDMD або MDMD. Чи можуть програми MMDMD і DMMDD виконуватися однаково?

Розв’язанная: Наше кажучи: чи існує таке рівнозначне перетворення коду, яке переводить одну програму в іншу? Ні, звичайно, і ви вже здогадалися що інваріант тільки треба придумати. В одному шматку 2 команди M 2 команди D, у другому тих і інших по 3, у третьому - знову по 2. Здається, ясно: у будь-якому вставленомк або видаленому шматку команд M і D порівну. Значить не змінюється, правильно, різниця між числом тих і інших команд. Вона буде нашим інваріантом - і дуже добре, так як в одній програмі на одну більше команд M, а в інший на одну більше команд D (значення різниці помінялося в 1 на -1).

 

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

 

(!) Різниця якихось кількостей і набір попарних різниць - теж типові інваріанти. Після суми і твори наступним справою треба перевіряти саме різниці.

 

Розв’язання: Де ж шукати інваріант? Із сумою чисел у файлі якось складно, тому що третя програма змінює її чорт знає як. В тому сенсі, що знаючи суми чисел у двох вхідних файлах ми не можемо визначити суму чисел у вихідному файлі. З різницею чисел у файлі все краще: перша програма не змінює різницю ((X+1)-(Y +1) =XY), друга -ділить її на 2 

(X/2-Y/2 = (XY) / 2) , а третя - складає різниці (XZ = (XY) + (YZ)). Що ж не змінюється при всіх цих перетвореннях - так відразу і не збагнеш ...

Поставимо ескперімент (так, математика - наука експериментальна!).

Вихідний файл (5, 19) можна пропустити тільки через першу програму і отримати файл (6, 20). З нього можна далі робити послідовність (7, 21), (8, 22) і т.д., а можна запустити другу програму і отримати файл (3, 10). З нього можна зробити послідовність (4, 11), (5, 12) ... (19, 26). Потім можна запустити третю програму на (5, 19) і (19, 26) і отримати файл (5, 26) ...

Порахуємо різниці: 5-19 = -14 = 6-20 = 7-21 = 8-22 = ...; 3-10 = -7 = 4-11 = 5-12 = ... = 19-26; 5-26 = -21. Що ж спільного у чисел -14, -7, -21? Звичайно, вони всі на 7 діляться. От нехай ця подільність і буде інваріантом.

Дійсно, коли різниця не змінюється, то й подільність збережеться; коли різниця ділиться на 2, то подільність на 7 не зникне (2 і 7 взаємно прості); а коли різниці, що діляться на 7, складаються, то сума теж ділиться на 7.Зрозуміло, що, маючи на початку файл з різницю чисел, що ділиться на 7, ми тільки такі різниці і будемо отримувати. Але різниця 1-2004 = -2003 на 7 не ділиться, і такий файл ми отримати не зможемо.

 

Вправа 1.2. Доведіть, що тут можна отримати всі ті і тільки ті файли, де перше число менше другого, а їх різниця ділиться на 7.

Глибокий сенс тут у чому: інваріант може залежати не тільки від правил, за якими проводяться перетворення, але і від початкових даних. Як тут: значення різниці за модулем 7, взагалі кажучи - не інваріант при вироблених перетвореннях. Але при конкретних початкових умовах, коли це значення з самого початку дорівнює 0 - тоді воно стає інваріантом.

Безумовно, якщо типові інваріанти (сума, добуток, різниці та їх значення за якимось,зразу помітним, модулем) не підходять, то корисно поставити експеримент: проробити кілька перетворень і пошукати деякі закономірності в тому, що при цьому буде виходити.

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

 

Задача 1.5. На дошці 3x5 всі клітини білі, а один кут чорний. За хід можна поміняти колір всіх клітин в одному рядку або стовпці. Чи можна всі клітини зробити білими?

Розв’язання: Парність числа чорних клітин на всій дошці, на жаль, змінюється дуже часто, а тому нам не допоможе. Де б знайти таку частину дошки, на якій ця парність незмінна? У нас тут в умові нерегулярність в кутку - так візьмемо 4 кута. При операції перефарбування змінює колір рівно два кути, або жоден - тобто парність числа чорних кутів - інваріант. Але на початку такий кут один, а наприкінці хочеться нуль - не можна.

​

Задача 1.6. На колі стоїть 12 точок, в одній написано -1, в інших +1. Можна змінити знак у трьох одиниць підряд. Чи можна здвинути єдину -1 до сусідньої вершину?

Розв’язання: Нехай, для визначеності, ми зрушили -1 до сусідньої проти годинникової стрілки вершину (інакше можна всю картинку дзеркально відобразити і отримати саме таку). Давайте занумеруем вершини, починаючи з вихідної -1, вже за годинниковою стрілкою (тоді те місце, куди зрушила -1 - це вершина 12). Давайте виділимо таку частину (безліч вершин), де є перша вершина, немає 12-й, а парність кількості-1 - інваріант (тоді ця кількість в даній частині треба буде змінити з 1 до 0, а це неможливо з- за парності).

 

Інваріант і розмальовки дощок у клітинку. Дуже важливий клас задач на інваріант - якісь перетворення на кліткових дошках. Або ми ходимо чим-небудь по дошці, або заставляємо дошку фігурами. У будь-якому разі, дуже корисною може бути розмальовка дошки в два або більше кольорів, що володіє якимись особливими властивостями. Найбільш поширені розмальовки:

- Шахова (два кольори чергуються так, що будь-які дві сусідні по стороні клітини - різних кольорів);

- "матрас" (чередування строк, викрашенних у два кольори - або стовбців);

- "Матрац" (чергування рядків, пофарбованих у два кольори - або стовпців);

- Збільшена шахова (у шаховому порядку фарбуються не окремі клітини, а цілі блоки 2x2, 3x3 і т.д.);

- Збільшений"матрац" (чергуються не рядки, а однакові по товщині блоки з рядків);

- "Матрац" в N кольорів: чергуються рядки, пофарбовані у кольори, 1-й, 2-й, ... N-й, 1-й, 2-й і т.д.

- Шахова в N кольорів - легше показати, ніж написати; приклад для 3-х кольорів; можна і по-іншому, щоб одноколірні діагоналі були нахилені в інший бік.

 

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

​

Задача 1.7. Доведіть, що шахову дошку не можна замостити 15-тима прямокутничками 1x4 і однієї фігуркою виду  .

Розв’язання: Шахова розмальовка тут не допоможе. Вона, так скажемо, не відрізняє особливу фігурку від прямокутничка: і в ній і в них рівно 2 білих і 2 чорних клітини. І ніщо не суперечить тому, що дошку можна замостити 16-ю фігурами з такою властивістю. Спробуємо іншу розмальовку, скажімо, "матрац". Тоді в прямокутнички 1x4 чи то 0, то 2, чи то 4 чорні клітини (дивлячись як він лежить). А в особливій фігурці - чи то 1, чи то 3. Коротше, там-парне, тут - непарне. А сума 15 парних чисел і одного непарного непарна і не може тому бути дорівнює 32 (числу чорних клітин на шаховій дошці).

Власне, інваріантом тут можна назвати парність кількості чорних клітин. Тільки ми тут не перетворимо об'єкт або набір об'єктів, а складаємо один об'єкт (дошку) з інших.

​

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

Розв'язання : Підберемо розмальовку, при якій фішка буде однаково міняти колір при будь-якому ході. Просто шахова і "матрац" не підійдуть. А зате шахова розмальовка в 3 кольори - просто чудово Наша фішка буде ходити з червоного на жовтий, з жовтого на зелений, з зеленого на червоний і т.д. Нехай, скажімо, початкова клітина червона - тоді кінцева буде жовта. Кольори чергуються по циклу довжини 3, тому число ходів: 3k +1 (тобто = 1 по mod 3). Але те ж число ходів на дошці NxN одно N2 -1. Звідси N 2 = 2 (mod 3), чого, з міркувань теорії чисел не буває. Відповідь "не можна".

(!) Інваріант інваріантом, але і про інші галузі математики по ходу справи не треба забувати. Часто рішення може прийти саме звідти.

Треба акуратно підходите до завдань про різні процеси з питанням "чи можна". Так, більша частина з них - з відповіддю "не можна", який доводиться через інваріант. Але трапляються іноді завдання з відповіддю "можна", де треба будувати приклад. Іноді, захопившись пошуком інваріанта, можна не помітити існування простого прикладу.