Дивовижно

Дивовижно

 

У далекому 1850 році британський математик Томас Кіркман сформулював цікаву та, на перший погляд, доволі просту задачку: «15 молодих вихованок школи пансіонату щодня протягом тижня ходять на прогулянку, вишукуючись у ряди по троє. Потрібно весь час розподіляти їх так, щоб кожна школярка змогла побувати у трійці з усіма іншими не більше ніж по одному разу».

 

Ця задача дала початок цілому напрямку математики – комбінаторним схемам. А методи розв’язання задачі по розподіленню людей на групи тепер використовуються у безлічі сфер: в експериментальному дизайні, інформатиці, сільському господарстві, криптографії та ще багато де.

 

Можливо це прозвучить дивно, але загальне рішення задачі Кіркмана так і не знайшли. Тобто можна розподілити 15 школярок по троє протягом 7 днів. Або взяти будь які інші цифри, та спробувати знайти рішення. Але математики усього світу так і не склали загальної формули для усіх можливих випадків. Тобто щоб n школярок розділити на групи по k людей, і щоб t дівчат ніколи не зустрічалися двічі в одній групі.

 

Остання робота на цю тему (остання, про яку мені відомо, але я не дуже слідкую за науковими виданнями, тому може є щось новіше) належить професору математики Пітеру Ківашу і датується квітнем 2015 року. У ній використовується теорія ймовірності, щоб підрахувати приблизну кількість рішень для різних значень n, k і t.

 

Я впевнений, що ви зараз ламаєте голову, якого дива я завів розмову про задачі з комбінаторики в Теорії Гри? Прошу у вас ще трошечки терпіння, скоро все стане ясно.

 

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

 

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

За допомогою теорії коригуючих кодів було побудовано одну з базових комбінаторних схем, а саме: неповні збалансовані блоки. Ну а далі знайшли декілька уніфікованих рішень задачі Кіркмана. Одне з цих рішень отримало неочікуване втілення.

 

Я впевнений, ви вже здогадалися, що я розповідаю про Доббл. Так, ця гра є одним з уніфікованих рішень задачі Кіркмана. Понад 50 символів розділені на 55 груп по 8 малюночків. Візьміть будь-які дві картки. На них обов’язково є однаковий символ. І тільки один.

 

Для чого я це розказую? Мене справді вражає те, що така простенька гра, як Доббл, базується на передових досягненнях математики та інформатики. Мені здається, це… дивовижно. Так, «дивовижно» – найвлучніше слово.

 


Примітка: цей допис було вперше опубліковано 15 лютого 2018 року на сторінці Теорії Гри у фейсбуці.

Тримаємо вас в курсі найцікавіших та найактуальніших подій світу настільних ігор в Україні.
Розповідаємо про настільні ігри просто, весело та цікаво.