Maths Olympiad Prep

Library / /167 of 173

Algebra Difficulty 3.3 AMC 10/12 Find the answer

For each positive digit DD and positive integer kk, we use the symbol D(k)D_{(k)} to represent the positive integer having exactly kk digits, each of which is equal to DD. For example, 2(1)=22_{(1)}=2 and 3(4)=33333_{(4)}=3333. There are NN quadruples (P,Q,R,k)(P, Q, R, k) with P,QP, Q and RR positive digits, kk a positive integer with k2018k \leq 2018, and P(2k)Q(k)=(R(k))2P_{(2k)}-Q_{(k)}=\left(R_{(k)}\right)^{2}. What is the sum of the digits of NN?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Suppose that DD is a digit and kk is a positive integer. Then D(k)=DDDDk times =D1111k times =D199999k times =D19(0000k times 1)=D19(10k1)D_{(k)}=\underbrace{D D \cdots D D}_{k \text { times }}=D \cdot \underbrace{11 \cdots 11}_{k \text { times }}=D \cdot \frac{1}{9} \cdot \underbrace{99 \cdots 99}_{k \text { times }}=D \cdot \frac{1}{9} \cdot(\underbrace{00 \cdots 00}_{k \text { times }}-1)=D \cdot \frac{1}{9} \cdot\left(10^{k}-1\right). Therefore, the following equations are equivalent: P(2k)Q(k)=(R(k))2P_{(2k)}-Q_{(k)}=\left(R_{(k)}\right)^{2}, P19(102k1)Q19(10k1)=(R19(10k1))2P \cdot \frac{1}{9} \cdot\left(10^{2k}-1\right)-Q \cdot \frac{1}{9} \cdot\left(10^{k}-1\right)=\left(R \cdot \frac{1}{9} \cdot\left(10^{k}-1\right)\right)^{2}, P19(102k1)Q19(10k1)=R2181(10k1)2P \cdot \frac{1}{9} \cdot\left(10^{2k}-1\right)-Q \cdot \frac{1}{9} \cdot\left(10^{k}-1\right)=R^{2} \cdot \frac{1}{81} \cdot\left(10^{k}-1\right)^{2}, 9P(102k1)9Q(10k1)=R2(10k1)29P \cdot\left(10^{2k}-1\right)-9Q \cdot\left(10^{k}-1\right)=R^{2} \cdot\left(10^{k}-1\right)^{2}, 9P(10k1)(10k+1)9Q(10k1)=R2(10k1)9P \cdot\left(10^{k}-1\right)\left(10^{k}+1\right)-9Q \cdot\left(10^{k}-1\right)=R^{2} \cdot\left(10^{k}-1\right) (since 10k1010^{k}-1 \neq 0), 9P10k+9K9Q=R210kR29P \cdot 10^{k}+9K-9Q=R^{2} \cdot 10^{k}-R^{2}, 9P9Q+R2=10k(R29P)9P-9Q+R^{2}=10^{k}\left(R^{2}-9P\right). We consider three cases: 3k2018,k=13 \leq k \leq 2018, k=1, and k=2k=2. Case 1: 3k20183 \leq k \leq 2018. Suppose that R29P0R^{2}-9P \neq 0. Since k3k \geq 3, then 10k(R29P)>100010^{k}\left(R^{2}-9P\right)>1000 if R29P>0R^{2}-9P>0 and 10k(R29P)<100010^{k}\left(R^{2}-9P\right)<-1000 if R29P<0R^{2}-9P<0. Since P,Q,RP, Q, R are digits, then 9P9Q+R29P-9Q+R^{2} is at most 9(9)9(0)+92=1629(9)-9(0)+9^{2}=162 and 9P9Q+R29P-9Q+R^{2} is at least 9(0)9(9)+02=819(0)-9(9)+0^{2}=-81. This means that if R29P0R^{2}-9P \neq 0, we cannot have 9P9Q+R2=10k(R29P)9P-9Q+R^{2}=10^{k}\left(R^{2}-9P\right) since the possible values do not overlap. So if 3k20183 \leq k \leq 2018, we must have R29P=0R^{2}-9P=0 and so 9P9Q+R2=09P-9Q+R^{2}=0. If R2=9PR^{2}=9P, then R2R^{2} is a multiple of 3 and so RR is a multiple of 3. Since RR is a positive digit, then R=3R=3 or R=6R=6 or R=9R=9. If R=3R=3, then 9P=R2=99P=R^{2}=9 and so P=1P=1. Since 9P9Q+R2=09P-9Q+R^{2}=0, then 9Q=9(1)+9=189Q=9(1)+9=18 and so Q=2Q=2. If R=6R=6, then 9P=R2=369P=R^{2}=36 and so P=4P=4. Since 9P9Q+R2=09P-9Q+R^{2}=0, then 9Q=9(4)+36=729Q=9(4)+36=72 and so Q=8Q=8. If R=9R=9, then 9P=R2=819P=R^{2}=81 and so P=9P=9. Since 9P9Q+R2=09P-9Q+R^{2}=0, then 9Q=9(9)+81=1629Q=9(9)+81=162 and so QQ cannot be a digit. Therefore, in the case where 3k20183 \leq k \leq 2018, we obtain the quadruples (P,Q,R,k)=(1,2,3,k)(P, Q, R, k)=(1,2,3, k) and (P,Q,R,k)=(4,8,9,k)(P, Q, R, k)=(4,8,9, k). Since there are 20183+1=20162018-3+1=2016 possible values of kk, then we have 22016=40322 \cdot 2016=4032 quadruples so far. Case 2: k=1k=1. Here, the equation 9P9Q+R2=10k(R29P)9P-9Q+R^{2}=10^{k}\left(R^{2}-9P\right) becomes 9P9Q+R2=10R290P9P-9Q+R^{2}=10R^{2}-90P or 99P=9R2+9Q99P=9R^{2}+9Q or 11P=R2+Q11P=R^{2}+Q. For each possible value of PP from 1 to 9, we determine the possible values of QQ and RR by looking for perfect squares that are at most 9 less than 11P11P. P=1P=1: Here, 11P=1111P=11 which is close to squares 4 and 9. We obtain (R,Q)=(2,7),(3,2)(R, Q)=(2,7),(3,2). P=2P=2: Here, 11P=2211P=22 which is close to the square 16. We obtain (R,Q)=(4,6)(R, Q)=(4,6). P=3P=3: Here, 11P=3311P=33 which is close to the square 25. We obtain (R,Q)=(5,8)(R, Q)=(5,8). P=4P=4: Here, 11P=4411P=44 which is close to the square 36. We obtain (R,Q)=(6,8)(R, Q)=(6,8). P=5P=5: Here, 11P=5511P=55 which is close to the square 49. We obtain (R,Q)=(7,6)(R, Q)=(7,6). P=6P=6: Here, 11P=6611P=66 which is close to the square 64. We obtain (R,Q)=(8,2)(R, Q)=(8,2). P=7P=7: There are no perfect squares between 68 and 76, inclusive. P=8P=8: Here, 11P=8811P=88 which is close to the square 81. We obtain (R,Q)=(9,7)(R, Q)=(9,7). P=9P=9: There are no perfect squares between 90 and 98, inclusive. Since k=1k=1 in each of these cases, we obtain an additional 8 quadruples. Case 3: k=2k=2. Here, the equation 9P9Q+R2=10k(R29P)9P-9Q+R^{2}=10^{k}\left(R^{2}-9P\right) becomes 9P9Q+R2=100R2900P9P-9Q+R^{2}=100R^{2}-900P or 909P=99R2+9Q909P=99R^{2}+9Q or 101P=11R2+Q101P=11R^{2}+Q. As PP ranges from 1 to 9, the possible values of 101P101P are 101, 202, 303, 404, 505, 606, 707, 808, 909. As RR ranges from 1 to 9, the possible values of 11R211R^{2} are 11,44,99,176,275,396,539,704,89111,44,99,176,275,396,539,704,891. The pairs of integers in the first and second lists that differ by at most 9 are (i) 101 and 99 (which give (P,Q,R)=(1,2,3)(P, Q, R)=(1,2,3)), (ii) 404 and 396 (which give (P,Q,R)=(4,8,6)(P, Q, R)=(4,8,6)), and (iii) 707 and 704 (which give (P,Q,R)=(7,3,8)(P, Q, R)=(7,3,8)). Since k=2k=2 in each of these cases, we obtain an additional 3 quadruples. In total, there are thus N=4032+8+3=4043N=4032+8+3=4043 quadruples. The sum of the digits of NN is 4+0+4+3=114+0+4+3=11.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.