Автомат Григорьева

[Ktina]

Оказывается, автоматы бывают не только с газировкой.

Автомат Григорьева может из двух карточек с натуральными числами $a, b$ сделать
либо одну карточку с их суммой, либо $a$ карточек, на каждой из которых написано число
$b$. У Серёжи изначально есть 3 карточки с числами 3,4,5. Он хочет получить ровно одну
карточку, на которой написано 2012. Удастся ли ему это? (С.Григорьев)

Думаю, надо сперва превратить 3 и 4 в три четвёрки, тогда у нас получится 4, 4, 4, 5.
Затем 4 и 5 превращаем в 5 четвёрок и получаем всего 7 четвёрок. Далее, из двух четвёрок можно сделать 4 четвёрки, таким образом, количество четвёрок увеличится на 2. Повторим эту операцию несколько раз, пока не получим 503 четвёрки. Затем за 502 хода просуммируем их и в итоге получим одну карточку с числом 2012. Как-то так?

У меня такое ощущение, что можно получить одну карточку не только с числом 2012, но и с любым достаточно большим числом. Как бы это доказать?

[Dmitriy40]

Представимы числа $12, 17, 19, 22$ и далее все.
Числа вида $14+3n$ представимы в виде преобразований $(3,4,5) \to (3,3,3,3,5)=17 \to (3,3,3,3,3,5)=20 \to \ldots$ (далее всегда две тройки заменяются на три тройки).
Числа вида $16+3n$ представимы в виде преобразований $(3,4,5) \to (3,3,3,3,3,4)=19 \to (3,3,3,3,3,3,4)=22 \to \ldots$ (далее всегда две тройки заменяются на три тройки).
Числа вида $21+3n$ представимы в виде преобразований $(3,4,5) \to (3,3,3,3,5) \to (3,3,3,3,3,3,3,3)=24 \to \ldots$ (далее всегда две тройки заменяются на три тройки).
Начиная с $22$ эти три последовательности покрывают все натуральные числа.

-- 12.03.2018, 09:35 --

Интересен вопрос о минимальном наборе карточек, покрывающих все натуральные числа, начиная с некоторого.
Очевидно одной карточки недостаточно.
Так же очевидно что в наборе должна быть минимум одна карточка с нечётным числом, иначе нечётные числа никак не получить.
Набор $(1,1)$ не подходит, из него получаются лишь числа $1,2$.
Набор $(1,2)$ не подходит, из него получаются лишь числа $1,2,3$.
Набор $(1,3)$ не подходит, из него получаются лишь числа $1,2,3,4$.
Набор $(1,4)$ не подходит, из него получаются лишь числа $1,2,3,4,5$.
Набор $(1,5)$ интереснее, из него уже получаются всё чётные числа большие $5$ через преобразования $(1,5) \to (1,1,1,1,1) \to (3,2) \to (2,2,2) \to (4,2) \to (2,2,2,2)=8 \to \ldots$ (рекурсивная замена трёх двоек на четыре двойки). Ну а числа от $1$ до $6$ получаются аналогично предыдущим пунктам. Также получаются все числа вида $3+3n$ преобразованиями $(1,5) \to (1,1,1,1,1) \to (3,2) \to (3,3)=6 \to (3,3,3)=9 \to \ldots$ (рекурсивная замена двух троек на три тройки). Нечётные некратные трём числа получить видимо невозможно.
Набор $(1,6)$ к предыдущему богатству добавляет комбинацию $(1,6) \to (1,1,1,1,1,1) \to (3,2,1) \to (2,2,2,1)=7$, из которой получаются все нечётные числа от $7$ рекурсивной заменой трёх двоек на четыре двойки. И этим закрывает всё множество натуральных чисел. Так что это первый набор вида $(1,k)$, покрывающий вообще всё натуральное множество.

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

[kotenok gav]

А почему нельзя получить числа 1,2,3,4,5,6,7,8,9,10,11,13,14,15,16,18,20,21?

[Dmitriy40]

Собственно, можно и прикрыть немного, рассмотрев самый первый набор из трёх разных неединичных карт $(2,3,4)$.
Комбинация $(2,4)$ даст все чётные числа от $6$, значит добавив к ним три получим все нечётные от $9$ и далее.
Преобразование $(2,3,4) \to (2,2,2,4)$ даст все чётные от $10$. Т.е. числа от $9$ и далее закрыты все. А меньше девяти получить и невозможно.

Остался вопрос можно ли обойтись двумя неединичными картами. Думаю нет: надо ведь сохранить нечётную карту и плюс ещё заиметь минимум три двойки. Т.е. после первого преобразования в наборе должна остаться карта с нечётным числом и карта с двойкой, что невозможно.

Остался также вопрос с одинаковыми картами в наборе, например $(2,2,3)$ и $(2,3,3)$. Учитывая что первый преобразуется ко второму за один шаг, рассмотрим только второй.
$(2,3,3) \to (2,2,2,3)$, а отсюда получаются все чётные от $10$ и все нечётные от $9$. Плюс первый набор даст числа $7$ и $8$. Т.е. набор $(2,2,3)$ является минимальным набором из трёх неединичных карт, покрывающим все натуральные числа от $7$.

Итого.
С единичной картой в наборе минимальным будет набор $(1,6)$, покрывающий все натуральные числа.
Без единичной карты минимальным будет набор $(2,2,3)$, покрывающий все натуральные числа от $7$.
Без единичной карты минимальный набор разных карт будет $(2,3,4)$, покрывающий все натуральные числа от $9$.

-- 12.03.2018, 10:14 --

kotenok gav в сообщении #1296908 писал(а):

А почему нельзя получить числа 1,2,3,4,5,6,7,8,9,10,11,13,14,15,16,18,20,21?

Ни одно из двух допустимых преобразований не уменьшает сумму чисел на карточках (при отсутствии в наборе единичных карт). Потому из набора $(3,4,5)$ нельзя получить числа меньше $3+4+5=12$.
Числа $13,14,15,16,18,21$ получить я не придумал как. Да и получить меньше $17$ нельзя если первым будет "умножение", а не сложение (умножение любых двух чисел из трёх даст не менее $12$ и при этом оставит ещё и добавку в виде третьей карты, а последующие трансформации сумму не уменьшат).
$20$ получить можно, я даже написал как.

[rockclimber]

Dmitriy40 в сообщении #1296911 писал(а):

kotenok gav в сообщении #1296908 писал(а):

А почему нельзя получить числа 1,2,3,4,5,6,7,8,9,10,11,13,14,15,16,18,20,21?

Ни одно из двух допустимых преобразований не уменьшает сумму чисел на карточках (при отсутствии в наборе единичных карт). Потому из набора $(3,4,5)$ нельзя получить числа меньше $3+4+5=12$.

Вы, кажется, что-то путаете (ну или я совсем плохой стал). Вроде бы аппарат умеет складывать?

Ktina в сообщении #1296887 писал(а):

Автомат Григорьева может из двух карточек с натуральными числами $a, b$ сделать либо одну карточку с их суммой, либо $a$ карточек, на каждой из которых написано число $b$.

Суем $3$ и $4$, получаем $7$. И так далее, можно получить любое число, начиная с $6$. Или вы хотите получить все числа с одного раза? Тогда сложнее, конечно.

Ktina в сообщении #1296887 писал(а):

Думаю, надо сперва превратить 3 и 4 в три четвёрки, тогда у нас получится 4, 4, 4, 5.
Затем 4 и 5 превращаем в 5 четвёрок и получаем всего 7 четвёрок. Далее, из двух четвёрок можно сделать 4 четвёрки, таким образом, количество четвёрок увеличится на 2. Повторим эту операцию несколько раз, пока не получим 503 четвёрки. Затем за 502 хода просуммируем их и в итоге получим одну карточку с числом 2012. Как-то так?

Если надо ускориться, то после первого вашего шага надо размножать пятерки, получать десятки, потом двадцатки и т. д.

$(4, 5) \rightarrow (5, 5, 5, 5)$

$(5, 5) \rightarrow (10)$

$(5, 10) \rightarrow (10, 10, 10, 10)$

Идея, думаю, понятна.

[Dmitriy40]

rockclimber

Ktina в сообщении #1296887 писал(а):

Он хочет получить ровно одну
карточку, на которой написано 2012.

Я это понял как то, что у него должно остаться на руках ровно одна карта с нужным числом. Не две, не три, не 100500, а ровно одна. Т.е. надо всунуть в аппарат все лишние карты и "в итоге должен остаться кто-то один".