Maths Olympiad Prep

Library / /19 of 34

Number theory Difficulty 5.9 AIME, harder Prove it Romania

One considers the non-zero distinct digits a,b,c,d,e,fa, b, c, d, e, f. Determine the positive integers xx, such that xx divides any 6-digit number written with the digits a,b,c,d,e,fa, b, c, d, e, f.

Solution

For any choice of 6 distinct non-zero digits, at least two of them are consecutive.
Indeed, if a<b<c<d<e<fa < b < c < d < e < f and no digits are consecutive, then ba+2b \ge a + 2, cb+2a+4c \ge b + 2 \ge a + 4, dc+2a+6d \ge c + 2 \ge a + 6, ed+2a+8e \ge d + 2 \ge a + 8 and fe+2a+10f \ge e + 2 \ge a + 10, which is impossible, since both aa and ff are digits.
Denote by mm and nn, m>nm > n, two consecutive digits among a,b,c,d,e,fa, b, c, d, e, f, and by p,q,r,sp, q, r, s the other four digits.
We have xpqrsmnx \mid \overline{pqrsmn} and xpqrsnmx \mid \overline{pqrsnm}, hence xpqrsmnpqrsnm=9(mn)x \mid \overline{pqrsmn} - \overline{pqrsnm} = 9(m-n). Since mn=1m-n=1, we find x9x \mid 9.
If 3a+b+c+d+e+f3 \nmid a + b + c + d + e + f, the only possibility is x=1x = 1.
If 3a+b+c+d+e+f3 \mid a + b + c + d + e + f and 9a+b+c+d+e+f9 \nmid a + b + c + d + e + f, then x=1x = 1 or x=3x = 3.
If 9a+b+c+d+e+f9 \mid a + b + c + d + e + f, then x=1,x=3x = 1, x = 3 or x=9x = 9.

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.