Maths Olympiad Prep

Library / /737 of 740

Algebra Difficulty 6.0 National Olympiad Prove it United States

Problem:
A positive integer nn is stacked if 2n2 n has the same number of digits as nn and the digits of 2n2 n are multiples of the corresponding digits of nn. For example, 12031203 is stacked because 2×1203=24062 \times 1203 = 2406, and 2,4,0,62, 4, 0, 6 are multiples of 1,2,0,31, 2, 0, 3, respectively. Compute the number of stacked integers less than 10001000.

Solution

Solution:
We do casework on the number of digits of nn.

One digit. There are 44 one-digit stacked integers: 1,2,3,41, 2, 3, 4.

Two digits. Suppose n=abn = \overline{ab} is a two-digit integer. If a<5a < 5 and b<5b < 5, then the digits of 2n2 n are double the respective digits of nn, so nn is stacked; there are 45=204 \cdot 5 = 20 such nn. Otherwise, since 2n<1002 n < 100, we still must have a<5a < 5, so b5b \geq 5. Then the last digit of 2n2 n is 2b102b - 10, so b2b10b \mid 2b - 10, which implies that b=5b = 5. Then the first digit of 2n2 n is 2a+12a + 1, which aa must divide, so a=1a = 1. Thus, the only stacked nn with b5b \geq 5 is 1515. Adding that to the 2020 stacked numbers with b<5b < 5 gives us 2121 two-digit stacked integers.

Three digits. Suppose n=abcn = \overline{abc} is a three-digit integer. If a,ba, b, and cc are all less than 55, then the digits of 2n2 n are double the respective digits of nn, so nn is stacked; there are 455=1004 \cdot 5 \cdot 5 = 100 such nn. Otherwise, since 2n<10002 n < 1000, we must have a<5a < 5. We now casework on which of bb and cc are at least 55.

- If b5b \geq 5 and c5c \geq 5, then the digits of 2n2 n are 2a+1,2b92a + 1, 2b - 9, and 2c102c - 10 in order. Thus, a2a+1a \mid 2a + 1, b2b9b \mid 2b - 9, and c2c10c \mid 2c - 10, which implies a=1a = 1, b=9b = 9, and c=5c = 5. Thus 195195 is the only stacked number in this case.

- If c5c \geq 5 only, then 2n=200a+2bc2 n = 200a + 2\overline{bc} has first digit 2a2a and last two digits 2bc2\overline{bc}, so nn is stacked if and only if bc\overline{bc} to be stacked. Since c5c \geq 5, as proved before, the only such stacked bc\overline{bc} is 1515, so we get 44 stacked numbers in this case: 115,215,315115, 215, 315, and 415415.

- If b5b \geq 5 only, then 2n2 n has last digit 2c2c and first two digits 2ab2\overline{ab}, so nn is stacked if and only if ab\overline{ab} to be stacked. As b5b \geq 5, similar to the previous case, the only such stacked ab\overline{ab} is ab=15\overline{ab} = 15, so we get 55 stacked numbers in this case: 150,151,152,153150, 151, 152, 153, and 154154.

Summing over all cases, there are 100+1+4+5=110100 + 1 + 4 + 5 = 110 three-digit stacked integers.

Our final answer is 4+21+110=1354 + 21 + 110 = 135.

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.