Завдання «Кінські біги»
Обговорення
1. Очевидно, що мінімальна кількість заїздів дорівнює N > 5, оскільки неможливо побачити кожного з 25 коней у дії менш ніж за п’ять заїздів, за умови, що в перегонах беруть участь максимум 5 коней. І гарантоване визначення першої трійки, очевидно, потребує навіть більшої кількості гонок.
2. Якщо швидший кінь завжди перемагає повільнішого, то кінь, який перемагає іншого коня, гарантовано переможе всіх тих, кого він перемагає.
3. Грунтуючись на попередньому пункті, можна з упевненістю сказати, що найкоротший спосіб визначити найкращих коней - це порівняти коней, які перемогли багатьох інших коней. Це означає, що турнір має проходити у кілька турів.
4. Не факт, що кінь В, переможений у раунді 1 конем А, програє коню С від інших п’яти коня А, що програв, у другому раунді. Адже двоє найшвидших коней можуть потрапити в перше коло.
5. Отже, порівняння коней, які програли в будь-якому з раундів, з будь-якими іншими кіньми, щоб визначити найшвидшого з усіх, у більшості випадків лише збільшить кількість перегонів. Зрештою, не знаючи найшвидшого, нам доведеться, наприклад, порівнювати кожного з тих, хто посідає друге місце, з кожним із тих, хто посідає перше місце в будь-якій іншій гонці того самого раунду.
6. З пункту No 5 випливає, що найкоротшим шляхом розв’язання задачі є розв’язання через визначення найшвидшого коня. Чого не можна досягти менш ніж за 6 гонок. П'ять кваліфікаційних змагань і шоста серія переможців. Тому N>6.
Мені здається, що тут потрібно йти від навпаки і просто прибирати найповільніших.
Я проілюструю відповідь Гідона вище, тому що я згоден з ним, але він надто затьмарив свою відповідь.
1. Проводимо 5 гонок, кожен раз з новою п'ятіркою. 2. Ми проводимо 6-й заїзд, в якому беруть участь лише переможці першогоп'ятьох.
Тепер складаємо квадратну таблицю 5х5: в перший рядок випишемо учасників 6-го заїзду зліва направо по спаданню результату: ABCDE Під кожним з них запишемо учасників перших п'яти забігів, в яких брав участь "мешканець" даного стовпця, по спаданню зверху вниз. 5>Отримуємо: ABCDE FGHIJ KLMNO PQRST UVWXY Можна уявляти, що під буквами ховаються різні числа, і в першому рядку вони розташовані за спаданням, як і в будь-якому стовпці, а з інших рядків і більше діагоналям інформації немає. Якщо писати це на аркуші паперу, то зручно розставляти знаки "більше" у відповідних місцях.
Насамперед ясно, що A — абсолютно найкращий кінь всього турніру, але з цим поки що робити нічого. Розглянемо, наприклад, кінь D. Краще за нього коня A, B, C. Значить, він не в трійці! Всі коні в її стовпці повільніше за неї. Те ж саме і для коней у стовпці E. Тобто праві два стовпці можна не розглядати. Трохи подумавши, не розглядаємо і два нижні рядки, залишаючи табличку 3х3:
ABC FGH KLM Розглянемо тепер коня H - в одному з перших 5 забігів ми дізналися, що C - швидше за неї, тоді як A і B - швидше С. Значить, H - теж не в трійці. Аналогічними міркуваннями відкинемо L та M.
ABC FG K Залишилося шість коней, з яких один — достовірно найшвидший. Проводимо сьомий забіг серед інших коней B, C, F, G, K. Дві найкращі з них, очевидно, займають, відповідно, другий і третій рядки загального рейтингу.