Maths Olympiad Prep

Library / /10 of 15

Number theory Difficulty 6.5 National Olympiad Prove it Argentina

Find the number of 20132013-digit numbers d1d2d2013d_1 d_2 \dots d_{2013} with odd digits d1,d2,,d2013d_1, d_2, \dots, d_{2013} so that
d1d2+d3d4++d1809d18101(mod4)d_1 \cdot d_2 + d_3 \cdot d_4 + \dots + d_{1809} \cdot d_{1810} \equiv 1 \pmod{4}, d1810d1811+d1811d1812++d2012d20131(mod4)d_{1810} \cdot d_{1811} + d_{1811} \cdot d_{1812} + \dots + d_{2012} \cdot d_{2013} \equiv 1 \pmod{4}.

Solution

We use the following observation: Any odd numbers x1,,xkx_1, \dots, x_k satisfy
x1x2+x2x3++xk1xk+xkx1k(mod4).() x_1 x_2 + x_2 x_3 + \dots + x_{k-1} x_k + x_k x_1 \equiv k \pmod{4}. \quad (*)
Note that the sum in ()(*) is cyclic, unlike the ones in the statement. To justify ()(*) reduce the xix_i mod 44; then they become +1+1's or 1-1's as odd numbers are congruent to ±1\pm 1 mod 44. Note that replacing an xi=1x_i = -1 by xi=1x_i = 1 does not change the mod 44 remainder of S=j=1kxjxj+1S = \sum_{j=1}^{k} x_j x_{j+1}. Indeed the new and the old value of SS differ by 2(xi1+xi+1)2(x_{i-1} + x_{i+1}) which is a multiple of 44 as xi1,xi+1x_{i-1}, x_{i+1} are odd. So we may assume xi=1x_i = 1 for all ii, then S=kS = k and ()(*) is obvious.

Let d1d2d2013d_1 d_2 \dots d_{2013} satisfy the stated conditions. By ()(*) we have j=11810djdj+11810(mod4)\sum_{j=1}^{1810} d_j d_{j+1} \equiv 1810 \pmod{4} (here

d_{1810} + 1 = d_1), hence j=11809djdj+11(mod4)\sum_{j=1}^{1809} d_j d_{j+1} \equiv 1 \pmod{4} if and only if 1810d1810d11(mod4)1810 - d_{1810} d_1 \equiv 1 \pmod{4}, i.e.
d1d18101(mod4)d_1 d_{1810} \equiv 1 \pmod{4}.

Similarly j=18102012djdj+11(mod4)\sum_{j=1810}^{2012} d_j d_{j+1} \equiv 1 \pmod{4} if and only if (20131809)d1810d20131(mod4)(2013-1809) - d_{1810} d_{2013} \equiv 1 \pmod{4}, i.e.
d1810d20131(mod4)d_{1810} d_{2013} \equiv -1 \pmod{4}. We see that the conditions depend only on the three digits d1,d1810,d2013d_1, d_{1810}, d_{2013}; the
remaining 20102010 digits did_i can be chosen arbitrarily among 1,3,5,7,91, 3, 5, 7, 9.

There are 33 odd decimal digits 1(mod4)\equiv 1 \pmod{4}, namely 1,5,91, 5, 9; there are 22 odd digits 1(mod4)\equiv -1 \pmod{4},
namely 3,73, 7. Let d1810{1,5,9}d_{1810} \in \{1,5,9\}. Then d1d18101(mod4)d_1 d_{1810} \equiv 1 \pmod{4} and d1810d20131(mod4)d_{1810} d_{2013} \equiv -1 \pmod{4} imply
d1{1,5,9},d2013{3,7}d_1 \in \{1,5,9\}, d_{2013} \in \{3,7\}. So there are 33 choices for each of d1d_1 and d1810d_{1810}, and 22 choices for d2013d_{2013}.
The choices are independent, which gives 332=183 \cdot 3 \cdot 2 = 18 admissible choices for the triple d1,d1810,d2013d_1, d_{1810}, d_{2013}.
Because there are 55 choices for each of the remaining 20102010 digits did_i (they can be arbitrary), we
obtain 185201018 \cdot 5^{2010} admissible numbers d1d2d2013d_1 d_2 \dots d_{2013} with d1810{1,5,9}d_{1810} \in \{1,5,9\}.

Likewise if d1810{3,7}d_{1810} \in \{3,7\} then d1{3,7}d_1 \in \{3,7\}, d2013{1,5,9}d_{2013} \in \{1,5,9\}. Thus there are 22 choices for each of d1d_1 and
d1810d_{1810}, and 33 choices for d2013d_{2013}, leading to 223=122 \cdot 2 \cdot 3 = 12 admissible choices for the triple d1,d1810,d2013d_1, d_{1810}, d_{2013}.
Like in the previous case we obtain 125201012 \cdot 5^{2010} admissible numbers with d1810{3,7}d_{1810} \in \{3,7\}.

In summary there are 1852010+1252010=65201118 \cdot 5^{2010} + 12 \cdot 5^{2010} = 6 \cdot 5^{2011} admissible numbers in all.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.