Король загадал одну из 36 игральных карт

[Гость]

Король загадал одну из 36 игральных карт. За один ход мудрецу разрешается разложить карты на стопки с разным числом карт во всех стопках и узнать у короля, в какой из них лежит загаданная карта. Как мудрецу отгадать карту за два хода?

[admin]

Заметим, что 1+2+3+4+5+6+7+8 = 36. Разложим все 36 карт в треугольник ("лестницу") из 8 строк, где в i-й строке ровно i карт:

строка 1: 1
строка 2: 2, 3
строка 3: 4, 5, 6
строка 4: 7, 8, 9, 10
строка 5: 11, 12, 13, 14, 15
строка 6: 16, 17, 18, 19, 20, 21
строка 7: 22, 23, 24, 25, 26, 27, 28
строка 8: 29, 30, 31, 32, 33, 34, 35, 36

Первый ход. Мудрец выкладывает стопки-строки: 1, 2, 3, 4, 5, 6, 7, 8 карт. Числа карт попарно различны, сумма равна 36, значит раскладка допустима. Король указывает номер строки i.

Второй ход. Мудрец снова берёт все 36 карт и выкладывает их стопками-столбцами того же треугольника: в j-м столбце лежат j-е по порядку карты из строк j, j+1, ..., 8, то есть ровно 9-j карт:

столбец 1: 1, 2, 4, 7, 11, 16, 22, 29 (8 карт)
столбец 2: 3, 5, 8, 12, 17, 23, 30 (7 карт)
столбец 3: 6, 9, 13, 18, 24, 31 (6 карт)
столбец 4: 10, 14, 19, 25, 32 (5 карт)
столбец 5: 15, 20, 26, 33 (4 карты)
столбец 6: 21, 27, 34 (3 карты)
столбец 7: 28, 35 (2 карты)
столбец 8: 36 (1 карта)

Размеры 8, 7, 6, 5, 4, 3, 2, 1 тоже попарно различны и в сумме дают 36, так что и такая раскладка разрешена. Король указывает номер столбца j.

Почему двух ходов хватает: строка и столбец треугольника пересекаются не более чем по одной карте, а каждая карта однозначно определяется парой (строка, столбец). Узнав i и j, мудрец называет карту, стоящую в i-й строке на j-м месте.

Замечание. Восемь стопок — это минимум: если в первом ходе есть стопка из i карт, то во втором ходе все её карты обязаны попасть в разные стопки, значит стопок не меньше 8; а единственный набор из 8 различных натуральных чисел с суммой 36 — это 1, 2, ..., 8. Поэтому такая треугольная конструкция по существу единственная.