Элементарная задачка

Добрый день.

В прошлой заметке была сформулирована математическая задача из одного давнего Турнира Городов о выборе таких четырёх карт из пяти, чтобы только их порядком можно было точно указать на пятую (для колод из 52 и 53 карт). А во второй половине этой заметки я объясню, почему расширение этой задачки является элементарным.

Классическим решением задачи с 52 картами, к которому многие приходят сами, является следующее:

0. Можно отсортировать все карты (договориться, что 2 < 3, пики < крести и т.д.). Этот порядок нам пригодится, чтобы уметь отсортировать любой набор карт (и потом строить любые перестановки этого набора).

1. Из пяти карт хотя бы две имеют одинаковую масть. Поэтому загадывать надо именно одну из них. Соответственно, первая в нашей четвёрке карт прямо укажет на масть загаданной карты.

2. Оставшиеся три карты можно расположить 3! = 6 разными способами. И нам этого хватает, чтобы закодировать достоинство пятой карты, поскольку на первом шаге из двух карт одинаковой масти мы выбрали не случайную, а ту, от которой до второй карты будет от 1 до 6 шагов (представьте себе круг из карт 2, 3, 4, 5, 6, 7, 8, 9, 10, В, Д, К, Т).

Соответственно, компьютер, посмотрев на первую карту в переданном ему наборе, выясняет не только масть загаданной карты, но и номер, к которому надо прибавить число от 1 до 6, чтобы узнать достоинство искомой карты. А сам этот номер вычисляется мгновенно, так как совпадает с номером перестановки второй, третьей и четвёртой карты.

С джокером (т.е. с набором из 53 карт) ситуация чуть-чуть усложняется:
- Естественно, если среди пяти карт джокера нет, то можно действовать так, как только что договорились,
- Если среди пяти карт джокер есть, то загадывать его нельзя, так как оставшийся набор из четырёх карт будет указывать на какую-то «обычную» карту (не джокера),
- Поэтому надо научиться кодировать любую загаданную карту набором из джокера и трёх «обычных» карт.

Итак, у нас есть четыре карты, которые можно переставить 4! = 24 способами. А описать этой перестановкой мы должны одну из 49 карт (53 в колоде минус 4 переданных). Как это сделать? Есть масса способов. Но нам должно быть лениво придумывать новое, если и предыдущее решение сработает (кстати, ниже я покажу, что можно было поступить ещё ленивее):

0. На картах задан порядок, поэтому мы их можем перенумеровать от 1 до 52 (джокера сейчас не считаем),

1. В наборе из четырёх карт с номерами от 1 до 52 всегда найдутся две карты, номера которых имеют одинаковый остаток при делении на 3 (это тот же принцип Дирихле, которым мы пользовались выше для четырёх мастей и пяти карт). Соответственно, давайте одну из этих карт называть картой T (и ставить её первой среди «обычных» карт). Это позволит нам точно указать, какой остаток при делении на 3 даёт номер загаданной карты.

2. Пусть J — джокер, T — карта, указывающая остаток при делении на 3, а A и B — две другие карты. Пересчитаем возможные перестановки:
  1) JTAB,
  2) JTBA,
  3) TJAB,
  4) TJBA,
  5) TAJB,
  6) TBJA,
  7) TABJ,
  8) TBAJ.
Получается, что мы можем передать сдвиг от 1 до 8. Но легко понять, что большего нам и не требуется, так как максимальное расстояние между двумя числами от 1 до 49, имеющих одинаковые остатки при делении на три, не превышает 8 (на множестве этих чисел, конечно).

Да, это решение сработает, но оно какое-то вычурное и неинтересное (благо, всё получилось без особых затрат времени и сил). Вот мы и подошли к ответу на вопрос, почему эту задачку можно назвать элементарной.

Как надо переформулировать задачу, чтобы её было решать просто и приятно?

Из набора чисел от 1 до N каким-то способом выбирают 5 чисел. Необходимо придумать способ закодировать одно из них порядком оставшихся четырёх чисел. Найти максимальное N, при котором это возможно.

Давайте оценим теоретический предел, выше которого N точно не поднимется. Нам на вход дают множество из пяти карт, а мы в ответ должны вернуть загаданную карту X и ещё четыре карты в определённом порядке. Давайте посчитаем, сколькими способами мы можем это сделать:
- загадать карту можем пятью способами (выбрать одну из пяти возможных),
- оставшиеся четыре переставить можно только 4! = 24 способами.
Итого: 5*24 = 120 — это количество разных состояний, которые мы можем вернуть.

А какую информацию надо сообщить? Требуется указать на одну из оставшихся N-4 карт. Т.е. надо передать одно из N-4 состояний.

Выходит, что если N больше 124, то фокус принципиально невозможно исполнить, потому что закодировать мы можем только одно из 120 состояний, а передать требуется одно из N-4 состояний. Так мы поняли, что N не может быть больше 124.

Эта задача является элементарной, потому что получив эту верхнюю оценку, мы можем спокойно идти искать способ кодирования. Да, он есть. И он не очень сложный. Почти все трюки были показаны выше (когда мы играли с делимостью), поэтому теперь каждый может найти решение для 124 карт.

Эту задачу можно было бы смело назвать сложной, если бы не существовало способа кодирования для 124 карт, но был бы какой-нибудь способ для, например, 117 карт (так как тогда стояла бы большая проблема доказать, что для 118 карт никакого способа не существует). Но у нас всё просто — верхняя граница достижима, способ для 124 карт есть, поэтому достаточно всего лишь его предъявить :)
Кстати, в комментариях к прошлой заметке уже была дана ссылка не только на разборы этой задачи при N=124, но и на другие её модификации. Но всё же я предлагаю сначала попробовать найти решение своими руками, а уже потом читать чужой подход.

Хорошей недели!

(Хотите примеров сложных задач из разных областей знаний? Недавно мы рассматривали сложную задачку о коробочках, табличках и общей цели, а достаточно давно была геометрическая формулировка о впихивании тетраэдров в куб. В обоих случаях после нахождения какого-то неплохого решения возникает настоящая проблема — доказать, что ничего лучше не сочинить.)