Ну очень интересное число

[Ktina]

Найдите наименьшее натуральное n со свойством: любое число из чисел 1, 2, 3,..., 9,10 может быть представлено как либо цифра числа n, либо сумма нескольких последовательных цифр числа n.

[_Ivana]

$1234$. Без компа и сразу. Кто меньше?

[venco]

А разве в многоточии не подразумевается 8?

[_Ivana]

8 тоже можно набрать, просто я не уделил достаточно внимания фразе "сумма нескольких последовательных цифр".

-- 15.03.2013, 18:38 --

Если можно суммировать только последовательные цифры, то с компом получилось... несколько другое число Также читерским методом легко находятся все такие числа (точнее, их конечное подмножество, не содержащее нулей, любой элемент которого можно любым образом дополнить нулями - и получаем все множество чисел, удовлетворяющее условию).

[Ktina]

_Ivana в сообщении #696150 писал(а):

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

Какое, всё-таки, счастье, что природа (или Бог, не суть важно) не одарила меня способностями к программированию.
Решила без компа и получила море удовольствия.

Уже можно давать ответ?
Или дать подумать тем, кто без компа хочет решить?

-- 15.03.2013, 20:58 --

_Ivana в сообщении #696150 писал(а):

и получаем все множество чисел, удовлетворяющее условию).

Оно счётно, даже если без нулей.

[hippie]

11134?

А давайте "заторим" число, т.е. первую и последнюю цифру тоже будем считать соседними. (Т.е. последняя и первая или последняя, первая и вторая или предпоследняя, последняя и первая и т.д. цифры тоже будут соседними.)
При каком наименьшем n любое число из чисел 1, 2, 3, ..., 12, 13 может быть представлено как либо цифра числа n, либо сумма нескольких последовательных цифр (заторенного!) числа n?

[Ktina]

hippie в сообщении #696289 писал(а):

11134?

Верно

-- 15.03.2013, 21:24 --

hippie в сообщении #696289 писал(а):

А давайте "заторим" число...

Давайте.
Задача становится ещё интереснее.

-- 15.03.2013, 21:29 --

hippie в сообщении #696289 писал(а):

При каком наименьшем n любое число из чисел 1, 2, 3, ..., 12, 13 может быть представлено как либо цифра числа n, либо сумма нескольких последовательных цифр (заторенного!) числа n?

Так тот же ответ получается -- 11134, вроде.

-- 15.03.2013, 21:32 --

Или я условие не поняла.

-- 15.03.2013, 21:33 --

Тогда вообще число 1 подходит -- заториваем его и представляем любое натуральное число как сумму последовательных единичек.

[_Ivana]

Тогда с условием отсутствия "наложений" - повторов одних и тех же позиций разрядов в суммировании. На задачу hippie комп дает число меньше 11134. Напишу в оффтопе, дабы желающие могли честно подумать

(Оффтоп)

1264

Заторенное от 1 до 10

(Оффтоп)

1135

от 1 до 15

(Оффтоп)

11148

от 1 до 20

(Оффтоп)

111377

[Руст]

hippie в сообщении #696289 писал(а):

11134?

А давайте "заторим" число, т.е. первую и последнюю цифру тоже будем считать соседними. (Т.е. последняя и первая или последняя, первая и вторая или предпоследняя, последняя и первая и т.д. цифры тоже будут соседними.)
При каком наименьшем n любое число из чисел 1, 2, 3, ..., 12, 13 может быть представлено как либо цифра числа n, либо сумма нескольких последовательных цифр (заторенного!) числа n?

Несколько лет назад я задавал такого типа вопрос. Расставить по кругу n натуральных чисел так, чтобы все суммы по кругу подряд (если не полный круг) были разными и все суммы от 1 до $n(n-1)+1$ (последнее для суммы по полному кругу) встречались.
Это известная и очень не простая задача.

[_Ivana]

А последовательности при увеличении количества содержащих сумм растут не так быстро...
от 1 до 25

(Оффтоп)

112885

от 1 до 30

(Оффтоп)

1113879

[hippie]

Руст в сообщении #696315 писал(а):

Несколько лет назад я задавал такого типа вопрос. Расставить по кругу n натуральных чисел так, чтобы все суммы по кругу подряд (если не полный круг) были разными и все суммы от 1 до (последнее для суммы по полному кругу) встречались.

Это я и имел в виду .

Впервые столкнулся с этой задачей около 25 лет назад. Тогда в журнале "Наука и Жизнь" предлагалось найти все циклические расстановки шести чисел, дающие суммы от 1 до 31. Задача предлагалась как программистская, но оказалось, что перебор достаточно простой, и все указанные расстановки находятся вручную.

Обсуждая эту задачу с сокурсником, мы за час нашли алгоритм, позволяющий строить требуемые расстановки чисел, при условии, что $n-1$ — степень простого числа. (В предложенном мной выше варианте $n-1=3^1.$) Решение оказалось очень простым (и, практически, очевидным), хотя и не школьным (требовало знаний алгебры и аналитической геометрии на уровне первого курса МатФака). (Правда, по сравнению с "предложенной" задачей оно давало "какие-то" расстановки, но не обязательно минимальную!)

Позже, в 2002 году, я краем уха слышал, что при других n требуемых расстановок чисел не существует.

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

Или я условие не поняла.

-- 15.03.2013, 21:33 --

Тогда вообще число 1 подходит -- заториваем его и представляем любое натуральное число как сумму последовательных единичек.

А это я накосячил. Нужно было подробнее написать.

Каждая цифра может использоваться не больше одного раза.
По-другому:
Десятичную запись числа можно разрезать (вертикальным разрезом) на 2 части, и поменять местами. После этого, в получившихся числах, для каждого целого числа от 1 до 13, выбрать несколько идущих подряд цЫфирок (возможно — все) так, чтобы их сумма равнялась нужному числу.

[Руст]

hippie в сообщении #696405 писал(а):

Позже, в 2002 году, я краем уха слышал, что при других n требуемых расстановок чисел не существует.

[/quote]
Заблуждаетесь. Доказано, что решения существует для всех таких $n>2$, что $n-1$ является степенью простого числа.
Решения представляются через проективную плоскость в поле Галуа с $n-1$ элементами. Но не доказано, что для других n отсутствует.
Я на компьютере нашел все решения для $n\le 20$. maxal дополнил в извеестных числовых последовательностях OES эти решения.

[hippie]

А известны ли примеры циклических конечных проективных плоскостей (порядка $(n-1)$), не получающихся факторизацией $GF((n-1)^3)$ по прямым проходящим через 0?