Старые марафонские задачи с продолжением

[VAL]

Руст писал(а):

Более интересно доисследовать следующие вопросы.
1. Разобраться с тем почему ответы зависят от чётности и нечётности базы системы исчисления d и количества цифр n.

Ответ на этот вопрос представляется очевидным.
Если n нечетно, а d четно, то наибольшее знчение суммы цифр x с отрицательным s(x) отличается от среднего значения суммы всего на 1/2. Ясно, при таком малом отличии шансов на положительное f(x) больше, чем в ситуации, когда сумма цифр номера меньше средней на целую единицу.

Если же n четно, то четность d ни на что особо не влияет.
Шансы на нахождение x с положительным f(x) и отрицательным s(x)
возрастают с ростом d независимо от его четности.
Например, если x состоит из d цифр d-2 и d нулей, то f(x) становится положительным, начиная с d = 12 и остается положительным при бОльших d. Причем отношение числа выигрышей к числу проигрышей с ростом d монотонно возрастает независимо от четности d.

[Руст]

VAL писал(а):

Руст писал(а):

Более интересно доисследовать следующие вопросы.
1. Разобраться с тем почему ответы зависят от чётности и нечётности базы системы исчисления d и количества цифр n.

Например, если x состоит из d цифр d-2 и d нулей, то f(x) становится положительным, начиная с d = 12 и остается положительным при бОльших d. Причем отношение числа выигрышей к числу проигрышей с ростом d монотонно возрастает независимо от четности d.

Мне тоже так казалось, но я не уверен. Вы проверили $d=13$? Может и здесь начинается с несколько большего значения при нечётных d.

[VAL]

Руст писал(а):

VAL писал(а):

Например, если x состоит из d цифр d-2 и d нулей, то f(x) становится положительным, начиная с d = 12 и остается положительным при бОльших d. Причем отношение числа выигрышей к числу проигрышей с ростом d монотонно возрастает независимо от четности d.

Мне тоже так казалось, но я не уверен. Вы проверили $d=13$?

Проверил, что отношение числа выигрышей к числу проигрышей (r(d,x)) монотонно возрастает
при возрастании d от 3 до 500. Правда, с ростом d r(d,x) растет все медленнее. Такое ощущение, что 1.2 оно не превысит никогда.

Цитата:

Может и здесь начинается с несколько большего значения при нечётных d.

Этого вопроса не понял.

[Руст]

VAL писал(а):

Цитата:

Может и здесь начинается с несколько большего значения при нечётных d.

Этого вопроса не понял.

Для нечётных n имеется минимальное значение $g_0(n)$ для чётных d и минимальное значение $g_1(n)$ для нечётных d, начиная с которых существуют n - значное х в d- ичной системе с условием $f(x)s(x)<0$. При нечётных n $g_1(n)>g_0(n), \ g_1(n)\not =g_0(n)+1$ из-за чего приходится определять две нижние границы.
При чётном n по видимому $g_1(n)=g_0(n)+1$ и поэтому достаточно определить $g_0(n)$ (даже если $g_1(n)=g_0(n)-1$ существует единая нижняя граница $g_1(n)$) .
Вообще для больших d и n=2d-2 можно вычислить $f(x_d),x_d=(0,0,..,d-2,d-2,...,d-2)$ асимптотически из функции TOTAL $(1+\frac{d-1}{x})^{d-2}[(d-2)x+1+\frac{1}{x}]^d$ и вычислить
$f(x_d)=d^{2d-2}(\frac{a_1}{\sqrt d}+\frac{a_2}{d}+..)$ (здесь нет зависимости от чётности d и разложение начинается с $d^{-1/2}$ как и для нечейных исходов). Показав положительность $a_1$ получим что начиная с некоторого d выполняется $f(x_d)s(x_d)<0$.

[VAL]

Продолжаю публикацию старых марафонских задач

MM29
Назовем натуральное число "полуквадратным", если приписывая это число само к себе,
получим квадрат натурального числа.
1) существуют ли полуквадратные числа в десятичной системе счисления?
2) для каких g (натуральных, больших 1) в системе счисления с основанием g
существуют полуквадратные числа?

[worm2]

MM29
1) Да, например 82644628100

[Профессор Снэйп]

worm2 писал(а):

MM29
1) Да, например 82644628100

1) Это наименьшее такое число или бывают меньше?
2) Как Вы его нашли?

[Руст]

Это очень простой вопрос (не дотягивает до олимпиадного уровня).
Число x (n- значное) представленное к себе дает
$(g^n+1)x=y^2$
Представим число $g^n+1=tz^2$, где t- произведение простых делителей $g^n+1$ входящих в нечётной степени. Соответственно решение получается $x=ta^2,y=taz$. При этом для сохранения количества цифр необходимо $g^{n-1}\le x<g^n$, т.е. $\frac{g^{n-1}}{g^n+1}\le (\frac az )^2<\frac{g^n}{g^n+1}$.
Это означает $z\sqrt{\frac{g^{n-1}}{g^n+1}}\le a<z$. Если
(1)

$$z\ge \frac{1}{1-\sqrt{\frac{g^{n-1}}{g^n+1}}}$$

существует хотя бы одно решение $a=z-1$.
остаётся только выяснить, когда существует такой делитель числа $g^n+1$.

[worm2]

Профессор Снейп писал(а):

1) Это наименьшее такое число или бывают меньше?
2) Как Вы его нашли?

Да, это наименьшее такое число. Нашёл я его сначала перебором таких чисел $10^n+1$, которые делятся на квадрат какого-нибудь числа: нашёл, что $10^{11}+1$ делится на $11^2$. Потом: $(10^{11}+1)/11^2=826446281$ является числом, которое после умножения на $10^{11}+1$ становится квадратом. Ну, и нужно умножить это число на 100, чтобы формально удовлетворить условию (если бы в условии было: "приписывая, возможно, с некоторым количеством нулей", то этого не надо было делать).

После этого я понял, как решать задачу в общем случае:
Вопрос сводится к тому, существует ли для заданного основания системы счисления $g$ такое n, что $g^n+1$ делится на квадрат какого-нибудь простого числа $p$.
Этот вопрос, действительно, простой.
Для чётного $g$ в качестве n можно взять (g+1): $g^{g+1}+1\equiv 0\pmod{(g+1)^2}$.
Для g=4k-1 подойдёт n=1
Для g=4k+1 подойдёт n=2k+1: $(4k+1)^{2k+1}+1\equiv 0\pmod{(2k+1)^2}$.
Поэтому на вопрос 2) ответ такой: для любого g.

Добавлено спустя 32 минуты 57 секунд:

Наконец-то до меня дошло, о чём писал Руст
Да, в моём решении изъян, связанный с тем, что ещё надо доказать, что можно приписать чётное число нулей... Причём если для случая чётного g и для g=4k-1 можно показать, что всё нормально, то вот случай g=4k+1 нуждается в дополнительном исследовании... Например, $24024_5=1764_{10}$ является квадратом (числа 42), но 240240 --- нет, и ещё одного нуля приписать нельзя

[Руст]

Чтобы VAL не думал, что 2) всё ещё не решён покажем что при любом g существует решение. В качестве z возьмём любой нечётный бесквадратный делитель некоторого $g^k+1$ удовлетворяющей условию (1) (очевидно, что это всегда возможно). Берём $n=zk$, тогда $g^k=-1\mod z\to g^{kz}=-1\mod z^2$ из за нечётности z, Поэтому $a=z-1$ решение.

[worm2]

Для g=5 нашёл решение: $(5^{27}+1)\cdot 5^2/3^4$.
Думаю, что в таком духе всегда можно двигаться и дальше: искать число в виде $A=((4k+1)^{(2k+1)^{2m-1}}+1)\cdot(4k+1)^n/(2k+1)^{2m}$, чтобы число $n=\lfloor 2m\log_{4k+1}(2k+1)\rfloor$ было чётным (в силу иррациональности логарифма это всегда возможно). Тогда в числе $A$ будет ровно $(2k+1)^{2m-1}$ $(4k+1)$-ичных цифр и приписывание самого себя будет эквивалентно умножению на $(4k+1)^{(2k+1)^{2m-1}}+1$.

Добавлено спустя 2 минуты 1 секунду:

Опять не успел. Слишком долго думаю

[VAL]

worm2 писал(а):

Профессор Снейп писал(а):

1) Это наименьшее такое число или бывают меньше?
2) Как Вы его нашли?

Да, это наименьшее такое число.

А что же делать с этими: 13223140496, 20661157025, 29752066116, 40495867769, 52892561984, 66942148761?

Добавлено спустя 3 минуты 12 секунд:

worm2 писал(а):

Для чётного $g$ в качестве n можно взять (g+1): $g^{g+1}+1\equiv 0\pmod{(g+1)^2}$.
Для g=4k-1 подойдёт n=1 Smile
Для g=4k+1 подойдёт n=2k+1: $(4k+1)^{2k+1}+1\equiv 0\pmod{(2k+1)^2}$.
Поэтому на вопрос 2) ответ такой: для любого g.

Добавлено спустя 32 минуты 57 секунд:

Наконец-то до меня дошло, о чём писал Руст Laughing
Да, в моём решении изъян, связанный с тем, что ещё надо доказать, что можно приписать чётное число нулей...

А разве обязательно приписывать четное число нулей?

[Руст]

Это то же решение ( с тем же z) только с $a=4,5,6,7,8,9$ a он взял а=z-1=10.

[VAL]

ММ39

Эта задачка перекликается с задачей №29.
В качестве основания системы счиления рассматриваются натуральные числа,
большие 1.

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

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

[Руст]

Можно взять $g^2+1=(c^2+1)b^2$ при фиксированном с найдётся бесконечно много решений $(g,b), b>c^2+1$ (уравнения типа Пелля) и взять число $x=b(c^2+1)^2$.