Maths Olympiad Prep

Library / /1 of 3

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(ana+bnb+cnc+dnd)(nana)+(nbnb)+(ncnc)+(ndnd)(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 nanan - a\lfloor\frac{n}{a}\rfloor is the remainder of nn divided by aa—denote it as (nmoda)(n \mod a). Meanwhile, the Chinese remainder theorem states that the map
Φ:{1,,abcd}{0,,a1}×{0,,b1}×{0,,c1}×{0,,d1},Φ(n)=(nmoda,nmodb,nmodc,nmodd) \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,,a1}×{0,,b1}×{0,,c1}×{0,,d1}\{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=0a1y=0b1z=0c1w=0d1(1)x+y+z+w=(x=0a1(1)x)(y=0b1(1)y)(z=0c1(1)z)(w=0d1(1)w)=1111=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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.