Maths Olympiad Prep

Library / /55 of 63

Number theory Difficulty 7.6 National olympiad, round 2 Prove it Japan

Suppose we denote by n(10)n_{(10)} the decimal representation for a positive integer nn. Suppose three distinct positive integers a,b,ca, b, c satisfy all of the following conditions:
* c(10)c_{(10)} coincides with the number obtained by removing a 6 from a(10)a_{(10)}.
* c(10)c_{(10)} coincides with the number obtained by removing a 6 from b(10)b_{(10)}.
* The number of digits for aa coincides with the number of digits for bb, and aa is a multiple of bb.
Determine the smallest possible value that cc can have satisfying these conditions.

Solution

We note that under the hypothesis the top digits of a(10)a_{(10)} and b(10)b_{(10)} must be different, since if they are the same, then we get ab<2\frac{a}{b} < 2 which violates the condition that aa is a multiple of bb. Therefore, we must have the top digit of a(10)a_{(10)} or b(10)b_{(10)} to be 6, but if the top digit of b(10)b_{(10)} is 6, then the fact that a2ba \ge 2b forces aa to have more digits than bb, contradicting the assumption. Therefore, the top digit of a(10)a_{(10)} must be 6. Furthermore, since the number of digits of aa and bb are the same, ab\frac{a}{b} must be one of the numbers 2, 3, 4, 5, 6. Let us call this number mm.

Next, we will show that if cc is the minimum number satisfying the conditions, then the 6 to be removed from b(10)b_{(10)} to get c(10)c_{(10)} must be one of the last three digits of b(10)b_{(10)}. First we note that the minimality of cc implies that bb cannot be a multiple of 10. For if the last digit of bb is 0, this forces the last digit of both a(10)a_{(10)} and c(10)c_{(10)} to be 0, and thus dividing every one of a,b,ca, b, c by 10, we get a triple satisfying all the conditions, thereby violating the minimality of cc. Now if the 6 to be removed from b(10)b_{(10)} to get c(10)c_{(10)} is not among the last three digits of bb, then we must have ab(mod1000)a \equiv b \pmod{1000}. But from the fact a=mba = mb it follows that (m1)b0(mod1000)(m-1)b \equiv 0 \pmod{1000}, from which it follows that bb is a multiple of 10, as m1{1,2,3,4,5}m-1 \in \{1, 2, 3, 4, 5\}, but this is impossible.

Next, we separate the cases depending on which digit the 6 to be removed from b(10)b_{(10)} lies. We keep in mind that bb is not a multiple of 10 in the following discussion.

(1) Case when 6 to be removed is the last digit of bb.
Since amb(mod10)a \equiv mb \pmod{10} the fact that b6(mod10)b \equiv 6 \pmod{10} determines the last digit of a(10)a_{(10)}, which would be equal to the next to the last digit of b(10)b_{(10)}. The consideration in terms of mod100\mod 100, then determines the next to the last digit of a(10)a_{(10)}, which equals the third digit from the bottom of b(10)b_{(10)}. Continuing in this fashion, one can determine the digits of a(10)a_{(10)} one by one from the bottom up. If the nn-th digit from the bottom of a(10)a_{(10)} equals 6, then we let a,ba, b be what are determined thus far. If this pair satisfies amb(mod10n)a \equiv mb \pmod{10^n}, then with c(10)c_{(10)} determined from b(10)b_{(10)} by removing the 6 in the last digit of b(10)b_{(10)}, we have the triple (a,b,c)(a, b, c) satisfying all the conditions. If the value of mm is given, then the cc obtained in this way will be the minimum one under the condition (1).
Checking for each of the cases m=2,3,4,5,6m = 2, 3, 4, 5, 6 we see that with m=4m = 4, we get a=615383a = 615383, b=153846b = 153846 and the corresponding c=15384c = 15384 gives the minimum.

(2) Case when 6 to be removed is next to the last digit of bb.
From amb(mod10)a \equiv mb \pmod{10} and ab(mod10)a \equiv b \pmod{10} we can determine the last digit of a,ba, b to be 2, 4, 6 or 8 if m=6m = 6, and be 5 if m=3m = 3 or 5. If we check each of these possibilities as we have done in the case (1), we see that in each case the cc obtained has at least 6 digits.

(3) Case when 6 to be removed is the third digit from the bottom of bb.
From amb(mod100)a \equiv mb \pmod{100} and ab(mod100)a \equiv b \pmod{100} we can get that the last two digits of a,ba, b are 25 and 75 respectively. If we check these cases further as we have done in the case (1), we see that in each case we get a cc having at least 6 digits.

Consequently, we can conclude that the smallest possible cc desired is 15348.

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.