数列$[\frac{n^2}{k}]$从哪项开始，之后的数都不相同

abababa

设$[x]$表示不超过$x$的最大整数。对于给定的正整数$k$，考察数列$[\frac{n^2}{k}]$，其中$n>0$。若数列从$n=m$开始（含这一项），以后的数都不相同，求$m$的最小值，并求出$n$从$1$到$m$取值时，数列中有多少个不同的数。

Czhang271828

事实 1. 容易检验, 待求的 $n$ 小于 $k$.
事实 2. 对正整数 $0<t<k$, 总有 $[(k-t)^2/k]-[t^2/k]=k-2t$.

这告诉我们: 找到最后一处 $a_n=a_{n+1}$, 等价于找到第一处 $a_{t+1}-a_t\geq 2$ (即, 取等号, 因为不可能严格大).

必要条件: $1<\frac{(t+1)^2}k-\frac{t^2}{k}<3$, 也就是 $k<2t+1<3k$. 有用的条件是 $t>\frac{k-1}{2}$.

归纳步骤 a. 若 $k=2m$ 是偶数, 此时 $t\geq m$. 注意到 $[\frac{m^2}{2m}]=[\frac m2]$, 以及 $[\frac{(m+s)^2}{2m}]=[\frac m2]+s+[\frac{s^2}{2m}]$. 因此, 只需找到首个大于 $1$ 的 $[\frac{s^2}{2m}]$.

归纳步骤 b. 若 $k=2m-1$ 是奇数, 此时 $t\geq m$. 注意到 $[\frac{m^2}{2m-1}]=[\frac{m-\frac 12}{2}+\frac 12+\frac{1}{8(m-\frac 12)}]$, 以及 $[\frac{(m+s)^2}{2m-1}]=[\frac{m-\frac 12}{2}+\frac 12+s+\frac{(2s+1)^2}{8(m-\frac 12)}]$. 因此, 只需找到首个大于 $1$ 的 $[\frac{(2s+1)^2}{8(m-\frac 12)}]$

后面的计算没有逻辑深度了, 我就不算了. 最后 $n_\min \approx \frac k2-\sqrt{k}$. 验证了 $k=1024$, 此时 $n_\min=481$ 是对的.

abababa

Czhang271828 发表于 2024-7-17 22:03
事实 1. 容易检验, 待求的 $n$ 小于 $k$.
事实 2. 对正整数 $0<t<k$, 总有 $[(k-t)^2/k]-[t^2/k]=k-2t$.
...

谢谢。我是设原数列为$a_n$，然后因为$m$之后的数都不相等，所以$a_{m+1}-a_m=[\frac{(m+1)^2}{n}]-[\frac{m^2}{n}]\ge1$，就有$[\frac{(m+1)^2}{n}]\ge1+[\frac{m^2}{n}]=[1+\frac{m^2}{n}]=[\frac{m^2+n}{n}]$，所以$\frac{(m+1)^2}{n}\ge\frac{m^2+n}{n}$，得到$m\ge\frac{n-1}{2}$。

然后取$m=\lceil\frac{n-1}{2}\rceil$，当$n=2h$时$m=h$，当$n=2h+1$时$m=h$，考虑$a_{m+t},a_{m+t+1}$，当$m=2h$时有
\begin{align*}
[\frac{(h+t+1)^2}{2h}]-[\frac{(h+t)^2}{2h}]
&=[\frac{(h+t)^2}{2h}+\frac{2h}{2h}+\frac{2t+1}{2h}]-[\frac{(h+t)^2}{2h}]\\
&=1+[\frac{(h+t)^2}{2h}+\frac{2t+1}{2h}]-[\frac{(h+t)^2}{2h}]\\
&\ge 1
\end{align*}

同理当$m=2h+1$时也有类似的不等式，所以$m=\lceil\frac{n-1}{2}\rceil$就是所求的值。主要是第二问里，我觉得数列能取遍所有的从$0$到$[\frac{m^2}{k}]$的值，这个怎么证明它在中间不会跳过某个数呢？

Czhang271828

abababa 发表于 2024-7-18 16:31
怎么证明它在中间不会跳过某个数呢？

上面写过了. $n_\min\approx \frac k2-\sqrt k <\frac k2$. 并且首个 $a_{t-1}-a_t\geq 2$ 出现在 $t\approx \frac k2+\sqrt k>\frac k2$. 所以 $1\leq t\leq n_\min$ 不重复.

abababa

Czhang271828 发表于 2024-7-18 17:58
上面写过了. $n_\min\approx \frac k2-\sqrt k <\frac k2$. 并且首个 $a_{t-1}-a_t\geq 2$ 出现在 $t\app ...

原来如此，我有点明白了，在$a_m$之前这些整数的增量不超过1，所以不会跳过。