Maths Olympiad Prep

Library / Korean Mathematical Olympiad Final Round /3 of 28

Korean Mathematical Olympiad Final Round

Number theory Difficulty 5.7 AIME, harder Prove it South Korea

Let aa, bb, cc, dd be pairwise coprime positive odd numbers. For positive integers nn, we define
f(n)=⌊na⌋+⌊nb⌋+⌊nc⌋+⌊nd⌋. f(n) = \lfloor \frac{n}{a} \rfloor + \lfloor \frac{n}{b} \rfloor + \lfloor \frac{n}{c} \rfloor + \lfloor \frac{n}{d} \rfloor.
Prove that
∑n=1abcd(−1)f(n)=1. \sum_{n=1}^{abcd} (-1)^{f(n)} = 1.

Solution

As aa, bb, cc, dd are all odd, we have
f(n)≡4n−(a⌊na⌋+b⌊nb⌋+c⌊nc⌋+d⌊nd⌋)≡(n−a⌊na⌋)+(n−b⌊nb⌋)+(n−c⌊nc⌋)+(n−d⌊nd⌋)(mod2). \begin{aligned} f(n) &\equiv 4n - \left(a\lfloor\frac{n}{a}\rfloor + b\lfloor\frac{n}{b}\rfloor + c\lfloor\frac{n}{c}\rfloor + d\lfloor\frac{n}{d}\rfloor\right) \\ &\equiv \left(n - a\lfloor\frac{n}{a}\rfloor\right) + \left(n - b\lfloor\frac{n}{b}\rfloor\right) + \left(n - c\lfloor\frac{n}{c}\rfloor\right) + \left(n - d\lfloor\frac{n}{d}\rfloor\right) \pmod{2}. \end{aligned}
We can observe that n−a⌊na⌋n - a\lfloor\frac{n}{a}\rfloor is the remainder of nn divided by aa—denote it as (nmod  a)(n \mod a). Meanwhile, the Chinese remainder theorem states that the map
Φ:{1,…,abcd}→{0,…,a−1}×{0,…,b−1}×{0,…,c−1}×{0,…,d−1},Φ(n)=(nmod  a,nmod  b,nmod  c,nmod  d) \Phi : \{1, \dots, abcd\} \to \{0, \dots, a-1\} \times \{0, \dots, b-1\} \times \{0, \dots, c-1\} \times \{0, \dots, d-1\}, \\ \Phi(n) = (n \mod a, n \mod b, n \mod c, n \mod d)
is a one-to-one correspondence, so we can replace our sum in nn as a sum in (x,y,z,w)=Φ(n)(x, y, z, w) = \Phi(n) when (x,y,z,w)(x, y, z, w) ranges over all elements of {0,…,a−1}×{0,…,b−1}×{0,…,c−1}×{0,…,d−1}\{0, \dots, a-1\} \times \{0, \dots, b-1\} \times \{0, \dots, c-1\} \times \{0, \dots, d-1\}. If Φ(n)=(x,y,z,w)\Phi(n) = (x, y, z, w) then f(n)≡x+y+z+w(mod2)f(n) \equiv x + y + z + w \pmod{2}, so it follows that
∑n=1abcd(−1)f(n)=∑x=0a−1∑y=0b−1∑z=0c−1∑w=0d−1(−1)x+y+z+w=(∑x=0a−1(−1)x)(∑y=0b−1(−1)y)(∑z=0c−1(−1)z)(∑w=0d−1(−1)w)=1⋅1⋅1⋅1=1. \begin{aligned} \sum_{n=1}^{abcd} (-1)^{f(n)} &= \sum_{x=0}^{a-1} \sum_{y=0}^{b-1} \sum_{z=0}^{c-1} \sum_{w=0}^{d-1} (-1)^{x+y+z+w} \\ &= \left(\sum_{x=0}^{a-1} (-1)^x\right) \left(\sum_{y=0}^{b-1} (-1)^y\right) \left(\sum_{z=0}^{c-1} (-1)^z\right) \left(\sum_{w=0}^{d-1} (-1)^w\right) \\ &= 1 \cdot 1 \cdot 1 \cdot 1 = 1. \end{aligned}

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.