?

Log in

решение задачи - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

решение задачи [окт. 30, 2002|07:10 pm]
Anatoly Vorobey
Решение задачки про карты.

В результате только lom написал там в комментах полное решение, основанное на индукции. Решение, которое я знаю (придумал его сам когда-то) и сейчас объясню, практически совпадает с решением lom'а. Другое, основанное на нахождении инварианта комбинации, решение начал писать dyak, но пока не закончил.

Так вот. Мы доказываем индукцией по n, что если нам даны 1+2+3+...+n карт, разложенных в кучки, и если мы продолжаем без конца операцию взятия по одной карте из каждой кучки и составления из взятых карт новой кучки, то в конце концов мы придём к разложению из n кучек, в которых будет соответственно 1,2,....,n карт. Условие нашей задачи соответствует тогда случаю n=9.

Случай n=2 очевиден просто путём перебора всех возможных комбинаций из трёх карт.

Итак, предположим, что утверждение выполняется для n-1, и докажем его для n. Для наглядности я буду рассматривать случай n-1=8 и n=9, т.е. 45 карт, но всё сказанное никак не использует конкретное значение n и потому доказывает общий шаг индукции.

Суть нашего подхода в том, что мы можем расположить наши карты в кучках (которые я отныне буду называть столбиками, мне так удобнее), и установить некие правила, согласно которым мы выбираем карту из данного столбика, таким образом, что нам это поможет "симулировать" задачу для n=8 (1+2+3...+8 = 36 карт) "внутри" задачи для n=9 (1+2+3...+9=45) карт (или, в общем случае, "симулировать" задачу n-1 внутри задачи для n). Важно понять, что в первоначальном условии задачи все карты "одинаковы", и для правильного следования условию совершенно неважно, какую именно карту я беру из каждого столбика на каждом шагу - например, верхнюю, нижнюю, или любую другую. Поэтому я могу придумывать любые правила на этот счёт, и следовать им -- лишь бы из каждого столбика на каждом шагу уходила в новый столбик ровно одна карта.

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

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

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

Далее, введём два правила, которые регулируют, какую именно карту из каждого столбика мы берём на каждом шагу.

Правило 1. Если в данном столбике есть белые карты, мы обязательно берём белую карту (какую именно из белых? неважно, но если надо представить, то, например, верхнюю). Только когда все белые карты в столбике кончаются, мы начинаем брать красные.

Правило 2. Если мы берём из столбика красную карту (т.е. все белые уже кончились), то берём всегда самую верхнюю из красных карт (т.е. самую близкую к горизонтальной оси, ниже которой лежат все красные карты). Более того, во вновь образованном столбике мы ставим самой верхней - самую левую из собранных красных карт (т.е. карту, взятую из самого левого столбика, из которого мы брали красные карты), под ней - следующую по порядку слева-направо, итд.

Эти два правила, как объяснено выше, ничего не меняют с точки зрения первоначального условия задачи. Если мы, следуя им, обязательно получим 9 столбиков с 1,2,....,9 картами в них, то тем самым мы решили задачу.

Теперь мы можем применить предположение индукции для n=8, для наших 36 "белых" карт. Действительно, если на секунду мы "забудем" про все красные карты, то увидим, что с белыми картами мы ведём себя в точности согласно первоначальному условию задачи (для n=8). Это следует из нашего Правила 1 (оно здесь очень важно), которое гарантирует, что на каждом шагу из каждого столбика, в котором есть белые карты, мы берём по одной белой карте, и из них состоит "белая" часть нового столбика.

Поэтому, согласно предположению индукции для n=8, через какое-то конечное число шагов нашей системы по нашим правилам, 36 белых карт станут в 8 столбиков с 1,2,3.....,8 карт в этих столбиках. (одна белая карта будет в самом правом из этих столбиков, а 8 - в самом левом; это следствие того, что новые столбики мы ставим слева от существующих). Это расположение белых карт будет теперь повторяться после каждого шага, "съезжая" влево на один столбик на каждом шагу. Всё, что нам осталось теперь доказать, это то, что через какое-то количество шагов после этого красные карты лягут в точности в нужные девять позиций под белыми (одна красная карта под каждым белым столбиком и ещё одна - справа от последнего белого столбика). Если это произойдёт, то это как раз и будет нужная конечная позиция для наших 45 карт -- девять столбиков с 1,2,....9 карт в них -- которая будет повторяться после каждого шага до бесконечности.

Как это доказать? Нужно посмотреть внимательнее на движение красных карт (напомню, что согласно Правилу 1 красные карты в каком-то столбике начинают сниматься только после того, как закончились все белые над ними). Нам нужно, чтобы все 9 карт попали в девять нужных позиций (8 позиций под белыми столбиками и одна - справа от последнего правого белого столбика). Назовём эти 9 позиций слотами. Эти слоты движутся влево с каждым шагом, вместе с "белыми" столбиками над ними.

Где вообще могут находиться красные карты? Какие-то из них могут быть уже в нужных слотах, какие-то другие могут находится под красными картами в слотах, образуя "красные столбики" длиной больше, чем одна карта; наконец, какие-то ещё могут находится правее всех "слотовых" столбиков (являясь остатками "длинных" красных столбиков, которые там были, и из которых наша система до сих пор продолжает снимать по одной карте, в то время, как белые столбики успели уже "убежать" влево). Если красная карта находится в каком-то слоте, в одной из 9 нужных конечных позиций, назовём такую красную карту бронзовой.

Важный факт: бронзовые карты остаются бронзовыми по мере движения системы. Почему? Потому что в любой данный момент максимум одна бронзовая карта находится в "открытом" положении, не под белыми -- а именно, та бронзовая карта, которая находится в 9-м слоте, справа от самого маленького белого столбика (если она вообще там есть). Эта бронзовая карта на следующем ходу уйдёт на бронзовое место вновь образованного столбика -- согласно нашему Правилу 2 (т.к. она самая верхняя в своём столбике, и она лежит в самом левом из всех возможных столбиков, из которых берут красные карты - во всех столбиках левее её есть белые кары). Более того, этот следующий ход "освободит" для дальнейшего удаления не более одной бронзовой карты -- а именно, той, которая лежала под белым столбиком с одной белой картой. Таким образом, каждый ход "высвобождает" не больше одной бронзовой карты, и на следующем ходу эта бронзовая карта уходит на вновь образовавшеся бронзовое место.

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

Итак, пусть у нас есть положение, в котором не все карты бронзовые. Не-бронзовые карты либо лежат в столбиках под бронзовыми, либо лежат справа от всех слотовых столбиков, и ждут, пока их оттуда подберут (они были частью длинных красных столбиков, и белые столбики "убежали" от них влево). Если вообще нет ни одной бронзовой карты, то все красные карты находятся справа от слотовых столбиков, и очевидно, что после следующего хода какая-то красная карта станет бронзовой. Поэтому можно предположить, что какие-то бронзовые карты уже есть. Далее, мы ищем какую-то красную карту, которая лежит прямо под бронзовой. Если такой нет, то все красные карты, кроме бронзовых, находятся справа от слотовых столбиков; но тогда сделаем 9 шагов системы, и все эти карты (к-х не больше 8; напомню, что всего красных карт 9) обязательно лягут где-нибудь под новыми девятью слотовыми столбиками (все эти карты подберут за 9 шагов, и все они лягут под вновь образовавшиеся 9 столбиков, к-е и являются новыми 9 слотовыми столбиками). Значит, каждая из них ляжет либо в слотовое место (и тогда у нас уже есть новая бронзовая карта и ничего доказывать не надо), либо под бронзовую карту, и тогда у нас будет красная карта того вида, что я ищу (лежащая прямо под бронзовой).

Значит, единственный случай, для которого мне осталось доказать, что рано или поздно появится новая бронзовая карта, такой: у нас есть хотя бы одна бронзовая карта, под которой лежит красная (возможно, под ней лежит больше одной красной, но остальные нас не интересуют). Перенумеруем все бронзовые карты согласно номерам слотов, в которых они лежат (от 1 до 9, где 1 - номер слота, над которым 9 белых карт, 8 - слот, над которым одна белая карта, 9 - номер "свободного" слота).

Заметим, что номера бронзовых карт (как и слотов, в которых они лежат) сохраняются с периодичностью в девять шагов. Например, если бронзовая карта лежит в слоте номер 5, то её номер будет меняться так: 5, 6, 7, 8, 9, 1, 2, 3, 4, 5 -- переход от 9 к 1 это как раз тот шаг, когда её берут из "свободного" слота и кладут в вершину нового столбика. Что при этом происходит с нашей красной картой, которая лежит под бронзовой? Предположим, например, что она лежит под бронзовой картой номер 5. Через четыре шага эта бронзовая карта становится номером 9, и на следующем шагу "уходит" в новый столбик, а красная карта под ней остаётся. Что будет ещё через один шаг? Всё зависит от того, была ли "бронзовая" карта в слоте номер 4. Если не было, то в столбике слева от нашей красной карты вообще нет красных карт, и согласно Правилу 2 наша красная карта теперь становится бронзовой. Если же была, то согласно тому же правилу эта вторая "бронзовая" карта идёт в вершину нового столбика, а наша красная идёт под неё. Тогда через 9 шагов после начала наша красная карта будет уже под бронзовой номер 4, а не номер 5.

Что же это значит? Мы зафиксировали внимание на одной конкретной красной карте, лежащей под какой-то бронзовой, и видим, что через 9 шагов наша красная карта неизбежно переходит на один столбик влево. Если в этом столбике есть своя бронзовая, наша карта ляжет под неё; если нет - станет бронзовой. Таким образом, "прыгая" по бронзовым картам, наша красная карта неизбежно дойдёт до пустого слота (а пустые слоты есть, т.к. не все карты ещё бронзовые), и когда она до него дойдёт, то станет бронзовой. Что и требовалось доказать.
СсылкаОтветить

Comments:
[User Picture]From: lom
2002-10-30 10:10 am

eщe oдна задачка

Анатoлий, хoтитe задачку, кoтoрая хoть и сoвсeм другoгo рoда, чeм Ваша с картами, нo тoжe oтличаeтся прeдeльнo прoстoй фoрмулирoвкoй, и при этoм трeбуeт дoвoльнo сeрьeзных усилий для рeшeния ?

Вo всякoм случаe, я кoгда-тo убил на нee дoвoльнo мнoгo врeмeни - пару вeчeрoв, как минимум.
Сразу oгoвoрюсь, чтo "oфициальнoгo" рeшeния я нe знаю, хoтя и нe вижу никакoгo пoвoда усoмниться в мoeм сoбствeннoм.
Задача звучит так:

С пoмoщью циркуля и линeйки пoстрoить oкружнoсть, касающуюся трeх данных.

Излагать рeшeниe пoдрoбнo нe нужнo, впoлнe хватит идeи, как этo сдeлать.
(Ответить) (Thread)
[User Picture]From: avva
2002-10-30 10:11 am

Re: eщe oдна задачка

Ой, это не для меня.
Просто не люблю такие задачки, у меня плохое геометрическое воображение итп.

Может, кого другого заинтересует разве что ;)
(Ответить) (Parent) (Thread)
[User Picture]From: lom
2002-10-30 10:28 am

Re: eщe oдна задачка

Пoлнoстью Вас пoнимаю, у мeня тoжe плoхoe прoстранствeннoe вooбражeниe и как правилo, я тeрпeть нe мoгу рeшать гeoмeтричeскиe задачи. Данная - oднo из нeмнoгих исключeний. Oна как бы нe сoвсeм гeoмeтричeская, тo eсть чeм бoльшe чeлoвeк рисуeт всяких картинoк (крoмe самoй пeрвoй, oтражающeй услoвиe, eсли этo пoмoгаeт eму думать), тeм хужe для нeгo. Нo пoсмoтрим ...
(Ответить) (Parent) (Thread)
From: drw
2002-10-30 10:51 am

уточните, пожалуйста

Касание, надо думать, внешнее?
(Ответить) (Parent) (Thread)
[User Picture]From: lom
2002-10-30 01:20 pm

Re: уточните, пожалуйста

Def: касающимися называются oкружнoсти, имeющиe oдну и тoлькo oдну oбщую тoчку.
Тo eсть, "внeшнee" касаниe нe спрашивалoсь.

Тeм нe мeнee, впoлнe дoпустимo рeшать задачу для "внeшнeгo" касания - а пoтoм пoсмoтрeть, пoдхoдит ли придуманный мeтoд в oбщeм случаe. Eсли нeт - тo придeтся прoдoлжать....
(Ответить) (Parent) (Thread)
[User Picture]From: ctapyxa
2002-10-31 12:08 am

Полночи ломала голову.

Пытаясь вспомнить, когда ж я решала такую задачу.
К утру вспомнила.
Это задача Аполлония.
Из моей любимой в школе книжки "Старинные задачи"
Была еще одна такая же любимая "Старинные английские задачи"
Ну так, про Аполлония.
Решается при помощи инверсии.
Но я вот все сомневаюсь, что Аполлоний ее так доказывал.


(Ответить) (Parent) (Thread)
From: drw
2002-10-31 04:29 am

Re: Полночи ломала голову.

Вот-вот, мне приятель сегодня сказал - "Задача простая, нужно два раза провести инверсию". Осталось выяснить, как это делается. :-)
(Ответить) (Parent) (Thread)
[User Picture]From: lom
2002-10-31 06:58 am

Re: Полночи ломала голову.

Надeюсь, вспoмнив прo Апoллoния, ты всe-таки заснула и к тeбe прилeтeли хoрoшиe сны :)
Мнe, кстати, ничeгo прo автoрствo задачи нe былo извeстнo, спасибo...

А насчeт инвeрсии... да, мoжнo сказать и так. Нo нужнo чуть пoдрoбнee.
(Ответить) (Parent) (Thread)
[User Picture]From: ctapyxa
2002-10-31 07:32 am

Ти-ичер. Пли-из!

Не. Этот подвиг второй раз мне не повторить.
Тогда три дня ушло :)
А в то время, я, несомненно, была умнее...
(Ответить) (Parent) (Thread)