Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

G
Topic
First Poster
Last Poster
No topics here!
Generaliztion of 1999 USAMO
EthanWYX2009   5
N Nov 16, 2024 by kingu
Let $p > 2$ be a prime and let $a_1,a_2,\ldots,a_{2n}$ be integers not divisible by $p,$ such that
\[ \left\{ \dfrac{ra_1}{p} \right\} + \left\{ \dfrac{ra_2}{p} \right\} + \cdots+ \left\{ \dfrac{ra_{2n}}{p} \right\} = n  \]for any integer $r$ not divisible by $p$. Prove that there exists $2\le j\le 2n$ such that $a_1+a_j$ is divisible by $p$.

Created by Haojia Shi
5 replies
EthanWYX2009
Nov 14, 2024
kingu
Nov 16, 2024
Generaliztion of 1999 USAMO
G H J
G H BBookmark kLocked kLocked NReply
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
EthanWYX2009
769 posts
#1 • 7 Y
Y by Martin.s, ehuseyinyigit, Phorphyrion, axsolers_24, Sedro, LLL2019, ereh
Let $p > 2$ be a prime and let $a_1,a_2,\ldots,a_{2n}$ be integers not divisible by $p,$ such that
\[ \left\{ \dfrac{ra_1}{p} \right\} + \left\{ \dfrac{ra_2}{p} \right\} + \cdots+ \left\{ \dfrac{ra_{2n}}{p} \right\} = n  \]for any integer $r$ not divisible by $p$. Prove that there exists $2\le j\le 2n$ such that $a_1+a_j$ is divisible by $p$.

Created by Haojia Shi
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
axsolers_24
5 posts
#2 • 2 Y
Y by ehuseyinyigit, ereh
by Haojia Shi? The perfect scorer this year
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
LLL2019
825 posts
#3 • 1 Y
Y by ehuseyinyigit
For reference, the article written by shj in NS Math column 2024/05/27: here
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math_comb01
637 posts
#5 • 4 Y
Y by kingu, hellomath010118, sharkydevil_humpty, Martin.s
Very Beautiful Problem, solved with a nudge from kingu. I'm not sure what the solution in above link is, as it shows "Forbidden access" to me, but I suspect the solutions should be isomorphic

EDIT: kingu told me the solutions are indeed the same.
Let $a'_i$ denote the inverse of $a_i \pmod p$, Let $\omega$ denote the $p$-th root of unity.
Like in the USAMO problem, it is easy to get to $\sum_{i} \frac{1}{1-\omega^{-a'_im}} = n$, therefore, for any non principal character $\chi$ we have $$\sum_{k=1}^{p-1} \sum_{i=1}^{2n} \frac{\chi(k)}{1-\omega^{-a'_im}} = n \sum \chi(k) = 0$$, for any fixed $i$, $1 \leq i \leq n$, we have
\[
\sum_{k=1}^{p-1} \frac{\chi(k)}{1 - w^{a'_i}k} = \chi(a_i) \sum_{k=1}^{p-1} \frac{\chi(a'_ik)}{1 - w^k} = \chi(a_i) \sum_{k=1}^{p-1} \frac{\chi(k)}{1 - w^k}.
\], and therefore we have $$\left(\sum (\chi(a_i))\right) \cdot \left(\sum_{k=1}^{p-1} \frac{\chi(k)}{1-\omega^{k}}\right) = 0$$, now we claim the following in flavor of standard $L$-function arguements.

Claim 1: $$\left(\sum_{k=1}^{p-1} \frac{\chi(k)}{1-\omega^{k}}\right) \neq 0$$Proof: We use a pairing arguement,
\begin{align*}
2\left(\sum_{k=1}^{p-1} \frac{\chi(k)}{1-\omega^{k}}\right) &= \sum_{k=1}^{p-1} \left(\frac{\chi(k)}{1-\omega^k}+\frac{\chi(-k)}{1-\omega^{-k}}\right) \\&= \sum_{k=1}^{p-1} \chi(k) \frac{1+\omega^k}{1-\omega^k} \\&= i \cdot \sum_{k=1}^{p-1} \left(\chi(k) \cdot \cot\left(\frac{k\pi}{p}\right)\right) \\&= \frac{ip}{\pi}\sum_{n \in \mathbb{N}} \frac{\chi(n)}{n} = \frac{ip}{\pi}\mathbb{L}(1,\chi) \neq 0
\end{align*}$\blacksquare$
From the claim, we conclude that $$\sum_{i=1}^{2n} \chi(a_i) = 0$$$$\therefore \sum_{i=1}^{2n} \chi(a_i \cdot a'_1) = \sum_{i=1}^{2n} \chi(-a_i \cdot a'_1)$$for all dirichlet characters, summing over all dirichlet characters gives, [Notation: Let $\mathcal{S}$ denote the set of all dirichlet characters]
$$\sum_{\chi \in \mathcal{S}} \sum_{i=1}^{2n} \chi(a_i \cdot a'_1) = \sum_{\chi \in \mathcal{S}} \sum_{i=1}^{2n} \chi(-a_i \cdot a'_1)$$exchanging the summation,
$$ \sum_{i=1}^{2n} \sum_{\chi \in \mathcal{S}} \chi(a_i \cdot a'_1) =  \sum_{i=1}^{2n} \sum_{\chi \in \mathcal{S}} \chi(-a_i \cdot a'_1)$$and now as clearly both sides are greater than $0$, so there exists a $j$ so that $\sum_{\chi \in \mathcal{S}} \chi(-a_j \cdot a'_1) > 0$
Now, this means that there exists an $j$ so that $-a_j \cdot a'_1 \equiv 1 \pmod p$ which is equivalent to $p \mid a_1+a_j$, as desired.
Remark: All the properties used without proof should exist in the book, Analytic Number theory by Tom M. Apostol
Motivation and Failed approaches
This post has been edited 4 times. Last edited by math_comb01, Nov 16, 2024, 7:29 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
tobiSALT
50 posts
#6
Y by
LLL2019 wrote:
For reference, the article written by shj in NS Math column 2024/05/27: here

Link doesn't work:(
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
kingu
209 posts
#7 • 3 Y
Y by axsolers_24, Martin.s, ereh
Heres a pdf for the official sol.
Attachments:
amo.pdf (86kb)
Z K Y
N Quick Reply
G
H
=
a