Словник / Інваріант
Є задачі, у яких хочеться пробувати ще і ще: переставити, перекласти, перевернути інакше. Здається, що бракує лише вдалого ходу. Але буває, що якась величина не змінюється від жодного ходу, а в кінці вона мусила б бути іншою. Тоді мети не досягти ніколи, і доводить це не тисяча невдалих спроб, а один підрахунок. Таку величину називають інваріантом.
Шар «На пальцях» приховано на всіх задачах.
Зі звичайної шахівниці 8 × 8 вирізали дві клітинки в протилежних кутах. Лишилося 62 клітинки. У вас 31 доміно, і кожне накриває рівно дві сусідні клітинки, по горизонталі або вертикалі.
Чи можна накрити всі 62 клітинки 31 доміно без накладань?
Ні, і доводить це один підрахунок, а не перебір.
Протилежні кути шахівниці одного кольору. Тож після вирізання лишилося 32 темні клітинки і лише 30 світлих. А кожне доміно, хоч як його покласти, накриває одну темну й одну світлу. Скільки б доміно ви не поклали, вільних темних завжди на 2 більше, ніж вільних світлих. Щоб накрити все, ця різниця мала б стати нулем, а вона не змінюється. Спробуйте самі.
Торкніться клітинки, потім сусідньої: ляже доміно. Торкніться доміно, щоб його прибрати.
Комп'ютер не здогадується, а шукає найбільшу кількість доміно повним алгоритмом. На дошці без протилежних кутів він теж зупиняється на 30, і дві вільні клітинки завжди темні. А на дошці без сусідніх кутів вирізано одну темну й одну світлу клітинку, різниця з самого початку нуль, і 31 доміно лягає.
На столі сім склянок, усі догори дном. За один хід треба перевернути рівно дві, будь-які. Чи вдасться поставити всі сім правильно? Оберіть дві склянки, і вони перевернуться.
Коли перевертаєте дві, кількість склянок догори дном змінюється на 2 або не змінюється зовсім: обидві з дна, обидві на дно, або одна туди, а друга назад. Тож непарне число лишається непарним, а 0 парне. Почали з 7, отже, нуля не буде. Але варто дозволити перевертати по три, і парність щоразу змінюється: інваріант зник, і мети можна досягти. Інваріант — властивість не самої задачі, а дозволених ходів.
Шар «Строго» приховано на всіх задачах.
Інваріант — це величина або властивість, яка не змінюється від жодного дозволеного ходу. Різниця між темними і світлими вільними клітинками, парність склянок догори дном, сума, остача від ділення на 3. Якщо на початку інваріант має одне значення, а в бажаному кінці мав би інше, кінця не досягти, хоч скільки пробувати.
П'ятнадцять плиток у коробці 4 × 4 і одна порожня клітинка. Хід — пересунути в порожнечу сусідню плитку. Тут усе зібрано, крім двох останніх: 15 стоїть перед 14. Здається, це найпростіша позиція з можливих: дві плитки поміняти місцями. Спробуйте.
Лічильник рахує дві речі. «Безлад» — скільки пар плиток стоять у неправильному порядку, якщо читати рядками зліва направо: більша раніше за меншу. І номер рядка порожньої клітинки. Хід уздовж рядка не змінює ні того, ні іншого. Хід угору чи вниз переносить плитку через три інші: безлад змінюється на 1 або на 3, а рядок порожнечі на 1. Разом виходить зміна на парне число, тож парність суми — інваріант. У зібраних п'ятнашках сума 0 + 4 = 4, парна. У позиції з переставленими 14 і 15 вона 1 + 4 = 5, непарна. Скільки б ви не крутили, зібрати не вийде.
Шар «Глибше» приховано на всіх задачах.
f(T(x)) = f(x) для кожного стану x і кожного дозволеного ходу T
Звідси одразу: якщо f(старт) ≠ f(ціль), жодна послідовність ходів не веде від старту до цілі. Функція f може бути числом, остачею, кольором, будь-чим, що можна порівняти.
Близький родич — монотонна величина (монотонний інваріант): вона не стоїть на місці, а щоразу зменшується. Якщо це ціле невід'ємне число, процес мусить зупинитися. Приклад — той самий безлад із п'ятнашок. Якщо в списку щоразу міняти місцями два сусідні елементи, що стоять не по порядку, безлад зменшується рівно на 1. Тож сортування обов'язково закінчиться, і ходів буде рівно стільки, скільки було пар не по порядку.
Двох кольорів вистачає для доміно. Для довших фігур беруть більше. Чи можна покласти дошку 10 × 10 смужками 1 × 4? Площа ділиться: 100 = 25 × 4. Розфарбуйте клітинки по діагоналях у чотири кольори по колу: колір клітинки — остача від ділення суми номерів рядка й стовпця на 4. Будь-яка смужка 1 × 4, лежача чи стояча, накриває по одній клітинці кожного кольору. Тож у покладеній дошці кольорів мало б бути порівну, по 25. А їх 25, 26, 25 і 24. Не вийде.
А іноді інваріант — уся історія. Теорема Гоморі: якщо з шахівниці 8 × 8 вирізати будь-яку темну і будь-яку світлу клітинку, решту завжди можна накрити 31 доміно. Тут різниця кольорів — єдина перешкода. Комп'ютер легко перевіряє всі 32 × 32 = 1024 такі пари: кожна складається.
Варіант, який дає гравцеві більше за будь-який інший його варіант, хоч би що обрали інші.
Знижка вигідна кав'ярні, хоч би що зробила сусідня, але коли знижують обидві, кожна заробляє втричі менше, ніж якби обидві тримали ціну.
Набір стратегій, у якому нікому не вигідно змінити свою, поки інші не змінюють своїх.
У дилемі в'язня обидва зраджують, хоча мовчати вигідніше обом: рівновага не означає найкращий результат.
Розв'язування гри з кінця: спершу останній хід, потім передостанній, і так до першого.
У грі-стоніжці логіка велить забрати копійки на першому ж ході, хоча, граючи довше, обидва отримали б сотні, і живі люди так майже не роблять.
Усі знають факт, усі знають, що всі знають, і так без кінця.
Два генерали можуть обмінятися тисячею підтверджень і все одно не мати спільного знання, тож жоден не наважиться атакувати першим.
Якщо предметів більше, ніж скриньок, у якійсь скриньці опиниться щонайменше два.
У Києві щонайменше троє людей мають рівно однакову кількість волосин на голові, хоча ніхто їх не рахував.