Олимпиада, не могу додуматься, то ли условий недостаточно, то ли я тупой...

Question

Олимпиада, не могу додуматься, то ли условий недостаточно, то ли я тупой...

Uriy Kashalov Ученик (102), закрыт 3 месяца назад

Имеется N>1 одинаковых предметов разложенных по M <= N кучам произвольным образом. Чтобы сделать ход игрок берет из каждой кучи по одному предмету и складывает взятые предметы в новую кучу (например разложение 1-2-2 переходит в разложение 1-1-3, а 1-1-1-4 - в 3-4). расположение куч значения не имеет. Игра заканчивается если после какого либо по счету хода разложение предметов оказывается таким же как перед этим ходом первое задание: при каком минимальном N игра закончится? Через какое максимально количество ходов это произойдет при таком N?

Answer 1

Dmitry Просветленный (22981) 3 месяца назад

Можно перебором.
N=2 не подходит, потому что бесконечно будут чередоваться разложения 1-1 и 2.
N=3 подходит. Здесь возможно всего три варианта:
a) 1-2 => 1-2 (1 ход);
б) 3 => 1-2 => 1-2 (2 хода);
в) 1-1-1 => 3 => 1-2 => 1-2 (максимальные 3 хода).
Ответ: 3; 3.

Uriy KashalovУченик (102) 3 месяца назад

А почему ты не переставляешь цифры? 1-2 => 1-2 (нужно же 1-2 => 2-1) их же нужно переставлять или ты пользуешься правилом что расположение куч значения не имеет? И почему оно не может зациклиться? Типо 1-1-1 => 1-2 => 1-1-1 => 1-2

Dmitry Просветленный (22981) Uriy Kashalov, да, взаимное положение куч не имеет значения. Для удобства, числа по возрастанию записаны. 1-1-1 => 1-2 быть не может. Потому что, если из 1-1-1 везде взять по одному предмету, то вообще никаких куч не остаётся. Потом кладём - одна новая куча из 3-х предметов. Чтобы понять, это проще без цифр - нарисовать, например, кучки из точек

Answer 2

Ласпи Оракул (71791) 3 месяца назад

То ли в лыжи обутый.