Число-автопортрет

[Лазков Йончер]

Придумайте десятизначное число, которое само про себя рассказывает: первая его цифра говорит о том, сколько в нем единиц, вторая говорит, сколько в нем двоек, и так далее, до последней, десятой цифры, которая говорит, сколько в нем нулей.

Существование гарантирую, единственность обещаю.

[Semak]

Красиво.
[size=0]2100010006[/size]

[Шшок]

Мне уже много раз встречалась эта задачка. Очень интересно было бы посмотреть на доказательство единственности решения. Вот его я нигде не встречал, а самому пытаться доказывать - лень.

[Semak]

Навскидку так:

[size=0]1) Ясно, что больше всего в данном числе должно быть нулей.
2) Последний разряд всегда ненулевой (число нулей), значит один из предыдущих разрядов тоже (равен единице в нужной позиции):
0000000108
3) Так как появляется единица в нужной позиции - мы вынуждены подсчитать их в первом разряде. Сначала пробуем обойтись одной единицей:
1000001007
4) Одна единица не катит, так как используется для образования пары с последним разрядом, а единица в первом разряде удваивает число единиц. Значит пробуем с двумя:
2100010006
5) С двумя все замечательно подошло. Если пытаемся вводить третью единицу - придется вводить дополнительный разряд, который мы этой единицей будем считать. А дополнительный разряд автоматом вынуждает нас заменять еще одну ненулевую позицию. То есть один дополнительный ненулевой разряд сокращает число нулей числа на два.
6) Из условия можно вывести лемму: сумма всех цифр числа должна быть равна 10. Если вводить более двух единиц, то условие выполнено не будет. Вообще, нашу лемму можно записать условием:
n1 +*n2 + n3 + n4 + ..... + n9 + n10 = 10

Если отлично от нуля более 4 разрядов, то равенство не сойдется.[/size]

[Шшок]

Навскидку так:

[size=0]1) Ясно, что больше всего в данном числе должно быть нулей.
2) Последний разряд всегда ненулевой (число нулей), значит один из предыдущих разрядов тоже (равен единице в нужной позиции):
0000000108
3) Так как появляется единица в нужной позиции - мы вынуждены подсчитать их в первом разряде. Сначала пробуем обойтись одной единицей:
1000001007
4) Одна единица не катит, так как используется для образования пары с последним разрядом, а единица в первом разряде удваивает число единиц. Значит пробуем с двумя:
2100010006
5) С двумя все замечательно подошло. Если пытаемся вводить третью единицу - придется вводить дополнительный разряд, который мы этой единицей будем считать. А дополнительный разряд автоматом вынуждает нас заменять еще одну ненулевую позицию. То есть один дополнительный ненулевой разряд сокращает число нулей числа на два.
6) Из условия можно вывести лемму: сумма всех цифр числа должна быть равна 10. Если вводить более двух единиц, то условие выполнено не будет. Вообще, нашу лемму можно записать условием:
n1 +*n2 + n3 + n4 + ..... + n9 + n10 = 10

Если отлично от нуля более 4 разрядов, то равенство не сойдется.[/size]

Респект, однако!

[Чива Ротсен]

Не вижу никакого респекта. Правильное решение, конечно, находится за две минуты. Но Сергеево доказательство единственности, мне кажется , хромает. Начиная с фразы "Ясно, что больше всего в данном числе должно быть нулей". Ясно-то это, может, и ясно. Но доказательство обычно требует чего-то более строгого.

[Мысли вслух]

Не вижу никакого респекта.

Представляю твое серьезное лицо, когда ты это писал. Попроще, Ротсен, попроще ))

[Шшок]

Не вижу никакого респекта. Правильное решение, конечно, находится за две минуты. Но Сергеево доказательство единственности, мне кажется , хромает. Начиная с фразы "Ясно, что больше всего в данном числе должно быть нулей". Ясно-то это, может, и ясно. Но доказательство обычно требует чего-то более строгого.

Ну вот... каждый может Семака обидеть... А нет бы предложить свой вариант.

[Dendr]

Пока пытаюсь надежно доказать единственность...

Интересно поставить задачу иначе. Точнее, другую задачу, на основе этой.
Рассмотрим числа в k-ичной системе. Назовем число N(k) суперчислом, если оно удовлетворяет следующим свойствам:
1) N - k-значное, т.е. k^(k-1)<=N<=k^k-1.
2) Первая его цифра слева (т.е. наибольший разряд) равна числу единиц в k-ичной записи, вторая - двоек и т.д... K-я (последняя) - количеству нулей.

Введем функцию f(k), которая определяет число суперчисел в k-ичной системе счисления.
Легко подсчитать, что f(2)=0, f(3)=0, f(4)=1 (N(4)=2101).

Задача - найти минимальное k, для которого f(k)<1. Либо - доказать, что для всех k>4 f(k)=1.

[Dendr]

Вот и доказательство - для исходной задачи.
Итак.
1) Сумма всех цифр числа должна равняться количеству цифр - это, надеюсь, очевидно.
Пусть число записывается условно следующим образом (не поленюсь записать все цифры):
n1-n2-n3-n4-n5-n6-n7-n8-n9-n10
Т.е., n1+n2+...+n10=10
Также и 1*n1+2*n2+...9*n9=10. (надо ли объяснять, почему?)

2) Рассмотрим, "кусок" числа:
-n5-n6-n7-n8-n9-
Чему равна сумма этих цифр? Очевидно, она не превышает единицы.
Докажем это. Допустим, что она равна двум.
Минимальный случай: ****20000*. То есть, среди прочих цифр есть две пятерки. Т.е., сумма цифр не меньше 12.
Не годится.
Может ли сумма быть нулем? Нет: ****00000* - означает, что где-то в этом ряду будет стоять единица.

Вывод: на куске от n5 до n9 стоит одна единица и 4 нуля. Пусть единица стоит на p-м месте. Тогда на последнем месте будет именно стоять число p.
(Докажем это. Пусть, у нас число ****10000*. Где-то должна стоять пятерка. Ясно, что не на 2-м и т.д. месте - иначе сумма будет больше 10. Пусть - на первом, тогда четверка на 10-м, единица на 4-м.
5**1100004. Сумма - уже больше 10. Перестановка единицы на следующие позиции только ухудшает. Ч.т.д.)

Имеем два равенства. Важно, что других вариантов набора цифр больше нет.
n1+n2+n3+n4+1+p=10 (np=1, n10=p)
n1+2*n2+3*n3+4*n4+p*1=10
Вычитаем из второго первое:
n2+2*n3+3*n4-1=0, или
n2+2*n3+3*n4=1.
Следовательно (т.к. числа n_ неотрицательные) n3=n4=0, т.е. n2=1. Где-то есть одна двойка, и нет вообще троек и четверок.
Тогда:
n1+1+0+0+1+p=10,
n1+p=8.
Очевидно, что именно цифра n1 - должна быть равна двум. Тогда p=6.
Таким образом - единственный ответ: 2100010006.

Кстати... таким же образом доказывается единственность "суперчисла" для общего случая.
Если k=2*m.
Среди цифр с позиции m до k-1 тоже ровно 1 единица, стоит на p-м месте - все повторяется
Если k=2*m+1. Может ли на m-м месте быть двойка (или единица плюс единица где-то "позже")? Видимо - нет. Иначе сумма превысит k
n1+n2+n3+...+1+...+p=k (np=1, nk=p)
n1+2*n2+3*n3+...+p*1+...+0=k

Вычитаем: n2+2*n3+3*n4+...(s-1)*ns=1. Следовательно n3=n4=...=0,
n2=1.
Тогда ничего не остается, чтобы n1=2.
2+1+0+...+1+0+...+p=k, p=k-4.
Т.е. "суперчисло" в k-ичной системе счислений единственно и выглядит так (p=k-4):
210...01000p
Это верно, видимо, для k не меньше 8 (фактически - и для 7). При меньших - нужен отдельный алгоритм (или простой перебор)

[SVM]

Прикольно видеть, как работают руки вместо головы у людей. Ну, к примеру: 2100010006. Или, скажем, 100000008. Да мало ли ...

[Азарапетыч]

скажем, 100000008. Да мало ли ...

100000008 - не годится. Восьмерка одна есть в числе, а восьмая цифра нуль.


2100010006 - и правда единственное решение.

[SVM]

Да, поторопился я. Задача оказалась серьезнее, чем показалась.