1912
Головоломка Digit Party щодня показувала гравцям максимальний можливий результат, але її творці знали незручну правду: приблизно в 5% випадків число було недосяжним. Математики Vincent Vatter з University of Florida та Robert Brignall з The Open University три роки використовували верхню оцінку, бо не мали способу швидко визначити справжній максимум. Тепер вони нарешті знайшли точний алгоритм — і заодно показали типову пастку задач оптимізації.
Правила гри прості. На полі 5×5 потрібно розмістити числа так, щоб однакові значення торкалися по горизонталі, вертикалі або діагоналі. За кожне таке сусідство нараховуються бали, після чого результат можна порівняти з теоретичним максимумом.
Проблема полягала в тому, що найкраще рішення для кожної групи однакових чисел не завжди можна реалізувати одночасно з найкращими рішеннями для всіх інших груп. Поле має лише 25 клітин, і локальні оптимуми починають заважати один одному.
Vatter порівнює це з валізою: можна окремо придумати ідеальне розміщення сорочок та костюмів, але коли їх треба скласти разом, місця раптом не вистачає. Тоді доводиться вирішувати, яку частину оптимального плану пожертвувати.
За 1096 щоденних головоломок за три роки гра показала неправильний максимум 55 разів. Середня помилка становила лише близько двох балів, найбільша — шість. За типового максимуму 150–200 балів різниця невелика, але математично це все одно означало неправильну відповідь.
На перший погляд повний перебір здавався майже неможливим: гра може видавати 13,9 мільйона різних наборів цифр.
Прорив стався, коли дослідники перестали розглядати кожен набір окремо. Вони згрупували задачі за однаковими структурами повторень і скоротили 13,9 мільйона варіантів до лише 1291 базової математичної ситуації.
У більшості з них конфлікту взагалі немає. Лише приблизно 400 випадків вимагають реального компромісу між групами чисел.
Для цих 400 задач команда обчислила всі корисні trade-offs. Наприклад, якщо неможливо одночасно ідеально зібрати четвірки та вісімки, зазвичай вигідніше пожертвувати зв’язком між четвірками, бо кожне сусідство вісімок приносить більше балів.
Після цього гра може миттєво показувати справжній maximum score для будь-якого набору.
Іронія в тому, що задача «який максимум?» тепер розв’язана, а питання «як людині найкраще грати, якщо вона бачить лише наступний хід?» — ні. Самі автори визнають, що користуються різними стратегіями й досі не знають, чия краща.
За межами гри ця історія ілюструє серйозний принцип: оптимізація окремих частин системи не гарантує оптимуму всієї системи. Та сама проблема виникає у виробничому плануванні, логістиці та розкладах.
https://phys.org/news/2026-08-high-scores-online-brain-teaser.html
