ИТМО 2024

Рассмотрим некоторого человека, назовем его Пусть его шляпа изначально оказалась у какого-то шляпа оказалась у и т.д.. Рассмотренный нами процесс нумерации рано или поздно закончится тем, что для какого-то его шляпа окажется у какого-то который был уже нами пронумерован ранее. Заметим, что это так как про всех остальных мы уже знаем, откуда взялись находящиеся у них шляпы. Значит, шляпа в начале представления оказалась у и мы получим цикл из человек. Каждый раз каждый из участников передает свою шляпу следующему по циклу. Таким образом, шляпы в этом цикле вернутся к своим хозяевам через минуту, затем через каждые следующие следующие минут.

Таких циклов может быть несколько. Тогда если все шляпы вернутся к своим хозяевам через минут, число должно делиться на длины всех этих циклов. Таким образом, нам нужно разложить число 12 в сумму нескольких слагаемых так, чтобы их наименьшее общее кратное было максимальным. Возьмем следующее разложение:

НОК этих чисел — 60, значит, шляпы вернутся к своим хозяевам через 59 минут. Если все слагаемые являются делателями числа 24, то их НОК не больше 24. Значит, для большего НОК нужно хотя бы одно число, не являющееся делителем 24, например, 5, 7, 9, 10 или 11. Варианты, в которых все слагаемые, кроме одного, равны единице, нам не нужны. Переберем оставшиеся варианты для слагаемых, больших 5:

• НОК
• НОК
• НОК
• НОК Для вариантов и НОК, очевидно, еще меньше.
• НОК

Осталось рассмотреть варианты с 5. Если все остальные делители не больше 6, НОК не больше, чем 60, а вариант с 7 мы уже разобрали. Значит, ответ — 59.