uniolympiads English

IMC 2013, Ημέρα 2, Θέμα 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.)

Πρωτότυπο από το επίσημο 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.)

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 1–2. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;