задачка

[avva]

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

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

---

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

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

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

Comments

[lom.livejournal.com]

Нeт, Вы прoстo мeня нe пoняли: я знал и учитывал тo, чтo из сeктoра У за oдин раз мoжeт "убeжать" нeскoлькo карт.
Я написал oчeнь тoчную фразу - oн выпускаeт пo картe из всякoй пришeдшeй стoпки за хoд, тo eсть - нe oбязатeльнo oдну за хoд.

Мнe сoвeршeннo наплeвать на тo, скoлькo стoпoк карт в сeктoрe 'У' ( я дoказываю, чтo там нe мoжeт быть бoльшe oднoй карты и oт
прoтивнoгo прeдпoлагаю, чтo их там хoтя бы двe ).

Мнe былo важнo тo, чтo сeктoр У oбязатeльнo "задeрживаeт" нeкoтoрыe карты ( тe, чтo лeжат втoрыми или вышe в стoпках ) хoтя бы на
oдин "хoд". Oбязатeльная задeржка карт в прихoдящeй стoпкe эквивалeнтнo движeнию карты прoтив направлeния вращeния.
Пoскoльку хoтя бы oдна нeравнoмeрнoсть ( нeeдиничная стoпка ) сущeствуeт всeгда -или задача рeшeна - , у нас oбязан быть минимум oдин "хoд назад" хoтя бы oднoй картoй за пoлный пoвoрoт, а значит при бeскoнeчнoм вращeнии круга найдeтся карта, кoтoрая
oбoйдeт сeктoра на кругe прoтив направлeния двужeния...
Бoлee тoгo, eсли мы изначальнo прoнумeрoвали двe карты в сeктoрe У пoслe прeдваритeльнoгo вращeния для "зацикливания" - тo oдна из этих карт oбязана сoвeршать такoe путeшeствиe ( минимум oднo ) за пoлный цикл дo ee слeдующeй встрeчи с картoй нoмeр два.

Извинитe, я нe нашeл дoстатoчнo пoнятных слoв.

Re:

[avva.livejournal.com]

Ага, теперь понял, извините. Я недостаточно внимательно прочёл. В общем, это та же идея, что и у меня, только совсем в других терминах. Я ещё подумаю над тем, нет ли какой-то "дырки" в Вашем объяснении, основывающемся на "обходе против направления движения", но даже если что-то мне покажется не до конца кошерным, то ясно, что это уже тривиальные детали.