solution

Attachments:

hxy09, Could you upload solution of problem 4?(China TST 2009)

This is a question like last years's third question of IMO, it is not hard enough for 3 but it is nice. I got the same solution as hxy09 and it seems like another proof for this appearently weak bound could be hard to find, maybe there can be a different approach resulting with a better bound. If somebody has a different approach, I would be pleased to see it.

Dear hxy09 Sorry for my stupidity,but could you you explain me how you got: $ x_1 + 2x_2 + ... + kx_k = a_r - a_1 + 1$

birzhan wrote: Dear hxy09 Sorry for my stupidity,but could you you explain me how you got: $ x_1 + 2x_2 + ... + kx_k = a_r - a_1 + 1$ Sorry for my late reply and I had a typo for $ x_1 + 2x_2 + ... + kx_k = a_r - a_1 + 1$ the correct version is $ x_1 + 2x_2 + ... + kx_k = a_r - a_1$ If $ p|a_i(a_i+1)...a_{i+1}-1$ the length is $ a_{i+1}-a_i$ then the sum of the length is $ a_r-a_1$ p.s. It made no difference whether $ x_1 + 2x_2 + ... + kx_k$ is $ a_r - a_1 + 1$or $ a_r - a_1$ and thank you for pointing out my mistake

Assume otherwise. Like the previous solution, we will use the fact that $x(x+1)...(x+m-1) \equiv 1 \pmod p$ has at most $m$ roots. Partition into intervals $[0,p^{\frac{1}{3}}],[p^{\frac{1}{3}} , 2p^{\frac{1}{3}}] ..., [p-p^{\frac{1}{3}} , p]$ Then there are $p^{\frac{2}{3}}$ such intervals. Let $a_i$ be the no. of solutions to $p|n!+1$ in $[ip^{\frac{1}{3}},(i+1)p^{\frac{1}{3}}]$ then any $a,b$ in the same interval gives us a distinct solution to $x(x+1)...(x+m-1) \equiv 1 \pmod p$ where $0 \leq m < p^{\frac{1}{3}}$. $\implies \binom{p^\frac{1}{3}}{2} \geq \sum \binom{a_i}{2} \geq p^{\frac{2}{3}}\binom{c}{2}$ where the last inequality follows from the fact that $\binom{n}{2}$ is convex. This is a contradiction for large enough $c$ and thus we are done.

Assume that the requisite number of such integers is $r$ with the integers being $a_1<a_2<\dots <a_r=p-1$. Suppose $x_j= \{\# \text{times} \quad a_{n+1}-a_n=j\}$. Note that by Lagrange's theorem we have that there are atmost $j$ solutions $\pmod p$ to $$(x+1)(x+2)\dots (x+j) =1 \pmod p$$This means that $x_j \leq j$. Because if $p\mid a_n!+1$ and $p\mid a_{n+1}!+1$ , then $p \vert (a_n+1)(a_n+2) \dots (a_n+(a_{n+1}-a_n)-1$. Note that we have $:=$ $$ \sum_{i=1}^{p-2} x_i = r-1 \quad \text{and} \quad \sum_{i=1}^{p-2} ix_i= a_r-a_1 \leq p-2$$ Note that $ \sum_{i=1}^{p-2} x_i = r-1$ when the terms with the smallest index are maximal . Hence the second sum looks like $1^2+2^2 +\dots k^2 + (k+1)\cdot \ell$ for some $0\leq \ell \leq k+1$. We then have the following estimate : $$p-2 > 1^2+2^2+\dots +k^2 \implies p-2 > \frac {k(k+1)(2k+1)}{6}$$$$ \implies p > \frac {k^3}3 \implies k< (3p)^{\frac 13}$$ Then we have $$ \sum_{i=1}^{p-2} x_i +1 \leq 1+2+\dots k + \ell+1= \frac {k(k+1)}2 + \ell \leq \frac {(k+1)(k+2)+2}{2} < 4k^2 < 4\cdot (3p)^{\frac 23}$$ This shows that $c= 4 \cdot 3^{\frac 23}$ is enough.

Fastest I could ever solve a China TST!! Thanks to @Aryan-23 Fang-jh wrote: Prove that for any odd prime number $ p,$ the number of positive integer $ n$ satisfying $ p|n! + 1$ is less than or equal to $ cp^\frac{2}{3}.$ where $ c$ is a constant independent of $ p.$ Claim(Lagrange Theoem):Let $p$ be a prime and $f\in\mathbb{Z[X]}$.If $f\neq 0$ in $\mathbb{F}_p$ then the number of solutions of $ \#\{f(x)\equiv 0\pmod p\}\leq \deg{f}$ Proof: We induct on the degree $d$ of $f$. Base case $d=0$ is obvious now assume it holds for $d$ we will prove it for $d+1$.If $f(x)\equiv 0\pmod p$ with degree $d+1$ has no solutions then we are done by inductive hypothesis. So assume there exists $g\in\mathbb{Z[X]}$ such that $$f(x)=(x-a)g(x)\pmod p$$and $\deg(g)\leq d$. But then this has atmost $\deg(g)+1\leq \deg(f)$ solutions so we are done.$\square$ Let $n_1<n_2\cdots <n_m=p-1$ be the set of solutions to the assertion.We have to show $m=\mathcal{O}(n^{\tfrac{2}{3}})$. Define $j=\left\lfloor\dfrac{\sqrt{1+8m}-1}{2}\right\rfloor$ and note that $\tfrac{j(j+1)}{2}\leq m\leq \tfrac{(j+1)(j+2)}{2}$. Key claim : For each $1\leq k<p$ there are atmost $k$ indices such that $n_{i+1}-n_i=k$ ProofWe have $$(n_i)!\equiv -1\equiv n_{i+1}!\pmod p\Longleftrightarrow (n_i+1)(n_i+2)\cdots (n_{i+1})\equiv 1\pmod p $$and so using Lagrange's Theorm this has atmost $n_{i+1}-n_i=k$ solutions to this.$\square$ To finish see that $$p>(p-1)-n_1=\sum_{i=1}^{i=m-1}(n_{i+1}-n_i)\geq 1^2+2^2+\cdots j^2=\dfrac{j(j+1)(2j+1)}{6}>\dfrac{j^3}{3}\Longleftrightarrow j<(3p)^{\tfrac{1}{3}}$$Thus $$m\leq \dfrac{(j+1)(j+2)}{2}<(j+1)^2\leq 4j^2<(576)^{\tfrac{1}{3}}p^{\tfrac{2}{3}}=\mathcal{O}(n^{\tfrac{2}{3}})\blacksquare$$

We claim $c=4$ works, and we will bound the number of $(i, j)$ such that $i(i+1)(i+2)\cdots(i+j-1) \equiv 1 \pmod{p},$ with $0 \le i < p, 0 < j < p^{1/3}.$ First, for any fixed $j,$ there are at maximum $j$ solutions for $i$ by Lagrange's theorem, so summing over all $j$ gives an upper bound of $p^{2/3}.$ Now, assume for the sake of contradiction there are more than $4 p^{2/3}$ solutions. We split the residues mod $p$ into $p^{2/3}$ blocks of size $p^{1/3}.$ If the $i$th block has $a_i$ solutions, then note that by taking any two solutions $n! \equiv m! \equiv -1 \pmod{p},$ and dividing, we get $\frac{n!}{m!} \equiv 1 \pmod{p},$ which gives a solution since the value of $j$ is less than $p^{1/3}$ by the condition that both solutions are in the same block. Therefore, we get at least $\binom{a_i}{2}$ solutions per block. Summing and using Jensen's, this tells us that we have at least $\binom{4}{2} p^{2/3}$ solutions, which is larger than the upper bound given before, so we're done.

Suppose that all the possible solutions to $n$ include $a_1<a_2<a_3<..........<a_X=p-1$ Our goal is to prove the existence of an constant $c$ such that $X \le c p^{\frac{2}{3}}$ Since $n_i! \equiv -1 \mod p$ and $n_{i+1}! \equiv -1 \pmod p$ hence $(n_i+1).........n_{i+1} \equiv 1 \pmod p$.

By Lagrange's theorem

,atmost $k$ indices such that $n_{i+1}-n_i=k$ This implies that the differences between $n_i$ are written in a ascending order then we get a the sequence $1,2,2,3,3,3,4,4,4,4,5,5,5,5,5...........,k,k,......,k$ Adding everything and comparing gives the result

Fang-jh wrote: Prove that for any odd prime number $ p,$ the number of positive integer $ n$ satisfying $ p|n! + 1$ is less than or equal to $ cp^\frac{2}{3}.$ where $ c$ is a constant independent of $ p.$ Just notice that sigma1/p^2 which p is a prime less than 1/2(about 0.78)then notice that p=1 mod 4 and you can finish your proof.

Fang-jh wrote: Prove that for any odd prime number $ p,$ the number of positive integer $ n$ satisfying $ p|n! + 1$ is less than or equal to $ cp^\frac{2}{3}.$ where $ c$ is a constant independent of $ p.$ I love China and Iran’s tst, especially number theory and combination!!!!!!

I might as well post the solution I wrote up a year ago on a different thread. The start is similar to other solutions, but I think the finish is a bit different. Call an integer $n$ good if $p$ divides $n! + 1$; observe that $p-1$ is the largest good integer. The key to this problem lies in the following lemma. Lemma 1: For each positive integer $t$, there are at most $t$ good integers $k$ such that $k+t$ is also good. Proof. If $p$ divides both $(k+t)! + 1$ and $k! + 1$, then $p$ must also divide \[ \big((k+t)! + 1\big) - \big(k! + 1\big) = k!\big((k+1)\cdots(k+t) - 1\big). \]Since $k$ is a good integer, $\gcd(p,k!) = 1$, so in fact \[ p\mid (k+1)\cdots (k+t) - 1. \]But the right hand side is a polynomial of degree $t$, which has at most $t$ solutions in $\mathbb F_p$ by Lagrange. $\square$ Let \[ n_1 < n_2 < \cdots < n_m = p-1 \]denote the set of good integers. For each $1\leq j\leq p$, let $a_j$ denote the number of integers $1\leq k\leq m$ such that $n_k - n_{k-1} = j$. By the lemma, $a_j\leq j$ for each $j$. Furthermore, we are given that \[ a_1 + 2a_2 + \cdots + pa_p = \sum_{k=1}^m(n_k - n_{k-1}) = n_m - n_1\leq p, \]and we wish to maximize $a_1 + \cdots + a_p$. The rest of this problem is encoded in the following purely algebraic lemma. Lemma 2. Suppose $b_1,\ldots, b_n$ are nonnegative real numbers such that \[ b_1 + 2b_2 + \cdots + nb_n \leq n\qquad\qquad(*) \]and $b_i\leq i$ for all $i$. Then there exists a constant $c > 0$ such that \[ b_1 + b_2 + \cdots + b_n \leq cn^{2/3}. \] Proof. Throughout this proof, we will use the notation $a\lesssim b$ to denote "less than or equal to up to a constant". Without loss of generality we may replace $(*)$ with the stricter condition $b_1 + 2b_2 + \cdots + nb_n = n$. Consider an arbitrary $n$-tuple $(b_1,\ldots, b_n)$ of nonnegative real numbers satisfying the given conditions. If there exist integers $r < s$ with $b_r < r$ but $b_s > 0$, then we may replace $(b_1,\ldots, b_n)$ by the tuple \[ (b_1',\ldots, b_n') = (b_1,\ldots, b_{r-1},b_r + \tfrac{s\varepsilon}r,b_{r+1},\ldots, b_{s-1},b_s - \varepsilon,b_{s+1},\ldots), \]where $\varepsilon$ is chosen small enough that $b_r + \tfrac{s\varepsilon}r < r$ and $b_s > \varepsilon$. (In other words, we adjust the values of $b_r$ and $b_s$ slightly while fixing all other elements in the tuple.) Then \[ b_1' + 2b_2' + \cdots + nb_n' = b_1 + 2b_2 + \cdots + nb_n = n, \]but the sum $b_1 + b_2 + \cdots + b_n$ increases. This means that $(b_1,\ldots,b_n)$ does not achieve our maximum. In particular, our maximum is achieved when \[ b_j = \begin{cases}j&\text{if }1\leq j\leq t,\\ 0&\text{if }j\geq t+2, \end{cases} \]where $t$ is some positive integer at most $n$. Finally, observe that \[ n = b_1 + 2b_2 + \cdots + nb_n \geq 1^2 + 2^2 + \cdots + t^2 \gtrsim t^3, \]and hence $t \lesssim n^{1/3}$. Then \[ b_1 + b_2 + \cdots + b_n = b_1 + \cdots + b_{t+1} \leq 1 + \cdots + (t+1) \lesssim t^2 \lesssim n^{2/3}, \]and so $b_1 + \cdots + b_n\leq cn^{2/3}$ for some constant $c$. $\square$ The problem falls upon applying Lemma 2 to the sequence $(a_1,\ldots, a_p)$. $\blacksquare$

The difficult part is definitely realizing the combinatorial approach. Let $1<n_1<n_2<\cdots<n_m = p$ be all the numbers that work, so it suffices to show $m \leq cp^{2/3}$. For each $i$, we have $$(n_i+1)(n_i+2) \cdots (n_i+n_{i+1}-n_i) \equiv 1 \pmod p.$$In other words, for each $k$, there are at most $k$ indices $i$ with $n_{i+1} - n_i = k$ by Lagrange theorem. The rest is easy. Let $j$ be maximal with $j(j+1) \leq 2m$. Then, note that $$p = \sum_{i=1}^{m-1} (n_{i+1} - n_i) \geq 1^2+2^2+\cdots+j^2 = \frac{j(j+1)(2j+1)}6.$$The result follows.

HamstPan38825 wrote: Then, note that $$p = \sum_{i=1}^{m-1} (n_{i+1} - n_i) \geq 1^2+2^2+\cdots+j^2 = \frac{j(j+1)(2j+1)}6.$$ Maybe I'm missing something (and you're not the only person to mention this in the thread, so I probably am), but why does this follow so quickly? Because there are at most $k$ terms such that $n_{i+1} - n_i = k$, the contribution of these terms to the overall sum is at most $k^2$, which seems like it should yield an inequality going in the wrong direction.