задачка

[avva]

Математическая задачка. Нетривиальная! На любителя.

Те, кто заранее знают решение, не выдавайте, а то неинтересно будет. Если в комментах не появится решение, напишу его через пару дней.

---

Есть 45 карт (игральных). Они разложены в какое-то количество кучек, в каждой кучке какое-то количество карт.

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

Доказать: независимо от того, с какого расположения карт мы начали, рано или поздно всегда дойдём до повторяющегося расположения из девяти кучек, в которых лежат соответственно 1,2,3,4,5,6,7,8 и 9 карт.

Comments

[dyak.livejournal.com]

ОК. Этот кошмар хоть какое, но вроде решение. Я думал, что из этого подхода что–то поэлегантней выковырять можно, но не смог. Только грубая сила.

Предварительные вещи.
Считаем стопки слева направо. Положение карты в стопке снизу вверх.
Новая стопка ставится слева от старых. Между стопками пустых мест нет, т.е. если в стопке была одна карта, после следующего шага стопке правее ее сдвигаются влево.
Координата каждой карты (х,у), х –– номер стопки, у –– номер карты в стопке. То есть нижняя карта в последней изготовленной стопке –– (1,1)

Мы будем рассматривать величину ЦТ = Сигма(х+у) для всех карт, т.е. для всех карт складываем ихние х'ы и у'и. Пример: если во всем мире две карты, то ЦТ=5 всегда ( (1,1) и либо (2,1) либо (1,2) ).
(Исторически, ЦТ – центр тяжести, представьте ху плоскость, повернутую на 90 градусов против часовой стрелки)

Стопки с одной картой я буду называть одиночными.

Что происходит при формировании новой стопки.
1. Если справа от одиночных стопок нет неодиночных, то ЦТ не изменяется. И впрямь: нижний ряд поворачивается на 90 градусов против часовой и для них х становится у и у становится х. Остальные карты смещаются вправо и вниз, для них у уменьшился а х увеличился на 1.
2. Если справа от одиночных стопок нет неодиночных, то ЦТ уменьшается. Нижний ряд поворачивается на 90 градусов против часовой и для них х становится у и у становится х. Остальные карты смещаются вправо и вниз, для них у уменьшился а х увеличился на 1. А ПОТОМ часть их сдвигается влево чтобы заполнить места возникшие из–за одниночных стопок, ставших пустыми и их х уменьшается на 1.

ЦТ до бесконечности идти вниз не может и не увеличивается, значит упрется в какую–то константу. В конце система выходит на цикл. Если некоторое состояние ведет к уменьшению ЦТ, оно не часть цикла, к нему возврата нет. Дык какие же состояния не ведут к уменьшению ЦТ?

Элегантная часть закончена. Далее см. часть #2

[dyak.livejournal.com]

3. Ясно, что стопки будут рассортированы и самая высокая –– слева, а самая низкая справа, любое нарушение сортировки ведет к появлению единичной стопки, у которой справа неединичная, ЦТ, уменьшится, и назад к нерассортированному состоянию дороги нет.

4. Ясно, что нет более двух стопок одинаковой высоты, так как если есть три стопки одной высоты, то будет три единичные стопки (на крайнем правом конце, конечно) а это приведет к нарушению сортировки в крайних левых стопках.

Продолжение следует...

[avva.livejournal.com]

Номер 4. я не очень понял.