Комбинаторные задачи.

[Andrei94]

1) $25$ пионеров отряда "рыжие-бестыжие" сели в круг. Каждому из них дали ровно по 2 карточки. На каждой из $50$ карточек написаны числа $1,2,...,25$ (каждое число встречается ровно 2 раза). Раз в минуту (одновременно ) каждый пионер передает соседу слева ту из своих карточек, на которой написано меньшее число. Игра заканчивается, когда у кого-то на руках оказывается два карточки с одинаковыми числами. Докажите, что это обязательно произойдет.

Тут есть такие мысли. Если изначально у кого-то две карточки с одинаковыми числами, то игра закончилась.
Если нет пионера с карточками, на которых одинаковые числа, то передавая меньшее числа, в итоге переберутся все числа от 1 до 24, а значит у кого-то совпадет обязательно 2 карточки.
Можно ли это считать доказательством?

2) На столе лежат 2001 конфета. Пионеры решили поиграть в игру:
Тот у кого получится по правилам сделать по разбить все конфеты на кучки, в каждой из которых 3 конфеты, тот выиграл.
Правила такие:
За каждый ход можно нужно съесть одну конфету (из какой либо кучки), после чего разделить одну из кучек на две. Возможно ли, играя по правилам, выиграть в такой игре?

Можно так?

$1997, 3$
$1993, 3,3$
$1989, 3,3,3$
$1985, 3,3,3,3$
....
$3,3,3,...,3$ (и так 500 раз)

Верно?

3) В волшебной стране чудес можно обменять любые $3$ монеты на любые $2$ или наоборот. Может ли Алиса обменять $100$ монет на $100 монет$, при этом отдав $1991$ монету?

При каждом обмене количество монет увеличивается на 1 или уменьшается на одну, соответвенно, количество увеличений должно быть равно количеству уменьшений. Пока что только такая мысль пришла в голову.
А еще 1991 не делится на $5$, не делится на $3$, не делится на $2$. Как тут дальше можно рассуждать?

[Andrei94]

Видно я какую-то совсем чушь написал в идеях?

[Shtorm]

Andrei94, по крайней мере, идея решения первой задачи выглядит правдоподобной.

[Shadow]

Вообще намека на решение нат в первой задачи. Если случится в начале - хорошо, а если нет - когда нибудь все равно случится...

Andrei94 в сообщении #898763 писал(а):

в итоге переберутся все числа от 1 до 24

В том-то и дело, что не все переберутся. Карточки с номерами 25 будут стоять на месте. С номерами 24-скорее всего тоже, но может разок переместится и остановится навсегда. Короче, докажите, что все большие ($>13$) в один момент перестанут двигатся. А больших ровно 24. Что будет с остальными подумайте, особое внимание обратите на карточек с номером 13.

[Shtorm]

Shadow, пусть карточки с номерами 25 и 24 стоят на месте. Остальные-то номера будут двигаться по кругу.

[Shadow]

Andrei94 в сообщении #898763 писал(а):

Можно так?

$1997, 3$
$1993, 3,3$
$1989, 3,3,3$
$1985, 3,3,3,3$
....
$3,3,3,...,3$ (и так 500 раз)

Верно?

Думаю, нет. Есть одну и выделять 3 можно, когда общее число конфет $4k-1$ (пока в большой куче окажутся 7, дальше понятно) Но у вас $4k+1$
Вот решение, где скрыта ошибка. Надеюсь вы ее увидите и напишете правильное решение:
После $k$ "ходов" общее число конфет будет $2001-k$
После $k$ ходов общее число куч будет $k+1$. Допустим, во всех по 3 конфет
$2001-k=3(k+1)$
$4k=1998$
Невозможно!

-- 24.08.2014, 16:33 --

Shtorm в сообщении #899215 писал(а):

Shadow, пусть карточки с номерами 25 и 24 стоят на месте. Остальные-то номера будут двигаться по кругу.

После того как карточки 25 и 24 застали на месте, карточки с номерами 23 долго будут двигатся?

[Shtorm]

Shadow, да карточки с номером 23 вскоре застынут, за ними 22 и так далее - так чем быстрее они все застынут - тем быстрее у одного из игроков окажутся карточки с одинаковыми числами.

[Shadow]

Shtorm

Shtorm в сообщении #899288 писал(а):

так чем быстрее они все застынут

Не все, а все "большие" ($>13$, их 24 штук, малые 24 и $2\times 13$). 25 по условии должны "двигатся" каждую минуту, не игнорируйте окончание...если число пионеров было четным, то игра может и не закончится.

[Andrei94]

Shadow в сообщении #899165 писал(а):

Короче, докажите, что все большие ($>13$) в один момент перестанут двигатся. А больших ровно 24. Что будет с остальными подумайте, особое внимание обратите на карточек с номером 13.

А с каких карточек начать рассмотрение? С 25? ДА, действительно, 25-ая будет стоять на месте. 24, быть может, однажды сдвинется и действительно застынет. 23 может тоже сдвинуться, причем не один раз (а когда у пионера карточка 24 или 25 на руках).

Карточки с номерами 1 постоянно будет двигаться по кругу, потому они у одного пионера встретиться не могут. Карточка номер 2 остановится лишь тогда, когда у пионера на руках окажется еще карточка с номером 1.

Впрочем ясно -- что вы имеете ввиду, но слишком много вариантов, я не представляю -- как это можно структурно описать(

[Andrei94]

Извиняюсь, что долго не отвечал.

Shadow в сообщении #899225 писал(а):

Думаю, нет. Есть одну и выделять 3 можно, когда общее число конфет $4k-1$ (пока в большой куче окажутся 7, дальше понятно) Но у вас $4k+1$
Вот решение, где скрыта ошибка. Надеюсь вы ее увидите и напишете правильное решение:
После $k$ "ходов" общее число конфет будет $2001-k$
После $k$ ходов общее число куч будет $k+1$. Допустим, во всех по 3 конфет
$2001-k=3(k+1)$
$4k=1998$
Невозможно!

Я так понял, что если $n$ конфет разделить на $k+1$ кучку за $k$ ходов, то число $n$ должно быть представимо в виде $n=4k+3$ (если решить уравнение $n-k=3(k+1)$ относительно $n$). Но число $2001$ не представимо в виде $4k+3$, а значит так сделать нельзя, верно?

-- 26.08.2014, 21:50 --

А как тут в третьей задаче, подскажите, пожалуйста!

3) В волшебной стране чудес можно обменять любые $3$ монеты на любые $2$ или наоборот. Может ли Алиса обменять $100$ монет на $100 монет$, при этом отдав $1991$ монету?

При каждом обмене количество монет увеличивается на 1 или уменьшается на одну, соответвенно, количество увеличений должно быть равно количеству уменьшений. Пока что только такая мысль пришла в голову.
А еще 1991 не делится на $5$, не делится на $3$, не делится на $2$. Как тут дальше можно рассуждать?

[Shadow]

Andrei94 в сообщении #900362 писал(а):

Впрочем ясно -- что вы имеете ввиду, но слишком много вариантов, я не представляю -- как это можно структурно описать(

Вариант один. Большие 25 номера будут стоять на месте, малые 25 номера будут вертеться по кругу. И тут роль карточек с номером 13.

Andrei94 в сообщении #900434 писал(а):

Я так понял, что если $n$ конфет разделить на $k+1$ кучку за $k$ ходов, то число $n$ должно быть представимо в виде $n=4k+3$ (если решить уравнение $n-k=3(k+1)$ относительно $n$). Но число $2001$ не представимо в виде $4k+3$, а значит так сделать нельзя, верно?

Верно, так сделать нельзя. Но можно сделать иначе. Я сказал, что в решении скрыта ошибка.

Shadow в сообщении #899225 писал(а):

После $k$ ходов общее число куч будет $k+1$

Вот здесь. Кучи не всегда увеличиваются на 1-если в некоторой куче только одна конфетка....

Andrei94 в сообщении #900434 писал(а):

При каждом обмене количество монет увеличивается на 1 или уменьшается на одну, соответвенно, количество увеличений должно быть равно количеству уменьшений. Пока что только такая мысль пришла в голову.

Составить уравнение - такая мысьл не приходила? Например..."количество увеличений должно быть равно количеству уменьшений должно быть равно икс".

[Andrei94]

Shadow в сообщении #900569 писал(а):

Andrei94 в сообщении #900434 писал(а):

При каждом обмене количество монет увеличивается на 1 или уменьшается на одну, соответвенно, количество увеличений должно быть равно количеству уменьшений. Пока что только такая мысль пришла в голову.

Составить уравнение - такая мысьл не приходила? Например..."количество увеличений должно быть равно количеству уменьшений должно быть равно икс".

Спасибо, хорошо! Тогда, если было $x$ уменьшений, то было $x$ увеличений еще. Получается, что $x=1991$. Чтобы отдать 1991 талон, нужно отдать $2x+3x=5x$ талонов. Но число 1991 не делится на 5, а значит такой обмен сделать невозможно. Верно?

-- 27.08.2014, 10:28 --

Shadow в сообщении #900569 писал(а):

Кучи не всегда увеличиваются на 1-если в некоторой куче только одна конфетка....

Ох, точно, спасибо. То есть можно изначально сьесть конфету, разделить на кучки -- 1999 и 1.
Число 1999 представимо в виде $4k+3$, значит можно разбить по $3$ конфеты, а в самом конце съесть ту 1 конфету, которая была в одной кучке. Верно?

-- 27.08.2014, 10:32 --

Shadow в сообщении #900569 писал(а):

Вариант один. Большие 25 номера будут стоять на месте, малые 25 номера будут вертеться по кругу. И тут роль карточек с номером 13.

Подозреваю, что именно номер два номера 13 рано или поздно должны оказаться у одного пионера. Но пока что нет представлений -- как это все структурно начать описывать(

[Andrei94]

Только что понял, что это оказалось неверно, потому как в конце будет в таком случае сделан не полный ход.

Цитата:

То есть можно изначально сьесть конфету, разделить на кучки -- 1999 и 1.
Число 1999 представимо в виде $4k+3$, значит можно разбить по $3$ конфеты, а в самом конце съесть ту 1 конфету, которая была в одной кучке. Верно?

[Shadow]

Да, надо по другому. Не будем мучатся:
1-1999
1-1998
3-1995

1995 хорошее число вида $4k+3$

[Andrei94]

Shadow в сообщении #901031 писал(а):

Да, надо по другому. Не будем мучатся:
1-1999
1-1998
3-1995

1995 хорошее число вида $4k+3$

Спасибо, понятно!
А как с задачей про конфеты и пионеров? Подскажите, пожалуйста... Интуитивно догадываюсь, что карточки будут неспешно двигаться, потому рано или поздно у кого-то будут две карточки с номером 13. Но как описывать этот все движение?
25 будет стоять на месте,
24 сдвинется не более чем на 1 позицию,
23 -- не более чем на 2,
22 -- не более чем на 3,
21 не более чем на 4,
20 не более чем на 5,
19 не более чем на 6,
18 не более чем на 8
17 не более чем на 9
16 не более чем на 10
15 не более чем на 11
14 не более чем на 12
13 не более чем на 13 (если сдвинется, то игра остановится)
Но не более чем -- не гарантирует, что ровно на 13. Как доказать, что ровно на 13?