uniolympiads Ελληνικά

IMC 2013, Day 2, Problem 2

Let pp and qq be relatively prime positive integers. Prove that

∑k=0pq−1(−1)⌊k/p⌋+⌊k/q⌋={0if pq is even,1if pq is odd.\sum_{k=0}^{pq-1} (-1)^{\lfloor k/p \rfloor + \lfloor k/q \rfloor} = \begin{cases} 0 & \text{if } pq \text{ is even}, \\ 1 & \text{if } pq \text{ is odd}. \end{cases}

(Here ⌊x⌋\lfloor x \rfloor denotes the integer part of xx.)

Original from the official PDFLet p and q be relatively prime positive integers. Prove that k k ( pq−1 + X 0 if pq is even, p q (−1) = 1 if pq is odd. k=0 (Here bxc denotes the integer part of x.)

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Proposed by Alexander Bolbot, State University, Novosibirsk)

Solution. Suppose first that pqpq is even (which implies that pp and qq have opposite parities), and let ak=(−1)⌊kp⌋+⌊kq⌋a_k = (-1)^{\left\lfloor\frac{k}{p}\right\rfloor + \left\lfloor\frac{k}{q}\right\rfloor}. We show that ak+apq−1−k=0a_k + a_{pq-1-k} = 0, so the terms on the left-and side of (∗)(*) cancel out in pairs.

For every positive integer kk we have {kp}+{p−1−kp}=p−1p\left\{\frac{k}{p}\right\} + \left\{\frac{p-1-k}{p}\right\} = \frac{p-1}{p}, hence

⌊kp⌋+⌊pq−1−kp⌋=(kp−{kp})+(pq−1−kp−{−1−kp})=pq−1p−p−1p=q−1\left\lfloor\frac{k}{p}\right\rfloor + \left\lfloor\frac{pq-1-k}{p}\right\rfloor = \left(\frac{k}{p} - \left\{\frac{k}{p}\right\}\right) + \left(\frac{pq-1-k}{p} - \left\{\frac{-1-k}{p}\right\}\right) = \frac{pq-1}{p} - \frac{p-1}{p} = q-1
and similarly
⌊pq−1−kq⌋+⌊kq⌋=p−1.\left\lfloor\frac{pq-1-k}{q}\right\rfloor + \left\lfloor\frac{k}{q}\right\rfloor = p-1.
Since pp and qq have opposite parities, it follows that ⌊kp⌋+⌊kq⌋\left\lfloor\frac{k}{p}\right\rfloor + \left\lfloor\frac{k}{q}\right\rfloor and ⌊pq−1−kp⌋+⌊pq−1−kq⌋\left\lfloor\frac{pq-1-k}{p}\right\rfloor + \left\lfloor\frac{pq-1-k}{q}\right\rfloor have opposite parities and therefore apq−1−k=−aka_{pq-1-k} = -a_k.

Now suppose that pqpq is odd. For every index kk, denote by pkp_k and qkq_k the remainders of kk modulo pp and qq, respectively. (I.e., 0≤pk<p0 \le p_k < p and 0≤qk<q0 \le q_k < q such that k≡pk(modp)k \equiv p_k \pmod{p} and k≡qk(modq)k \equiv q_k \pmod{q}.)

Notice that

⌊kp⌋+⌊kq⌋≡p⌊kp⌋+q⌊kq⌋=(k−pk)+(k−qk)≡pk+qk(mod2).\left\lfloor\frac{k}{p}\right\rfloor + \left\lfloor\frac{k}{q}\right\rfloor \equiv p\left\lfloor\frac{k}{p}\right\rfloor + q\left\lfloor\frac{k}{q}\right\rfloor = (k-p_k) + (k-q_k) \equiv p_k + q_k \pmod{2}.

Since pp and qq are co-prime, by the Chinese remainder theorem the map k↦(pk,qk)k \mapsto (p_k, q_k) is a bijection between the sets {0,1,…,pq−1}\{0,1,\ldots,pq-1\} and {0,1,…,p−1}×{0,1,…,q−1}\{0,1,\ldots,p-1\}\times\{0,1,\ldots,q-1\}. Hence

∑k=0pq−1(−1)⌊kp⌋+⌊kq⌋=∑k=0pq−1(−1)pk+qk=∑i=0p−1∑j=0q−1(−1)i+j=(∑i=0p−1(−1)i)⋅(∑j=0q−1(−1)j)=1.\sum_{k=0}^{pq-1}(-1)^{\left\lfloor\frac{k}{p}\right\rfloor + \left\lfloor\frac{k}{q}\right\rfloor} = \sum_{k=0}^{pq-1}(-1)^{p_k+q_k} = \sum_{i=0}^{p-1}\sum_{j=0}^{q-1}(-1)^{i+j} = \left(\sum_{i=0}^{p-1}(-1)^i\right)\cdot\left(\sum_{j=0}^{q-1}(-1)^j\right) = 1.

Transcribed from the official solutions, pages 1–2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?