Математичні парадокси

Словник / Інваріант

Словник · інваріант

Чому тут не допоможе жодна спроба?

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

На пальцяхкартинки, аналогії, маленькі числа

Шар «На пальцях» приховано на всіх задачах.

Шахівниця без двох кутів

Зі звичайної шахівниці 8 × 8 вирізали дві клітинки в протилежних кутах. Лишилося 62 клітинки. У вас 31 доміно, і кожне накриває рівно дві сусідні клітинки, по горизонталі або вертикалі.

Чи можна накрити всі 62 клітинки 31 доміно без накладань?

Торкніться клітинки, потім сусідньої: ляже доміно. Торкніться доміно, щоб його прибрати.

Комп'ютер не здогадується, а шукає найбільшу кількість доміно повним алгоритмом. На дошці без протилежних кутів він теж зупиняється на 30, і дві вільні клітинки завжди темні. А на дошці без сусідніх кутів вирізано одну темну й одну світлу клітинку, різниця з самого початку нуль, і 31 доміно лягає.

Сім склянок

На столі сім склянок, усі догори дном. За один хід треба перевернути рівно дві, будь-які. Чи вдасться поставити всі сім правильно? Оберіть дві склянки, і вони перевернуться.

Коли перевертаєте дві, кількість склянок догори дном змінюється на 2 або не змінюється зовсім: обидві з дна, обидві на дно, або одна туди, а друга назад. Тож непарне число лишається непарним, а 0 парне. Почали з 7, отже, нуля не буде. Але варто дозволити перевертати по три, і парність щоразу змінюється: інваріант зник, і мети можна досягти. Інваріант — властивість не самої задачі, а дозволених ходів.

Строготаблиці, графіки, формули

Шар «Строго» приховано на всіх задачах.

Що таке інваріант

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

  • Почніть із ходу, а не з метиЗапишіть, що саме робить один хід: накриває дві сусідні клітинки, перевертає дві склянки, міняє місцями дві плитки. Інваріант шукають серед того, що цей хід зберігає.
  • Перші кандидатиПарність (парне чи непарне), розфарбування в два чи більше кольорів, сума чисел, остача від ділення. Найчастіше спрацьовує парність.
  • Доводить «ні», але не «так»Якщо інваріант на старті й на фініші різний, мета недосяжна. Якщо однаковий, це ще нічого не обіцяє: може існувати інший інваріант, якого ви не помітили, або просто бракувати ходів.
  • Невдалі спроби не доказСто невдач кажуть лише, що ви не знайшли розкладу. Інваріант каже, що розкладу немає. Саме тому на нього варто витратити хвилину, перш ніж пробувати вдесяте.

П'ятнашки, які не складаються

П'ятнадцять плиток у коробці 4 × 4 і одна порожня клітинка. Хід — пересунути в порожнечу сусідню плитку. Тут усе зібрано, крім двох останніх: 15 стоїть перед 14. Здається, це найпростіша позиція з можливих: дві плитки поміняти місцями. Спробуйте.

Лічильник рахує дві речі. «Безлад» — скільки пар плиток стоять у неправильному порядку, якщо читати рядками зліва направо: більша раніше за меншу. І номер рядка порожньої клітинки. Хід уздовж рядка не змінює ні того, ні іншого. Хід угору чи вниз переносить плитку через три інші: безлад змінюється на 1 або на 3, а рядок порожнечі на 1. Разом виходить зміна на парне число, тож парність суми — інваріант. У зібраних п'ятнашках сума 0 + 4 = 4, парна. У позиції з переставленими 14 і 15 вона 1 + 4 = 5, непарна. Скільки б ви не крутили, зібрати не вийде.

Де живуть інваріанти

  • Подвійний запис у бухгалтеріїКожна операція записується двічі, в дебет і кредит, тож активи завжди дорівнюють пасивам. Рівність — інваріант кожної проводки. Якщо баланс не зійшовся, десь помилка, і шукати її можна, не перевіряючи кожну цифру. Цей метод описав Лука Пачолі 1494 року в «Summa de arithmetica».
  • Кубик РубикаЯкщо розібрати кубик і зібрати деталі навмання, складеться лише кожен 12-й варіант. Повернутий на місці один кут, перевернуте одне ребро чи дві переставлені деталі ламають один із трьох інваріантів (2 × 3 × 2 = 12), і жодні повороти граней цього не виправлять.
  • ПрограмуванняІнваріант циклу — твердження, правдиве перед кожним кроком циклу. У двійковому пошуку це «шукане, якщо воно є, лежить між лівою і правою межею». Роберт Флойд (1967) і Тоні Гоар (1969) зробили такі твердження основою доведення, що програма правильна.
  • Закони збереженняЕнергія замкненої системи — інваріант усього, що в ній відбувається. Тому вічний двигун не потребує перевірки креслення: Паризька академія наук ще 1775 року вирішила не розглядати таких проєктів.
Глибшеузагальнення, теорія, історія

Шар «Глибше» приховано на всіх задачах.

Формула і монотонна величина

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 такі пари: кожна складається.

Звідки взялися ці задачі

  • ШахівницяЗадачу з вирізаними кутами поставив філософ Макс Блек у підручнику логіки «Critical Thinking» (1946). Її розбирали Соломон Голомб (1954) і Мартін Гарднер у колонці в Scientific American (1957), а Джон Маккарті 1964 року запропонував її як «твердий горіх» для програм, що шукають доведення: перебір ламається, а людина бачить кольори.
  • П'ятнашкиГоловоломку вигадав поштмейстер Нойз Чепмен із міста Канастота в штаті Нью-Йорк, і 1880 року нею захопилася вся Америка. Ще 1879 року Вільям Джонсон і Вільям Сторі в American Journal of Mathematics довели, що рівно половина розкладів не складається. Сем Лойд пізніше видавав себе за автора і обіцяв 1000 доларів тому, хто розставить 14 і 15 по місцях.
  • Симетрії і збереженняЕммі Нетер 1918 року довела, що кожен закон збереження у фізиці випливає з симетрії: енергія зберігається, бо закони не змінюються з часом, імпульс — бо вони однакові в кожній точці простору. Інваріант і симетрія виявилися двома боками однієї ідеї.

Де це трапляється

Ще в темі «Ігри та логіка»

Усі терміни →