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

[worm2]

MM29

VAL писал(а):

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

VAL писал(а):

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

Стормозил Конечно, можно умножать на квадрат любого числа, а не только на квадрат основания системы счисления
Однако, месье знает толк в извращениях (это я про себя)
При этом сильно упрощаются мои потуги доказательства для g = 4k+1. Получается явная формула:

$$((4k+1)^{2k+1}+1)\frac{4k^2}{(2k+1)^2}$$

.
(вместо $4k^2$ в числителе последней дроби можно поставить квадрат меньшего числа, лишь бы только дробь оказалась не меньше 1/g).

[VAL]

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

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

Угу.

А теперь обещанное продолжение:
Для каких g существуют полукубические числа?
В частности, существуют ли они при g = 10 ?

[Руст]

Если речь всё ещё идёт о двузначных для g=10, то очевидно не существует $101$ - простое.

[VAL]

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

Если речь всё ещё идёт о двузначных для g=10, то очевидно не существует $101$ - простое.

Если бы речь шла о двузначных, я бы и не стал эту речь заводить

[Руст]

Представим

$$g^n+1=\prod_i p_i^{k_i}$$

и выделим сомножители

$$a=\prod_{i|k_i=1\mod 3}p_i, \ b=\prod_{i|k_i=2\mod 3}p_i, \ c=\prod_i p_i^{[k_i/3]}.$$

Тогда n- значное число х полукубично тогда и только тогда, когда $x=a^2bd^3, y=abcd$ и $\frac{g^{n-1}}{g^n+1}\le\frac ab (\frac{d}{c})^3<1$.
Здесь единственное что можно доказать это конечность полукубических чисел при каждом фиксированном g. Однако из-за не эффективных оценок нельзя сказать при заданном g до какого n надо проверять для того, чтобы убедится что дальше решений нет.

[VAL]

ММ41. Промежуточные итоги

Напомю условие.

VAL писал(а):

Двое играют в такую игру:
Игроки A и B выставляют на кон по банкноте одинакового достоинства, на каждой из которых имеется семизначный номер. Игроки сравнивают соответствующие (стоящие в одинаковых позициях) цифры номеров. Если i-я цифра на банкноте игрока A больше i-й цифры на банкноте B, то A получает зачетный балл, и наоборот. Побеждает (и забирает банкноту противника) тот, кто наберет больше зачетных баллов. В случае равенства баллов игроки остаются при своих.
Например, если у A номер банкноты 4987200, а у B - 4007311, то со счетом 3:2 победит B.
Какую наименьшую сумму цифр может иметь номер банкноты, для которой математическое ожидание выигрыша положительно?
_________________

Ответ: 31

Вот полный (с точностью до порядка цифр) перечень номеров с суммой цифр 31 и положительным мат. ожиданием выигрыша:
[0 0 0 6 7 9 9], 39689
[0 0 0 6 8 8 9], 142049
[0 0 0 7 7 8 9], 266685
[0 0 1 7 7 7 9], 32563
[0 0 0 7 8 8 8], 370665
[0 0 1 6 8 8 8], 20097
[0 0 1 7 7 8 8], 112813
После каждого номера x указана разность между W(x) ( количеством номеров, у которых x выигрывает) и L(x) (количеством номеров, которым x проигрывает).

Разумеется (законы сохранения и симметрию никто не отменял), раз есть выигрышные номера номера с суммой 31, должны быть и проигрывающие номера с суммой 32. Вот самый проигрышный:
[1 1 1 2 9 9 9], -370665.

Перейдем к обобщениям задачи.

Пусть $ x = [x_1 x_2 ... x_n] $ - n-значный номер в d-ичной системе счисления.
Назовем номер x парадоксальным, если $ x = 2(x_1+x_2+ ... +x_n) < n(d-1) $. $ R(x) = \frac{W(x)}{L(x)} > 1 $ назовем коэффициентом парадоксальности, а $ D(x) = n(d-1) - 2(x_1+x_2+ ... +x_n) $ - степенью парадоксальности.

Вот некоторые выводы по обобщенной задачке (из коих лишь часть доказаны, а остальные являются гипотезами):

1. Парадоксальные номера имеются для любых d > 7.
2. Степень парадоксальности может быть сколь угодно большой.
3. Степень парадоксальности D достигается, начиная с d = 4D+4 и при всех больших d (за естественным исключением случая d - нечетно, D - четно).
4. Наилучший коэффициент парадоксальности достигается для номеров вида [d-2 d-2 ... d-2 0 0 ... 0] (нулей меньше половины).
5. Двойственным образом номера вида [d-1 d-1 ... d-1 1 1 ... 1] (единиц больше половины, D(x) < 0) являются наиболее проигрышными.

[VAL]

ММ57

Назовем многоугольник ординарным, если он выпуклый и никакие 3 его диагонали не пересекаются в одной точке внутри многоугольника.
Пусть n - число сторон ординарного многоугольника.

1) На сколько частей разбивают диагонали ординарный многоугольник?
2) Верно ли, что при фиксированном n среди частей, на которые разбивается диагоналями ординарный многоугольник всегда одно и тоже число треугольников?
3) При каком минимальном n в разбиении ординарного многоугольника может получиться восьмиугольник?
4) Существует ли ординарный многоугольник, в разбиении которого получается больше пятиугольников, чем треугольников?
5) При каких n существуют разбиения ординарного многоугольника, содержащие только треугольники и четырехугольники?

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

[VAL]

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

Здесь единственное что можно доказать это конечность полукубических чисел при каждом фиксированном g.

Не понял, откуда следует конечность полукубических чисел при фиксированным g.

Цитата:

Однако из-за не эффективных оценок нельзя сказать при заданном g до какого n надо проверять для того, чтобы убедится что дальше решений нет.

А откуда вытекает, что начиная хоть с какого-то n $ g^n+1 $ не может иметь подходящего разложения?

[Руст]

Сошлёмся к не доказанной $abc$ гипотезе c $a=g^n,b=1,c=g^n+1$. Согласно нему имеется только конечное множество (для этого случая они уже просчитаны, только не доказано что их больше нет) таких, что $rad(c)<c^{2/3}$, что необходимо для вышеуказанного разложения. Это доказывает конечность полукубических чисел при каждом $g$.
На самом деле этот результат можно получить уже из доказанных теорем теории чисел. Просто я не помню ссылок.

[VAL]

ММ45-46

Функция f(n) задается так:
Натуральные числа от 1 до n расставлены по кругу.
Начинаем отмечать числа 1, 2, 4, 7, 11, 16 и т.д.
Значением f(n) будет то число, которое первым будет отмечено повторно.

1) Доказать, что существует бесконечно много n, для которых f(n) = 500501.
2) Найти явную формулу для $f(3^k)$.
3) Описать все такие n, для которых f(n) определяется на n+1-вом шаге, (т. е. все числа будут отмечены по разу, прежде чем какое-то будет отмечено повторно). Найти явное выражение f(n) для таких n.
4) Доказать, что на множестве нечетных простых чисел f(n) инъективна (т.е. f(p) не может равнятся f(q), если p и q - различные нечетные простые числа).
5) Верно ли, что f(n) сюръективна, т.е. для любого натурального m найдется n такое, что f(n) = m? В частности существует ли n такое, что f(n) = 917?
6) Верно ли, что существует бесконечно много таких n, для которых f(n) = n?

[Руст]

Володя!
Здесь всё это уже обсуждалось. Получилось так, что maxal просил моё мнение об этом, потом я выложил сюда.

[VAL]

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

Володя!
Здесь всё это уже обсуждалось. Получилось так, что maxal просил моё мнение об этом, потом я выложил сюда.

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

PS: А ММ57 не обсуждалась? А то все молчат...

[Руст]

VAL писал(а):

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

Здесь я дал полное решение. Ответы на 5) сюръективна бесконечнократно. 6) верно.
Однако так и не нашёл эту задачу. Если уже потерялась задача могу выложит более короткое решение.

[Руст]

VAL писал(а):

ММ45-46

Функция f(n) задается так:
Натуральные числа от 1 до n расставлены по кругу.
Начинаем отмечать числа 1, 2, 4, 7, 11, 16 и т.д.
Значением f(n) будет то число, которое первым будет отмечено повторно.

1) Доказать, что существует бесконечно много n, для которых f(n) = 500501.
2) Найти явную формулу для $f(3^k)$.
3) Описать все такие n, для которых f(n) определяется на n+1-вом шаге, (т. е. все числа будут отмечены по разу, прежде чем какое-то будет отмечено повторно). Найти явное выражение f(n) для таких n.
4) Доказать, что на множестве нечетных простых чисел f(n) инъективна (т.е. f(p) не может равнятся f(q), если p и q - различные нечетные простые числа).
5) Верно ли, что f(n) сюръективна, т.е. для любого натурального m найдется n такое, что f(n) = m? В частности существует ли n такое, что f(n) = 917?
6) Верно ли, что существует бесконечно много таких n, для которых f(n) = n?

Решил привести полное решение.
Очевидно, что отмечаются номера $\frac{k(k+1)}{2}+1\mod n$. Здесь всвязи с нумерацией от 1 до n, а не от 0 до n-1, вычеты по модулю имеют такую же нумерацию, т.е. при делении числа a на n считается $a\mod n =n$,
1) Число 500501 первый раз отмечается при $k=1000, n>500500$. Если оно отмечается и при втором походе, то $n=\frac{k(k+1)}{2}-500500$ для некоторого k. Если $k>500500$ то это первое число отмеченное во втором круге а значит $f(\frac{k(k+1)}{2}-500500)=500501,k>500500$.
Удобнее работать с нечётными числами $s=2k+1$, тогда отмечаемые числа есть $\frac{s^2+7}{8}\mod n$. Пусть отмечается некоторое число первый раз ходом $s_1=2k_1+1$ и во второй раз $s_2=2k_2+1$. Тогда $(s_2-s_1)(s_2+s_1)=8an$. Тогда одно из чисел равно $2ml_1$ другое $2\frac{2n}{m}l_2$ для некоторого нечётного делителя m числа n. Соответственно $s_2=ml_1+\frac{2n}{m}l_2,s_1=|ml_1-\frac{2n}{m}l_2|$. Однако, чтобы $s_2$ было первым, отмечаемым второй раз ходом должно быть $l_1=l_2=1$. Отсюда получается явный вид $f(n)=\frac{s^2+7}{8}\mod n, \ s=m+\frac{2n}{m}$, где нечётный делитель m выбирается из условия минимальности $|2\ln m -\ln n|$ среди всех нечётных делителей числа n.
2) В частности для $n=3^k$ получается $m=3^{[(k+1)/2]}, s=3^{[(k+1)/2]}+2*3^{[k/2]}, f(n)=\frac{3^{2[k/2]}+7}{8}.$
3) В этом случае $m=1$ единственный нечётный делитель числа n, т.е. $n=2^k$. Соответственно для $n=1,f(1)=1$ а при $k>0$ $s=2^{k+1}+1,f(n)=1+\frac n2$.
4) Если n нечётное простое число, то $m=n,s=n+2,f(3)=1, f(p)=\frac{pl+11}{8}, l=p+4\mod 8, p>3$
Если не наврал, для 5) и 6) вначале давалось решение при предположении бесконечного количества простых значений квадратного многочлена, а потом получалось следующие решения.
Введём нечётные числа $x=s_2,y=s_1$, тогда
(1) $x^2-y^2=8n$ и
$8f(n)=7+x^2-k(x^2-y^2)$, где $k=[\frac{x^2}{8n}]=1+[\frac{y^2}{8n}]\in N$.
решим в начале задачу
6). Если $k=1$ то $8n=y^2+7=x^2-y^2$. В этом случае автоматический x - есть подходящее (минимальное нечётное число) и $(x_i+\sqrt 2 y_i)=(3+\sqrt 2)(3+2\sqrt 2)^i$. Это определяет автоматический некоторую бесконечную серию $n_i$ удовлетворяющую рекурентному соотношению $n_{i+1}=34n_i-n_{i-1}$ например $n_0=2,n_1=11$.
5) На самом деле здесь нет сюръективности..
Пусть m=f(n) фиксированное число, тогда $8m-7=ky^2-(k-1)^x^2$.
Случай $k=1$ соответствует $8f(n)=2y^2-x^2+7$. Bообще, если есть одно решение с $k=2$ и $7-8f(n)\not =x^2-2y^2$, то таких решений бесконечно, так как они не попадут случаю с $k=1$. Вообще говоря решение имеется не при всех $m=f(n)$.

[VAL]

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

VAL писал(а):

ММ45-46

Функция f(n) задается так:
Натуральные числа от 1 до n расставлены по кругу.
Начинаем отмечать числа 1, 2, 4, 7, 11, 16 и т.д.
Значением f(n) будет то число, которое первым будет отмечено повторно.

1) Доказать, что существует бесконечно много n, для которых f(n) = 500501.
2) Найти явную формулу для $f(3^k)$.
3) Описать все такие n, для которых f(n) определяется на n+1-вом шаге, (т. е. все числа будут отмечены по разу, прежде чем какое-то будет отмечено повторно). Найти явное выражение f(n) для таких n.
4) Доказать, что на множестве нечетных простых чисел f(n) инъективна (т.е. f(p) не может равнятся f(q), если p и q - различные нечетные простые числа).
5) Верно ли, что f(n) сюръективна, т.е. для любого натурального m найдется n такое, что f(n) = m? В частности существует ли n такое, что f(n) = 917?
6) Верно ли, что существует бесконечно много таких n, для которых f(n) = n?

Решил привести полное решение.

[...]

Спасибо!
Хотя понял пока не все.
Буду разбираться.

Добавлено спустя 48 минут 59 секунд:

VAL писал(а):

ММ57

Назовем многоугольник ординарным, если он выпуклый и никакие 3 его диагонали не пересекаются в одной точке внутри многоугольника.
Пусть n - число сторон ординарного многоугольника.

1) На сколько частей разбивают диагонали ординарный многоугольник?
2) Верно ли, что при фиксированном n среди частей, на которые разбивается диагоналями ординарный многоугольник всегда одно и тоже число треугольников?
3) При каком минимальном n в разбиении ординарного многоугольника может получиться восьмиугольник?
4) Существует ли ординарный многоугольник, в разбиении которого получается больше пятиугольников, чем треугольников?
5) При каких n существуют разбиения ординарного многоугольника, содержащие только треугольники и четырехугольники?

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

К сожалению, эта задачка не слишком заинтересовала форумчан (версия о том, что она оказалась им "не по зубам", представляется мне менее состоятельной).

Что ж...
Привожу решение и обещанное продолжение.

Решение

Введем некоторые обозначения.
Диагонали, соединяющие вершины многоугольника через одну, будем называть
"короткими", а диагонали соединяющие противоположные вершины при четном n
и наиболее близкие к противополжным при нечетном n - "длинными".
(Таким образом и у четырехугольника, и у пятиугольника все диагонали являются
короткими и длинными одновременно).

1) Первый пункт задачи №57 представляет собой широко известную задачу.
Наиболее изящный способ решения - применить соотношение Эйлера для плоской
укладки связного графа. Наш многоугольник задает такую укладку, если
в качестве вершин графа рассматривать вершины и точки пересечения диагоналей
многоугольника, а в качестве ребер - стороны исходного многоугольника и
отрезки, на которые разбиваются диагонали.
Обозначим через В, Р и Г количества вершин, ребер и граней графа.
По формуле Эйлера В + Г - Р = 1 (внешняя грань, не являющаяся частью разбиения,
нас не интересует).
Поскольку каждая точка пересечения диагоналей находится в биективном
соответствии с каждой (неупорядоченной) четверкой вершин многоугольника,
количество точек пересечения равно C(n,4). Поэтому В = С(n,4) + n.
Каждая диагональ разбивается на отрезки, количество которых на один больше
числа точек пересечения, лежащих на этой диагонали. При этом каждая точка
пересечения принадлежит двум диагоналям, а всего диагоналей - n(n-3)/2.
Поэтому Р = 2*С(n,4) + n(n-3)/2 + n (последнее слагаемое соответствует
сторонам многоугольника).
Таким Образом,

$$ \Gamma(n) = P(n) - B(n) + 1 = C(n,4) + n(n-3)/2 + 1 = (n - 1)(n - 2)(n^2 - 3n + 12)/24. $$

2) Нет.
Пример:
В разбиении семиугольника с вершинами A(-5;0), B(5;0), C(7;3), D(7;6), E(4;7),
F(-4;8), G(-7;3) участвуют 32 треугольника.
Если же вторую координату вершины C заменить на 4, то треугольников станет 35.

3) При n = 9.
Пример подходящего девятиугольника: A(-50;0), B(50;0), C(70;35), D(70;60),
E(42;72), F(3;80), G(-40;80), H(-60;56), I(-70;30).
Остается показать, что восьмиугольник не может возникнуть при меньшем n.
Т.к в формировании одной части разбиения участвует не более двух диагоналей,
выходящих из одной вершины, и при этом каждая диагональ инцидентна двум
вершинам, восьмиугольник не может возникнуть при n < 8.
Допустим, что восьмиугольник возникает при разбиении восьмиугольника.
Ясно что, части разбиения, примыкающие к сторонам исходжного многоугольника,
являются треугольниками.
Назовем диагонали, на пересечении которых образуется восьмиугольник,
формирующими.
Очевидно, что короткие диагонали не могут быть формирующими (легко видеть,
что части разбиения, примыкающие к коротким сторонам, не более чем пятиугольны)
Тогда из каждой вершины должны выходить две соседние диагонали (одна длинная и
одна "средняя"), формирующие восьмиугольник. При этом каждая такая диагональ
должна пересекать все формирующие диагонали, не имеющие с ней общих вершин.
Пусть ABCDEFGH исходный многоугольник. Длинная диагональ AE (как и любая
длинная диагональ) обязана быть формирующей. Не нарушая общности рассуждений,
можно считать, что AF - вторая формирующая диагональ, инцидентная A.
Тогда дигональ EH тоже обязана быть формирующей, поскольку дагональ BE не
пересекает AF. Остальные 5 формирующих диагоналей должны пересекать дигональ
AE. Но это невозможно, поскольку шесть концов этих диагоналей ( по два в
точках B, C, D) лежат по одну сторону от AE и лишь четыре конца (два в точке G
и по одному в точках F и H) - по другую.
Таким образом, восмиугольник не может возникать в разбиении восьмиугольника.

4) Нет.
Легко видеть, что сумма количеств углов всех многогугольников разбиения
зависит только от n. Обозначим эту сумму через Y(n). К каждой вершине исходного
многоугольника примыкает n-2 угла, а к каждой точке пересечения диагоналей - 4.
Поэтому $ Y(n) = 4*C(n,4) + n(n-2) $.
$ Y(n) - 4*\Gamma(n) = -(n-2)^2. $
Каждый m-угольник разбиения с числом сторон, большим 4, привносит в эту
сумму m-4 единицы. И лишь треугольники дают "отрицательный вклад" (по -1 на
каждый треугольник). Но Y(n) - 4*Г(n) является отрицательным при любом
допустимом n. Поэтому количество треугольников превышает в разбиении
суммарное количество всех многоугольников с чмслом сторон, превышающем 4, и,
в частности, пятиугольников.

5) При n = 3 и n = 4.
Короткие диагонали высекают внутри исходного многоугольника многоугольник с
таким же количеством сторон. Легко видеть, что все части разбиения, лежащие
вне этого многоугольника, являются треугольниками, а количество таких
треугольников равно n(n-3).
Применим рассуждение, аналогичное приведенному в пункте 4, к n-угольнику,
высекаемому короткими диагоналями:

$$ Y_1(n) = Y(n) - 3n(n-3), \Gamma_1(n) = \Gamma(n) - n(n-3), Y_1(n) - 4*/ _1(n) = n - 4. $$

Поэтому, начиная с n, равного 5, внутри многоугольника, ограниченного короткими
диагоналями, обязаны присутствовать части разбиения, имеющие более четырех
сторон.


Обсуждение

Ситуация третьего пункта задачи легко обощается.
Если m нечетно, то m-угольник может (но не обязан) возникать в разбиении
регулярного n-угольника, начиная с n = m.
Если же m четно, то m-угольник может быть частью разбиения, начиная с n = m+1.

Из рассуждения, приведенного в пятом пункте, следует, что начиная с n = 5,
в разбиении регулярного многоугольника появляются многоугольники, имеющие
больше четырех сторон. Не сложно показать, что среди них всегда будут
пятиугольники. При n = 5 пятиугольником разбиения будет сам многоугльник,
высекаемый короткими диагоналями. А для бОльших значений n не менее n/2
пятиугольников будут примыкать с внутренней стороны к коротким диагоналям.

А теперь некоторые из вопросов, ответы на которые не столь прозрачны.

1) Верно ли, что, начиная с некоторого n, в разбиении ординарного многоугольника обязательно будут присутствовать шестиугольники, семиугольники...?

2) Легко видеть, что с ростом n число средее число сторон одной части разбиения стремится к 4. Следует ли отсюда, что, начиная с некоторого n, число четырехугольников в разбиении ординарного многоугольника начнет превышать число треугольников?

3) Очевидно, что при четных n, бОльших 4, правильный многоугольник не является ординарным. Верно ли, что при нечетных n правильные многоугольники всегда ординарны?

4) Степенью неординарности выпуклого n-угольника назовем число C(n, 4) - v, где v - число точек пересечения диагоналей данного многоугольника. Верно ли, что четных n правильные n-угольники всегда имеют наибольшую возможную при данном n степень неординарности?