Browse · MathNet
PrintRioplatense Mathematical Olympiad
Argentina number theory
Problem
The 400-digit number , which is formed by 100 copies of , is written on a blackboard. Lionel has to erase some of the digits of in such a way that the resulting number is divisible by , and the largest possible. Determine which digits Lionel should erase.
Solution
Notice that . Let be the resulting number after Lionel erases some digits. We want to be even, so we must erase the rightmost . We also want to be divisible by . For this to happen, the sum of digits of must be divisible by . Initially, the sum of digits equals . Since erasing digits or does not alter the congruence class modulo , we must erase some digits . If we erase of these digits, then will be equivalent to modulo . This number is divisible by if and only if , hence , i.e., we must remove at least two digits .
So far, we have proved that Lionel needs to remove at least two digits and one digit . Suppose it is possible to erase only those three digits, and let us now think about how to obtain the largest possible multiple of in this situation. To obtain a multiple of , the last digit should be removed (otherwise, the last two digits of would be ). So we have the following number, in which we must erase one more digit : We will not erase the last digit , as would end up not being divisible by . We classify the rest of the 's in two groups: those that are the first digit of a block and those that are the third digit of a block. If we remove one of the latter, then will have the form Since and are divisible by and is not, this number is not divisible by . Hence we must remove the leading digit of some block. In order to obtain the highest possible number, it is always preferable to choose a block from the right, since . 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 ), whereas choosing the third rightmost block does work. So Lionel's final number is:
So far, we have proved that Lionel needs to remove at least two digits and one digit . Suppose it is possible to erase only those three digits, and let us now think about how to obtain the largest possible multiple of in this situation. To obtain a multiple of , the last digit should be removed (otherwise, the last two digits of would be ). So we have the following number, in which we must erase one more digit : We will not erase the last digit , as would end up not being divisible by . We classify the rest of the 's in two groups: those that are the first digit of a block and those that are the third digit of a block. If we remove one of the latter, then will have the form Since and are divisible by and is not, this number is not divisible by . Hence we must remove the leading digit of some block. In order to obtain the highest possible number, it is always preferable to choose a block from the right, since . 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 ), whereas choosing the third rightmost block does work. So Lionel's final number is:
Final answer
Erase exactly three digits: the last three of the whole number, the two immediately before it so the number ends with twenty, and the leading two of the third block from the right among the remaining full 2023 blocks. Equivalently, the final number is ninety-six copies of 2023, then 023, then 2023, then 2023, followed by 20.
Techniques
Divisibility / FactorizationModular Arithmetic