Maths Olympiad Prep

Library / Romanian Mathematical Olympiad /157 of 275

Romanian Mathematical Olympiad

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 b≥a+2b \ge a + 2, c≥b+2≥a+4c \ge b + 2 \ge a + 4, d≥c+2≥a+6d \ge c + 2 \ge a + 6, e≥d+2≥a+8e \ge d + 2 \ge a + 8 and f≥e+2≥a+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 x∣pqrsmn‾x \mid \overline{pqrsmn} and x∣pqrsnm‾x \mid \overline{pqrsnm}, hence x∣pqrsmn‾−pqrsnm‾=9(m−n)x \mid \overline{pqrsmn} - \overline{pqrsnm} = 9(m-n). Since m−n=1m-n=1, we find x∣9x \mid 9.
If 3∤a+b+c+d+e+f3 \nmid a + b + c + d + e + f, the only possibility is x=1x = 1.
If 3∣a+b+c+d+e+f3 \mid a + b + c + d + e + f and 9∤a+b+c+d+e+f9 \nmid a + b + c + d + e + f, then x=1x = 1 or x=3x = 3.
If 9∣a+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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.