Maths Olympiad Prep

Library / /813 of 860

Number theory Difficulty 5.6 AIME, harder Find the answer

Let SS be the set of all 3-digit numbers with all digits in the set {1,2,3,4,5,6,7}\{1,2,3,4,5,6,7\} (so in particular, all three digits are nonzero). For how many elements abc\overline{a b c} of SS is it true that at least one of the (not necessarily distinct) 'digit cycles' abc,bca,cab\overline{a b c}, \overline{b c a}, \overline{c a b} is divisible by 7? (Here, abc\overline{a b c} denotes the number whose base 10 digits are a,ba, b, and cc in that order.)

A number or a short expression. Spacing and $ signs are ignored.

Solution

Since the value of each digit is restricted to {1,2,,7}\{1,2, \ldots, 7\}, there is exactly one digit representative of each residue class modulo 7. Note that 7abc7 \mid \overline{a b c} if and only if 100a+10b+c0(mod7)100 a+10 b+c \equiv 0(\bmod 7) or equivalently 2a+3b+c02 a+3 b+c \equiv 0. So we want the number of triples of residues (a,b,c)(a, b, c) such that at least one of 2a+3b+c0,2b+3c+a02 a+3 b+c \equiv 0,2 b+3 c+a \equiv 0, 2c+3a+b02 c+3 a+b \equiv 0 holds. Let the solution sets of these three equations be S1,S2,S3S_{1}, S_{2}, S_{3} respectively, so by PIE and cyclic symmetry we want to find 3S13S1S2+S1S2S33\left|S_{1}\right|-3\left|S_{1} \cap S_{2}\right|+\left|S_{1} \cap S_{2} \cap S_{3}\right|. Clearly S1=72\left|S_{1}\right|=7^{2}, since for each of aa and bb there is a unique cc that satisfies the equation. For S1S2S_{1} \cap S_{2}, we may eliminate aa to get the system 02(2b+3c)(3b+c)=b+5c0 \equiv 2(2 b+3 c)-(3 b+c)=b+5 c (and a2b3c)\left.a \equiv-2 b-3 c\right), which has 7 solutions (one for each choice of cc). For S1S2S3S1S2S_{1} \cap S_{2} \cap S_{3} \subseteq S_{1} \cap S_{2}, we have from the previous paragraph that b5cb \equiv-5 c and a10c3c0a \equiv 10 c-3 c \equiv 0. By cyclic symmetry, b,c0b, c \equiv 0 as well, so there's exactly 1 solution in this case. Thus the answer is 37237+1=1273 \cdot 7^{2}-3 \cdot 7+1=127.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.