перебор

[Димаsick]

На столе лежат 4 карточки, на которых написаны нули. За один ход разрешается менять любую одну карточку на карточку с большей на 1 или меньшей на 1 цифрой (меньшей для 0 считаем 9, а большей для 9 считаем 0). За какое наименьшее число ходов можно получить на карточках все натуральные числа от 0001 до 9999?

[Dandan]

9999

[Nxx]

А если изменить условие,

Например, если одну и ту же карточку нельзя трогать два раза подряд?

[gris]

А вы уверены, что можно за 9999 раз?

Это значит, что можно получить такую перестановку чичел от 0001 до 9999, что 0001 стоит на первом месте и у двух соседних чисел три позиции одинаковы, а одна отличается на 1 (учитывая случай 0-9).

1 2 3 4 5 6 7 8 9 19 18 17 16 15 14 13 12 11 10 20 21.... 99 98 97 96 95 94 93 92 91 191 ... я не уверен, что этот алгоритм сработает.

А какой у вас алгоритм?

[Димаsick]

...

[Dandan]

gris писал(а):

А вы уверены, что можно за 9999 раз?

Это значит, что можно получить такую перестановку чичел от 0001 до 9999, что 0001 стоит на первом месте и у двух соседних чисел три позиции одинаковы, а одна отличается на 1 (учитывая случай 0-9).

1 2 3 4 5 6 7 8 9 19 18 17 16 15 14 13 12 11 10 20 21.... 99 98 97 96 95 94 93 92 91 191 ... я не уверен, что этот алгоритм сработает.

А какой у вас алгоритм?

да такой же. А почему не уверены, что он сработает? По индукции просто докажите, что перебрать все числа длины n можно начиная с любого числа (не обязательно 00..0)

[gris]

В какой-то момент может оказаться, что мы можем перейти только к числу, которое уже было. И потребуется больше, чем 9999 ходов.

ну вот продолжу

191 192...199 190 180 ... 189 179... 170 160 ... 119 118 ...110
100 101 ... 109
209

Вроде бы получается. То есть мы с любого места можем перебрать все варианты для n правых карточек за $10^n$ шагов, а потом добавить ещё одну карточку.

А в чём подвох? Не может же быть всё просто.

[Димаsick]

Если после 91 переход к 191, то когда же и как вернуться к 90?

[Хорхе]

Димаsick писал(а):

Если после 91 переход к 191, то когда же и как вернуться к 90?

Никто же не запрещает подумать! Ну вставьте Вы туда 90 и 190. И дальше чуть подправьте.

[Димаsick]

Уже думал. Если бы додумался - не спрашивал бы. Общего метода все еще не вижу. Если это так просто - может, кто-нибудь объяснит?
Вопрос остается открытым.

[gris]

Я немного ошибся. Конечно, там должен быть еще один шаг 97 96 95 94 93 92 91 90, а потом уже 190 191 199.
Серия "возвратно-поступательных" шагов должна охватывать все числа по одному из очередной сотни.
После этого делается переход на следующую сотню, потом на тысячу.

[Димаsick]

Теперь все логично и понятно! Спасибо!