Число решений

[RIP]

Пусть $\{F_x\}_{x=1}^\infty$ --- последовательность натуральных чисел (я не отношу 0 к натуральным числам ), такая что при любом $x\in\mathbb N$ выполнено $\frac{F_{x+1}}{F_x}\geqslant1+\varepsilon$, где $\varepsilon>0$, $k,m_1,\ldots,m_k\in\mathbb N$. Докажите, что для любого $N\in\mathbb N$ кол-во решений уравнения

$$m_1F_{x_1}+\ldots+m_kF_{x_k}=N$$

(уравнение относительно $x_1,\ldots,x_k\in\mathbb N$) не превосходит некоторой постоянной, зависящей только от $k$ и $\varepsilon$.

[neo66]

Количество решений не превосходит $k!(\log_{1+\varepsilon}(m_1+ \dots +m_k) +1)$.

[нг]

neo66, Ваша оценка очевидно зависит от $m_i$, в то время как RIP предлагал доказать существование оценки, зависящей только от $k$ и $\varepsilon$.

[neo66]

Я это подозревал.

[RIP]

Да, константа не должна зависеть от $m_i$, но мне всё-таки интресно, как получается

neo66 писал(а):

Количество решений не превосходит $k!(\log_{1+\varepsilon}(m_1+ \dots +m_k) +1)$.

[maxal]

У меня получилась другая оценка - в грубой форме
$(1+\log_{1+\varepsilon} \sum m_i)^k$
Идея доказательства такая: пусть $n$ - это такой индекс, что $F_n\leq N<F_{n+1}$. Заметим, что для $s\leq n$ выполняется неравенство $F_s (1+\varepsilon)^{n-s}\leq F_n$. Поэтому $X=\max x_i$ обязано лежать в отрезке $[n-\log_{1+\varepsilon} \sum m_i,\,n]$, так как больше $n$ оно быть не может в виду выбора $n$ и меньше $s=n-\log_{1+\varepsilon} \sum m_i$ тоже, ибо в противном случае получаем противоречие:

$$F_n \leq N=m_1F_{x_1}+\ldots+m_kF_{x_k} \leq F_X \sum m_i < F_{s} (1+\varepsilon)^{n-s}\leq F_n.$$

Таким образом, количество различных значений $X$ (а значит по индукции и каждого из $x_i$) не превышает $1+\log_{1+\varepsilon} \sum m_i$.

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

Пусть $S(k,\varepsilon,m_1,\ldots,m_k,N)$ --- число решений данного в условии уравнения.

Ясно, что $S(1,\varepsilon,m_1,N) \leqslant 1 = 1! \cdot \prod_{i=1}^1 (1 + \log_{1+\varepsilon} i)$.

Пусть даны числа $k,\varepsilon,m_1,\ldots,m_{k+1}$ и $N$. Для каждого $i \in [1,k+1]$ через $X_i$ обозначим множество $x \in \mathbb{N}$, таких что $m_iF_x \in [N/(k+1),N]$. Так как из равенства

\[ m_1F_{x_1} + \dots + m_{k+1}F_{x_{k+1}} = N \]

следует, что $m_iF_{x_i} \geqslant N/(k+1)$ хотя бы для одного $i \in [1,k+1]$, то

\[ S(k+1,\varepsilon,m_1,\ldots,m_{k+1},N) \leqslant \sum_{i=1}^{k+1} \sum_{x \in X_i} S(k,\varepsilon,m_1,\ldots,m_{i-1},m_{i+1},\ldots,m_{k+1},N-m_iF_x). \]

Легко заметить, что $|X_i| \leqslant 1+\log_{1+\varepsilon}(k+1)$. Значит, если

\[ S(k,\varepsilon,m_1,\ldots,m_k,N) \leqslant k! \cdot \prod_{i=1}^k (1+\log_{1+\varepsilon}i) \]

для всех $N,m_1,\ldots,m_k \in \mathbb{N}$, то

\[ S(k+1,\varepsilon,m_1,\ldots,m_{k+1},N) \leqslant \sum_{i=1}^{k+1} \sum_{x \in X_i} \left( k! \cdot \prod_{i=1}^k (1+\log_{1+\varepsilon}i) \right) \leqslant (k+1)! \cdot \prod_{i=1}^{k+1} (1+\log_{1+\varepsilon}i) \]

Таким образом, в качестве требуемой оценки можно взять число

\[ k! \cdot \prod_{i=1}^k \left( 1+ \log_{1+\varepsilon}i \right). \]

P. S. Ясно, что оценку можно улучшить, хотя не думаю, что намного. По крайней мере, если $\varepsilon$ намного больше, чем $k$, то указанное произведение близко к $k!$, а то, что при произвольном $\varepsilon$ уравнение

\[ 1 \cdot F_{x_1} + \dots + 1 \cdot F_{x_k} = F_1 + \dots + F_k \]

имеет не менее чем $k!$ различных решений, очевидно.

[RIP]

Найти все множества $A\subset\mathbb N(=\{1,2,\ldots\})$, обладающие следующим свойством. Найдутся числа $m,k\in\mathbb N$ такие, что при всех достаточно больших $n\in\mathbb N$ число решений уравнения

$$x_1+\ldots+x_k=n$$

в числах $x_j\in A$ ($1\le j\le k$) равно $m$.

[Sonic86]

Покажем, что такого множества не существует.
Обозначим искомое множество А. Условием его существования будет выполнимость высказывания
$(\exists A)(\exists k)(\exists m)(\exists N)(\forall n) n \geqslant N \Rightarrow N(x_1 + x_k = n)=m, x_j \in A$
Положим $f(x)= \sum\limits_{j \in A} x^j$. Будет $\frac{f^{(r)}(0)}{r!} = 0;1\geqslant 0$ - конечны.
Тогда условие существования А примет вид условия существования $f(x)$:
$f(x)^k = P_{N-1} (x) + m \sum\limits_{j \geqslant N} x^j = P_{N-1} (x) + mx^N \cdot \frac{1}{1-x}$.
$\Leftrightarrow (1-x)f(x)^k = (1-x)P_{N-1} (x) + mx^N$.
Дифференцируем $n>N$ раз:
$((1-x)(f(x)^k)^{(N)} = 0 \Leftrightarrow f(x)^k = \frac{Q(x)}{1-x}$.
Теперь если правую часть разложить в ряд, то получим там все коэффициенты конечными, а если $k \geqslant 2$, то ввиду $\frac{f^{(r)}(0)}{r!} = 0;1\geqslant 0$ получим последовательность коэффициентов неограниченно возрастающей. Получили противоречие.

Мне задача понравилась. Кажется ее без производящих функций не так-то просто решить (или нет?!).

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

Sonic86 писал(а):

Покажем, что такого множества не существует.

Неправда! Если, к примеру, $A$ содержит почти все натуральные числа (то есть множество $\mathbb{N} \setminus A$ конечно), то найдутся $m=k=1$.

Можно привести и более сложные примеры, с произвольными $k$ и $m$.

[Sonic86]

Ну у меня в решении случай $k=1$ был исключен. С Вашим замечанием я согласен

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

Sonic86 писал(а):

Ну у меня в решении случай $k=1$ был исключен. С Вашим замечанием я согласен

Почему исключён? В условии сказано $k \in \mathbb{N}$ без каких-либо оговорок. Я знаю, что некоторые не хотят $0$ натуральным числом считать, но о том, что единица не из $\mathbb{N}$ и что натуральный ряд начинается с двойки, первый раз слышу.

В каком смысле Вы согласны с моим замечанием? Считаете ли Вы, что Ваше решение содержит ошибку и что пример множества $A$, удовлетворяющего указанным в условии задачи требованиям, возможен даже для $k>1$? Я Ваше решение, честно говоря, просто не понял. До последней строчки всё более-менее ясно, а вот почему какая-то "последовательность коэффициентов" (вероятно, коэффициентов разложения функции $f(x)^k$ в ряд Маклорена) окажется неограниченно возрастающей я не понимаю. (Кстати, зачем был нужен весь выпендрёж с разложением и дифференцированием, если Вы сразу установили, что почти все эти коэффициенты равны $m$?)

[Sonic86]

Ха! У меня в самом начале еще больше выпендрежа было!!! Я там даже диффур решил методом Бернулли!!!
Вы меня извините, но смысл у меня простой. Вы нашли все решения - я их проморгал, считайте мое доказательство доказательством того факта, что k<2. Останется простой случай k=1. А смысл только в методе производящих функций - ввели ПФ и дальше полагайтесь на свою интуицию.
Впрочем, я доказательство посмотрю и напишу проще, если получится.

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

Sonic86 писал(а):

Вы нашли все решения - я их проморгал, считайте мое доказательство доказательством того факта, что k<2. Останется простой случай k=1. А смысл только в методе производящих функций - ввели ПФ и дальше полагайтесь на свою интуицию.
Впрочем, я доказательство посмотрю и напишу проще, если получится.

Я Ваше доказательство не понимаю и считаю, что оно ошибочно. Поясните две последних строчки. Как Вы делаете вывод о неграниченном возрастании последовательности коэффициентов?

[Sonic86]

Да, действительно, то, что я написал выше - грубая переформулировка в терминах ПФ и выпендреж.
Пока смог доказать только,что k нечетно.
Пусть А - описанное выше множество. Докажем, что невозможен случай четного k.
Возьмем $a \in A$. Рассмотрим уравнение $x_1+...+x_k=ka$. Оно имеет решение $x_1,...,x_k = a$. Оно не изменяется при любых перестановках. Вообще, если уравнение $x_1+...+x_k=n$ имеет решение, то путем перестановок из него можно получить всего
$R = \frac{k!}{r_1! \cdot ... \cdot r_k!}$ решений, где $r_1+...+r_k=k$. А
$x_1=...=x_k \Leftrightarrow r_1! \cdot ... \cdot r_k! = k! \Leftrightarrow R$ нечетно при чтеных k. Во всех остальных случаях при четном k R четно. Существование перестановок $\Leftrightarrow k>1$.
Таким образом при четных k, если $(\exists a \in A) n=ak$, то $m=N(x_1+...+x_k=n)$ нечетно, в противном случае - четно. Но число решений - $m = const$, а уравнения $x_1+...+x_k=ka$ существуют, так как $A \neq \empty$. Значит нет уравнений с четным числом решений, что возможно только при нечетных k.

Примерно так же доказывается, что k не может быть простым.