USAMO 2026 (Problem 1)

Let

n

be an integer greater than

1

. For which real numbers

x

\lfloor nx\rfloor-\sum_{k=1}^{n}\frac{\lfloor kx\rfloor}{k}

maximal, and what is the maximal value that this expression can take? Note:

\lfloor z\rfloor

denotes the greatest integer less than or equal to

z

Let's prove Hint 7.

g=\gcd(\ell,n)

\ell=\ell'g

n=n'g

\gcd(\ell',n')=1

\left\{\left\{\frac{k\ell}{n}\right\}:1\le k\le n\right\}=\left\{\left\{\frac{k\ell'}{n'}\right\}:1\le k\le n\right\}

A=\{\ell',2\ell',\ldots,n'\ell'\}

We want to prove

A\equiv\{0,1,2,\ldots,n'-1\}\pmod{n'}.

i\ell'\equiv j\ell'\pmod{n'},

i\equiv j\pmod{\frac{n'}{\gcd(n',\ell')}}

i\equiv j\pmod{n'}.

1\le i,j\le n'\quad\Longrightarrow\quad i=j.

So all elements of

A

are distinct modulo

n'

, and

A

has

n'

elements. Therefore,

A=\{\ell',2\ell',\ldots,n'\ell'\}\equiv\{0,1,2,\ldots,n'-1\}\pmod{n'}.

Also,

(n'+1)\ell'\equiv\ell'\pmod{n'}

(n'+2)\ell'\equiv2\ell'\pmod{n'}

\vdots

(2n')\ell'\equiv n'\ell'\pmod{n'}

Similarly,

\{\ell',2\ell',\ldots,n'\ell'\}\equiv\{(n'+1)\ell',(n'+2)\ell',\ldots,2n'\ell'\}\pmod{n'}

\equiv\{(2n'+1)\ell',(2n'+2)\ell',\ldots,3n'\ell'\}\pmod{n'}

\vdots

\equiv\{((g-1)n'+1)\ell',((g-1)n'+2)\ell',\ldots,gn'\ell'\}\pmod{n'}

\equiv\{0,1,2,\ldots,n'-1\}\pmod{n'}.

Therefore, the multiset

B=\left\{\left\{\frac{k\ell}{n}\right\}:1\le k\le n\right\}=\left\{\left\{\frac{k\ell'}{n'}\right\}:1\le k\le n\right\}

=\left\{\underbrace{0,0,\ldots,0}_{g},\underbrace{\frac1{n'},\ldots,\frac1{n'}}_{g},\underbrace{\frac2{n'},\ldots,\frac2{n'}}_{g},\ldots,\underbrace{\frac{n'-1}{n'},\ldots,\frac{n'-1}{n'}}_{g}\right\}.

Since

\frac{k}{n'}=\frac{kg}{gn'}=\frac{kg}{n},

B=\left\{\underbrace{0,0,\ldots,0}_{g},\underbrace{\frac gn,\ldots,\frac gn}_{g},\underbrace{\frac{2g}{n},\ldots,\frac{2g}{n}}_{g},\ldots,\underbrace{\frac{n-g}{n},\ldots,\frac{n-g}{n}}_{g}\right\}.

=\{b_1,b_2,b_3,\ldots,b_n\}

Assume

b_1\le b_2\le b_3\le\cdots\le b_n.

We have

b_i\le\frac{i-1}{n}\qquad(1\le i\le n).

Since

b_1=0\le\frac0n\ \checkmark

b_2=0\le\frac1n

\vdots

b_g=0\le\frac{g-1}{n}

b_{g+1}=\frac gn\le\frac gn

b_{g+2}=\frac gn\le\frac{g+1}{n}

\vdots

b_{2g}=\frac gn\le\frac{2g-1}{n}

\vdots

b_{ig+1}=\frac{ig}{n}\le\frac{ig}{n}

b_{ig+2}=\frac{ig}{n}\le\frac{ig+1}{n}

\vdots

b_{(i+1)g}=\frac{ig}{n}\le\frac{(i+1)g-1}{n}

\vdots

b_{n-g+1}=\frac{n-g}{n}\le\frac{n-g}{n}

b_{n-g+2}=\frac{n-g}{n}\le\frac{n-g+1}{n}

\vdots

b_n=\frac{n-g}{n}\le\frac{n-1}{n}