Maths Olympiad Prep

Library / /135 of 196

Number theory Difficulty 5.6 AIME, harder Prove it Soviet Union

Problem:

A six digit (decimal) number has six different digits, none of them 00, and is divisible by 3737. Show that you can obtain at least 2323 other numbers which are divisible by 3737 by permuting the digits.

Solution

Solution:

Suppose the digits are a1,a2,a3,a4,a5,a6a_1, a_2, a_3, a_4, a_5, a_6 and that a1a2a3a4a5a6a_1a_2a_3a_4a_5a_6 is divisible by 3737. We claim that a2a3a4a5a6a1a_2a_3a_4a_5a_6a_1 is also divisible by 3737. Put n=a2a3a4a5a6n = a_2a_3a_4a_5a_6 and m=a1m = a_1. The original number is 105m+n10^{5}m + n and the derived number is 10n+m10n + m. But 3737 divides 103110^{3} - 1 and hence also 106110^{6} - 1 and m(1061)m(10^{6} - 1). So it also divides 10(105m+n)m(1061)=10n+m10(10^{5}m + n) - m(10^{6} - 1) = 10n + m, which proves the claim.

Iterating, we get the original number and 55 others:

a1a2a3a4a5a6
a2a3a4a5a6a1
a3a4a5a6a1a2
a4a5a6a1a2a3
a5a6a1a2a3a4
a6a1a2a3a4a5

Similarly, we have that a1a2a3a4a5a6a1a2a6a4a5a3=(a6a3)999a_1a_2a_3a_4a_5a_6 - a_1a_2a_6a_4a_5a_3 = (a_6- a_3)999, so a1a2a6a4a5a3a_1a_2a_6a_4a_5a_3 is also divisible by 3737. Iterating we get:

a1a2a6a4a5a3
a2a6a4a5a3a1
a6a4a5a3a1a2
a4a5a3a1a2a6
a5a3a1a2a6a4
a3a1a2a6a4a5

Similarly, we could swap the first term and the fourth to get:

a4a2a3a1a5a6
a2a3a1a5a6a4
a3a1a5a6a4a2
a1a5a6a4a2a3
a5a6a4a2a3a1
a6a4a2a3a1a5

or the second and the fifth to get:

a1a5a3a4a2a6
a5a3a4a2a6a1
a3a4a2a6a1a5
a4a2a6a1a5a3
a2a6a1a5a3a4
a6a1a5a3a4a2

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.