Maths Olympiad Prep

Library / /5 of 18

Number theory Difficulty 6.3 National olympiad Prove it Argentina

The 400-digit number N=202320232023N = 20232023\ldots2023, which is formed by 100 copies of 20232023, is written on a blackboard. Lionel has to erase some of the digits of NN in such a way that the resulting number is divisible by 8484, and the largest possible. Determine which digits Lionel should erase.

Solution

Notice that 84=4×3×784 = 4 \times 3 \times 7. Let MM be the resulting number after Lionel erases some digits. We want MM to be even, so we must erase the rightmost 33. We also want MM to be divisible by 33. For this to happen, the sum of digits of MM must be divisible by 33. Initially, the sum of digits equals 100(2+0+2+3)=7001(mod3)100 \cdot (2 + 0 + 2 + 3) = 700 \equiv 1 \pmod{3}. Since erasing digits 00 or 33 does not alter the congruence class modulo 33, we must erase some digits 22. If we erase xx of these digits, then MM will be equivalent to 7002x700 - 2x modulo 33. This number is divisible by 33 if and only if x2(mod3)x \equiv 2 \pmod{3}, hence x2x \ge 2, i.e., we must remove at least two digits 22.

So far, we have proved that Lionel needs to remove at least two digits 22 and one digit 33. Suppose it is possible to erase only those three digits, and let us now think about how to obtain the largest possible multiple of 8484 in this situation. To obtain a multiple of 44, the last digit 22 should be removed (otherwise, the last two digits of MM would be 0202). So we have the following number, in which we must erase one more digit 22:
[2023][2023][2023]20. [2023][2023]\dots[2023]20.
We will not erase the last digit 22, as MM would end up not being divisible by 44. We classify the rest of the 22's in two groups: those that are the first digit of a 20232023 block and those that are the third digit of a 20232023 block. If we remove one of the latter, then MM will have the form
[2023][2023][203][2023][2023]20. [2023]\dots[2023][203][2023]\dots[2023]20.
Since 20232023 and 203203 are divisible by 77 and 2020 is not, this number is not divisible by 77. Hence we must remove the leading digit of some 20232023 block. In order to obtain the highest possible number, it is always preferable to choose a block from the right, since 0232023<20230230232023 < 2023023. We can see by direct inspection that erasing the leading digit of either of the two last blocks does not work (because the resulting number is not divisible by 77), whereas choosing the third rightmost block does work. So Lionel's final number is:
M=[2023][2023][2023][023][2023][2023]20. M = [2023][2023]\dots[2023][023][2023][2023]20.

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 and solution reproduced as published; topic and difficulty added by this site.