Древнекитайская головоломка о подносах с монетами

[Xenia1996]

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

[Sonic86]

Xenia1996 писал(а):

Затем снова выбрать любые два (возможно, других) подноса, взять по одной монете с каждого из них и переложить обе эти монеты на любой другой поднос.

А если один из выбранных подносов пустой - операция не выполнима?

[Xenia1996]

Sonic86 в сообщении #429064 писал(а):

Xenia1996 писал(а):

Затем снова выбрать любые два (возможно, других) подноса, взять по одной монете с каждого из них и переложить обе эти монеты на любой другой поднос.

А если один из выбранных подносов пустой - операция не выполнима?

Разумеется. Нельзя же оставить минус одну монету. Тем более, что в Древнем Китае не пользовались отрицательными числами!

Класть на пустой поднос можно, а вот брать нельзя.

[whitefox]

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

[Xenia1996]

whitefox в сообщении #429071 писал(а):

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

А если непустых подносов ровно 2, как Вы собираетесь обнулять?

[Sonic86]

Пусть подносов как минимум 3. Сначала есть $(a,b,0)$. Если $a=b$, то задача решается перекладыванием в 3-й поднос, считаем, что $0<b<a$. На первом шаге число монет везде разное. На каждом шаге берем 2 кучки где монет больше и из нее перекладываем по одной монете в кучку, где монет меньше. В результате максимальная разница между количеством монет уменьшается на каждом шаге (при условии, что эта разница больше 2!). В итоге наступит момент, когда окажется, что есть 2 кучки с одинаковым числом монет. Перекладываем из этих кучек в оставшуюся кучку и все.
Хотя нет. Я вру: $(2;3;7) \to (4;2;6) \to (3;4;5) \to (5;3;4) \to ...$. Видимо 4-й поднос все же нужен. Например $(0;1;2)$ вообще неразрешим, указанное преобразование оставляет его на месте.

[spaits]

Sonic86 в сообщении #429080 писал(а):

Видимо 4-й поднос все же нужен.

Sonic86, по условию, подносов больше трёх, значит, как мимимум, их четыре (как и монет).
Случай $(0,1,2) $ не соответствует условию задачи.

[Sonic86]

Разница перестанет уменьшаться в случае расклада $(a,a+1,a+2)$. Вот тут-о и нужен 4-й поднос: $(a,a+1,a+2) \to (a,a,a+1,2) \to (a-1,a-1,a+5,0) \to ... \to (0,0,N,0)$ - возможно лишь при $a>0$, а в случае $a=0$ получаем только 3 монеты, как и оговорено в условии задачи.

-- Ср мар 30, 2011 16:05:09 --

spaits писал(а):

Sonic86, по условию, подносов больше трёх, значит, как минимум, их четыре (как и монет).
Случай $(0,1,2) $ не соответствует условию задачи.

Да, я понял. Просто хотелось понять, почему условие именно такое. Вроде как решение получилось соответствующим условию

[Xenia1996]

Вот моё решение:

Начнём с того, что число непустых подносов всегда можно уменьшить до двух. Действительно, берём два подноса с наименьшим числом монет и перекладываем с каждого по одной монете на тот поднос, где монет больше всех. Рано или поздно, поднос с наименьшим числом монет опустеет.

Теперь у нас осталось два непустых подноса, на одном x монет, на другом y $(x\le y)$ По условию подносов больше 3, значит, должны быть ещё 2 пустых подноса, z и w.

1) Если x=y, то просто перекладываем с этих двух подносов на z каждый раз по одной монете.

2) Если x меньше y и чётно, то перекладываем по одной монете c подносов x и y попеременно то на z, то на w. Когда x опустеет, у нас будет равное количество монет на z и w, переложим их по одной на y.

3) Если x меньше y и нечётно, то перекладываем одну монету c x и одну монету с y на поднос z. Тогда на x будет чётно, а на z будут две монеты.
Теперь переложим по две монеты с x и z на y. z снова опустел, остались x и y, и x - чётно! Возвращаемся к пункту 2) и решаем задачу!

[Sonic86]

Вы используете сразу 4 подноса. Хорошее решение, на мой взгляд!

[Xenia1996]

Sonic86 в сообщении #429112 писал(а):

Вы используете сразу 4 подноса. Хорошее решение, на мой взгляд!

Если изначально подносов было ровно 3, то задача может быть неразрешимой. Рассмотрите, как меняются остатки при делении на 3 разности между некоторыми двумя подносами.

[whitefox]

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

-- 30 мар 2011, 14:05 --

Вопрос в продолжение темы: можно ли из моей позиции получить правильное решение?

[Sonic86]

whitefox писал(а):

Вопрос в продолжение темы: можно ли из моей позиции получить правильное решение?

Ну так я из Вашей позиции его и сделал!

[whitefox]

Значит и у меня был шанс.