Інваріанти

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ІНВАРІАНТИ, ЇХ ВИБІР І ЗАСТОСУВАННЯ

Серед розмаїття математичних задач є такі, які можна об'єднати під рубрикою «Задачі на відображення». Їх загальна постановка формулюється так: «Є множина А елементів а,b,с_, ... довільної природи і множина X споріднених елементів х, у, z,..., а також відображення f, яке перетворює елементи множини А у подібні їм елементи. Чи мож­на, вдаючись до неодноразового перетворення елементів множини А за допомогою відображення f, одержати той чи інший елемент з мно­жини X?»

Приклади задач на відображення

1. Є набір паличок різної довжини: 4 палички довжиною 2 см, 7 паличок довжиною 3 см, 5 паличок довжиною 8 см. Чи можна з усіх паличок скласти прямокутник?

2.Було 4 аркуші паперу. Деякі з них розірвали на 4 частини, потім деякі з четвертинок знову розірвали на 4 частинки і т. д. Коли полічили загальну кількість отриманих клаптиків паперу, то виявило­ся, що їх 2000. Чи правильно полічили?

3. У лівому нижньому куті шахівниці розміром 8x8 клітинок роз­міщено у формі квадрата 3x3 дев'ять фішок. Фішку можна переставля­ти через будь-яку іншу на симетричну відносно неї вільну клітинку. Чи можна за декілька таких ходів зібрати всі фішки у формі квадрата 3x3:

а)       у верхньому лівому куті шахівниці;

б)      у верхньому правому куті шахівниці?

4.  Дано три числа: 2; 1 + 2^0,5; 1 -2^0,5;. За один хід дозволяється написати три нові числа, замінивши кожне з даних чисел півсумою двох
інших. Чи можна, виконавши цю операцію кілька разів, дістати набір
таких чисел: 1; 2+2^0,5;  2 - 2^0,5?

5. Біля кожної вершини куба написано число а. За один крок до двох чисел, розміщених на одному ребрі, додається по одиниці. Чи можна за кілька таких кроків зробити всі вісім чисел однаковими, якщо спочатку були написані числа: a) нуль та один, що розташовані у шаховому порядку у вершинах; b) розташовані від 1 до 4 у вершинах нижньої основи і від 5 до 8 у вершинах верхньої основи?

6. Над квадратним тричленом ах² +bх + с дозволяється вико­нувати такі дії: а) замінювати в ньому х на х – k; б) замінювати його на тричлен сх² + (b + 2с)х + (а + b + с).  Чи можна за допомогою таких дій із тричлена х² - 3х - 4 дістати тричлен х²- 2х - 5?

7. Комп'ютер Незнайко вміє виконувати лише одну операцію — обчислювати середнє арифметичне двох чисел однакової парності. При цьому одне з них він забуває. Спочатку було задано числа 0, 1999, 2000. Чи є у Незнайка можливість за допомогою комп'ютера одержати число 7?

8. На дошці записані одне за одним числа 7, 5, 5, 7. За ними записуємо останню цифру суми цих чисел, а перше число витираємо. Таку ж операцію виконаємо з одержаною четвіркою чисел, потім — з новою четвіркою і т. д. Чи можна в результаті таких операцій дістати на деякому кроці четвірку 1, 9, 8, 9?

У цих задачах елементами множини А_і (індекс вказує на номер задачі) є палички, А₂ — аркуші паперу, А₃ — фішки, певним чином розміщені на шахівниці, А₄ А₇, А_І  — числа, А₅ - числа, певним чином розміщені біля вершин куба, А₆ — квадратні тричлени; відображення Ф₁ полягає у складанні многокутників із заданих паличок, Ф₂ — розриванні аркуша або його частини на чотири частини, Ф₃ — переміщенні фішок на таблиці, Ф₄, Ф₅, Ф₇, Ф₈ — утворенні нових чисел, Ф₆ — утворенні нових квадратних тричленів; даними елементами з множин Х_п, п =1,...., 8, є відповідно прямокутник, кількість утворених клаптиків паперу, фішки, певним чином зібрані на таблиці, число 7, три конкретні числа, чотири конкретні числа, вісім однакових чисел, 1 квадратний тричлен.

Відповідь у цих задачах коротка — «так» або «ні». Звісно, задача 1
вважається розв'язаною, якщо відповідь обґрунтована. Для обґрунтування заперечення часто використовують інваріанти: величини, співвідношення, відповідності тощо — все те, що не змінюється у процесі виконання заданих у задачі перетворень. Якщо заданий елемент або елементи з множини X не відповідають цим величинам, не володіють  співвідношеннями, не справджують відповідності, то ці елементи не можна дістати в результаті перетворення заданих елементів множини А.
Слід застерегти, що збереження інваріантності є лише необхідною
умовою досягнення позитивного результату. Інваріанти дають підставу
тільки для негативної відповіді.     

Поняття інваріантів, їх вибір і застосування пояснимо під час розв'язування задач 1.-5.

Усіх паличок є 16, а їх загальна довжина становить 69 см. З них можна складати різні многокутники — від трикутників до шістнадцятикутників. Але периметр кожного многокутника залишається незмінним — 69 см. Периметр утворюваних многокутників і є інваріантом у цій задачі. Оскільки периметр прямокутника завжди є числом   парним, то з заданих паличок не можна скласти прямокутник.

Легко помітити, що число клаптиків паперу кожного разу збіль­шується на 3. Їх стає 7, 10, 13, 16, ..*, а остача від ділення цих чисел на 3 дорівнює 1 і залишається незмінною, тобто є інваріантом. Оскільки   2000=3*666 + 2, то 2 є остачею від ділення 2000 на 3, а отже, полічили   неправильно.

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

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

чотири останні елементи якої утворюють стартову четвірку чисел задачі.

Задачі для самостійного розв'язування  

    

1. Є 99 відрізків, довжини яких дорівнюють 1, 2, 3, ..., 99. Чи можна з них скласти: А) квадрат; б) прямокутник, якщо в побудові використані всі задані відрізки?

2.  Є металеві стрижні довжиною 1, 2, 3, ..., 198, 199. Чи можна;
використавши всі стрижні, спаяти: а) каркас куба; б) каркас прямокутного паралелепіпеда?

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

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