Є 25 коней і бігова доріжка, на якій одночасно біжать щонайбільше 5. Секундоміра немає: забіг показує лише, хто прибіг першим, хто другим і так далі. Кожен кінь завжди біжить з однаковою швидкістю, і всі швидкості різні. Яка найменша кількість забігів, щоб напевно знайти трьох найшвидших коней і знати, хто з них перший, другий і третій?
Здається, досить шести: п'ять забігів по п'ять коней і забіг переможців. Але забіг переможців надійно знаходить лише найшвидшого. Другим може виявитися кінь, що програв саме йому ще у своєму забігу. Тому потрібен сьомий забіг: у ньому біжать п'ять коней, які ще можуть бути другим чи третім.
Класична задача зі співбесід програмістів: Вільям Паундстоун подає її як питання зі співбесіди в Google (2012). Перевіряють не знання формул, а вміння помітити, що саме кожен забіг уже довів, і не витратити жодного забігу на те, що й так відомо.
25 коней, пронумерованих від 1 до 25. На вигляд вони однакові, тож хто швидший, можна дізнатися лише з перегонів.
На доріжці 5 смуг, тож в одному забігу біжать щонайбільше 5 коней. Можна поставити й менше.
Секундоміра немає. Забіг повідомляє тільки порядок фінішу: хто перший, хто другий і так далі. Час забігу ні з чим не порівняєш.
Кожен кінь завжди біжить однаково швидко, не втомлюється і не хитрує. Усі 25 швидкостей різні, нічиїх не буває.
Яка найменша кількість забігів гарантує, що ви знайдете трьох найшвидших коней і їхній порядок?
«Шість: п'ять забігів по п'ятеро, а потім забіг переможців»
Обережніші, відчуваючи пастку, кажуть 10 чи 11. Насправді потрібно рівно 7. Шостий забіг знаходить найшвидшого, але порядок фінішу в ньому вгадує всю трійку лише з імовірністю 25/46, приблизно 54%. А шести забігів не вистачить за жодної стратегії.
25 коней, 5 доріжок, лише порядок фінішу. Зафіксуйте найменшу кількість забігів, яка, на вашу думку, гарантує результат.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Секундоміра немає, тож час різних забігів не порівняти. Перед кожним забігом думайте, що вже відомо напевно і хто вже точно не потрапить у трійку.
Почніть з п'яти забігів по п'ять коней і забігу переможців. Потім для кожного коня порахуйте, скільки коней точно швидші за нього: якщо три або більше, він вибуває.
Після забігу переможців найшвидший уже відомий. Хто ще може бути другим або третім? Із забігів, чиї переможці прийшли четвертим і п'ятим, точно ніхто.
Оберіть до 5 коней і натисніть «Старт». Швидкості заздалегідь не задано: їх вигадує стайня, яка бачить ваш вибір. Вона ніколи не суперечить попереднім результатам, але щоразу обирає порядок фінішу, що лишає в грі якомога більше коней. Гра закінчиться, коли з результатів однозначно випливуть перший, другий і третій.
Кожного разу коням дістаються випадкові швидкості. Спершу п'ять забігів по п'ятеро і забіг переможців. Наївна відповідь бере трійку з забігу переможців. Повна стратегія проводить ще один забіг для п'яти претендентів. Порівнюємо, хто частіше називає справжню трійку, і ділимо результати сьомого забігу на п'ять можливих сценаріїв.
Після забігу переможців підписуємо забіги літерами: A для забігу найшвидшого переможця, B для наступного і так далі; цифра означає місце у своєму забігу. Стовпчики показують, хто фінішував першим і другим у сьомому забігу, тобто хто насправді другий і третій.
Ключ у тому, щоб після кожного забігу рахувати, скільки коней точно швидші за кожного коня. Хто має трьох точно швидших, уже не потрапить у трійку, і бігати йому більше нема чого.
Кінь C2 повільніший за C1, C1 повільніший за B1, а B1 повільніший за A1. Отже, три коні точно швидші за C2, і в трійку він не потрапить. Так само вибувають увесь забіг D і E, A4, A5, B3, B4, B5 і C2–C5. Лишаються A1, A2, A3, B1, B2 і C1. A1 найшвидший: його забіг виграв забіг переможців. Тож у сьомому забігу біжать A2, A3, B1, B2 і C1, і їх рівно п'ять, саме стільки, скільки доріжок.
Другим найшвидшим може бути лише A2 або B1: усі інші претенденти мають щонайменше двох точно швидших. Обидва бігають у сьомому забігу, тож його переможець і є другим. Третій займає друге місце в цьому забігу: будь-хто з претендентів, хто фінішував після нього, повільніший, а всі коні поза забігом, крім A1, мають трьох точно швидших.
Назвемо коня непереможеним, якщо його ще ніхто не обігнав. Спочатку непереможених 25, а в кінці має лишитися один. Нехай у кожному забігу перемагає непереможений кінь, якщо такий там є, а серед них той, хто бігав найбільше. Це не суперечить жодним результатам, і тоді забіг відбирає статус щонайбільше в 4 коней. 24 / 4 = 6, тож лише щоб знайти найшвидшого, потрібно 6 забігів. А якщо їх рівно 6, у кожному біжать п'ятеро непереможених.
Тоді переможець п'ятого забігу ще непереможений і мусить бігти в шостому, тож чемпіон бігав щонайменше двічі. Коні, що прийшли другими в цих двох його забігах, програли лише йому і більше не бігали: хто з них швидший, невідомо. Тож сьомий забіг потрібен будь-якій стратегії.
Забіг переможців каже правду про трійку, лише коли три найшвидші коні опинилися в трьох різних забігах. Другий найшвидший не потрапляє в забіг найшвидшого з шансом 20/24: там лишилося 4 місця з 24. Третій не потрапляє в жоден з цих двох забігів з шансом 15/23. Разом 25/46 ≈ 54,3%, тобто майже в половині випадків шість забігів дають неправильну трійку.
У задачі про отруєне вино межу дає підрахунок варіантів, і він точний. Тут він майже нічого не каже: два забіги дають 120² = 14 400 результатів, а це більше, ніж 13 800 можливих трійок. Але забіг не вміє питати про будь-що. Він порівнює лише тих коней, що бігли разом, і на кожного з 25 коней треба витратити місце хоча б в одному забігу. Обмеження в доріжках, а не в бітах.
Результати забігів утворюють орієнтований граф без циклів: стрілка йде від швидшого коня до повільнішого. Він задає частковий порядок: про деякі пари коней відомо, хто швидший, про інші ні. Справжні швидкості є одним із лінійних порядків, сумісних з усіма стрілками.
Предки коня означають усіх, від кого до нього веде шлях стрілками, тобто всіх точно швидших. Кінь може фінішувати k-м у якомусь сумісному порядку тоді й лише тоді, коли в нього щонайбільше k − 1 предків (і не забагато нащадків). Достатньо поставити спершу всіх його предків, потім його самого. Тому в трійку ще можуть потрапити лише коні з 0, 1 або 2 предками.
Після шостого забігу в коня, що прийшов j-м у забігу з літерою номер i, рівно (i − 1) + (j − 1) предків. Клацніть кружечок, щоб побачити їх. Граф без жодного зайвого ребра, як тут, називають діаграмою Гассе.
Кінь Xij прийшов j-м у забігу, переможець якого посів i-те місце в забігу переможців. Точно швидші за нього: j − 1 сусідів по забігу та i − 1 переможців кращих забігів.
У трійку може потрапити лише кінь з не більше ніж двома предками.
Мінус A1, який уже відомий як найшвидший. П'ятеро претендентів якраз заповнюють доріжки, тож усього забігів:
Нижня межа: кожен забіг відбирає статус непереможеного щонайбільше в 4 коней, а відібрати треба в 24.
Шанс, що трійка забігу переможців правильна: три найшвидші коні в трьох різних забігах.
Стратегія не лише вкладається в межу, а й не витрачає жодного місця на доріжці марно: у кожному з семи забігів біжить по п'ять коней, і кожен із них ще міг виявитися в трійці.
Задача про коней належить до теорії вибору: як знайти найкращих, порівнюючи елементи невеликими групами. У математиці вона веде до оптимальних турнірів, у логіці до старої претензії Льюїса Керролла до тенісу, а на практиці до того, як бази даних шукають перші k рядків.
Математика
Для 25 коней найшвидшого знаходять за 6 забігів, двох найшвидших за 7 і трійку теж за 7. Те саме міркування працює для n доріжок і n² коней. Кожен забіг відбирає статус непереможеного щонайбільше в n − 1 коня, а відібрати треба в n² − 1, тож лише для першого місця потрібно (n² − 1)/(n − 1) = n + 1 забіг, і n забігів плюс забіг переможців цього досягають.
Аргумент про двох других у чемпіона дає n + 2 для другого місця, а забіг претендентів A2, A3, B1, B2, C1 вміщується на доріжку при n ≥ 5. Тож для трійки теж n + 2. Для 4 доріжок і 16 коней претендентів п'ятеро, а доріжок чотири, і так просто вже не вийде. Шукати четвертого чи п'ятого коня теж складніше: претендентів після забігу переможців k(k + 1)/2 − 1, тобто 9 для k = 4.
Якщо доріжок дві, забіг стає звичайним порівнянням. Чемпіона знаходить турнір на вибування за n − 1 матч: кожен матч вибиває одного учасника. Другим може бути лише той, кого обіграв сам чемпіон, бо всі інші програли комусь, хто не є найкращим. Чемпіон зіграв не більше ніж ⌈log₂ n⌉ матчів, тож серед його суперників ще ⌈log₂ n⌉ − 1 порівнянь.
Юзеф Шрайер описав цей метод 1932 року і вважав його найкращим, але його доведення мало прогалини. Повне доведення, що менше ніж n + ⌈log₂ n⌉ − 2 порівнянь не вистачить, дав С. С. Кислицин 1964 року. Для 25 коней на двох доріжках це 28 забігів.
Логіка
Числа на сітці означають справжню силу гравця: 1 найсильніший, і сильніший завжди перемагає. Чемпіоном завжди стає гравець 1. Але срібло дістається найсильнішому з іншої половини сітки. Справжній другий отримає його, лише якщо жеребкування поставило його в іншу половину, а це шанс 8/15 ≈ 53% для 16 гравців і 16/31 ≈ 52% для 32. Ці 16/31 Керролл обчислив сам 1882 року в листі до «St James's Gazette».
1883 року математик Чарльз Доджсон, відомий як Льюїс Керролл, видав брошуру «Lawn Tennis Tournaments» з підзаголовком про «хибність теперішнього методу» розподілу призів. Його претензія та сама, що в задачі про коней: результати турніру не доводять, хто другий. Другий забіг для тих, хто програв чемпіону, це і є наш сьомий забіг.
Практика
Наївно друге за величиною число шукають двома проходами: спершу максимум за n − 1 порівнянь, потім максимум серед решти ще за n − 2. Турнір економить майже половину, бо другий прохід іде лише серед ⌈log₂ n⌉ суперників чемпіона. Для мільйона чисел це 1 000 018 порівнянь замість 1 999 997. Перевірте кнопкою: сторінка рахує кожне порівняння.
Та сама ідея живе в спорті: в олімпійській боротьбі в утішні сутички (репешаж) за бронзу потрапляють ті, хто програв фіналістам, бо лише вони могли бути сильнішими за інших. У програмуванні дерево турніру перетворюється на купу (heap), а запит «ORDER BY … LIMIT k» PostgreSQL виконує без повного сортування: у плані EXPLAIN ANALYZE видно «Sort Method: top-N heapsort».
Чарльз Доджсон, оксфордський математик, відомий як автор «Аліси в Країні Чудес», видав брошуру «Lawn Tennis Tournaments: The True Method of Assigning Prizes with a Proof of the Fallacy of the Present Method». Він доводив, що турнір на вибування несправедливо роздає другий і третій призи.
Польський математик Юзеф Шрайер у статті в журналі «Mathesis Polska» описав, як знайти найкращого й другого гравця за n + ⌈log₂ n⌉ − 2 порівнянь, і стверджував, що швидше не можна. Його доведення виявилося неповним.
Через 32 роки С. С. Кислицин у «Сибірському математичному журналі» нарешті довів, що n + ⌈log₂ n⌉ − 2 порівнянь справді потрібно. Це один із перших точних результатів про те, скільки коштує вибір, а не повне сортування.
У третьому томі «Мистецтва програмування» (1973) Дональд Кнут присвятив вибору з найменшою кількістю порівнянь розділ 5.3.3. Історію питання він починає з есе Доджсона 1883 року про тенісні турніри, а далі розповідає про результати Шрайера і Кислицина.
1973 року Блум, Флойд, Пратт, Рівест і Тар'ян показали, як знайти медіану за лінійний час навіть у найгіршому випадку. Алгоритм ділить числа на групи по п'ять, як коней на забіги, і бере медіану медіан. Четверо з п'яти авторів згодом отримали премію Тюрінга.
Стільки існує трійок призерів з порядком серед 25 коней, а один забіг має 5! = 120 можливих результатів. Голий підрахунок варіантів обіцяє 2 забіги, бо 120² = 14 400. Справжня відповідь утричі більша, бо забіг порівнює лише тих, хто біг разом.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.