Maths Olympiad Prep

Library / /294 of 310

, 2019

Number theory Difficulty 4.6 AIME Find the answer Canada

How many 7-digit positive integers are made up of the digits 0 and 1 only, and are divisible by 6?

Pick one

Solution

Let nn be a 7-digit positive integer made up of the digits 0 and 1 only, and that is divisible by 6.

The leftmost digit of nn cannot be 0, so must be 1.

Since nn is divisible by 6, then nn is even, which means that the rightmost digit of nn cannot be 1, and so must be 0.

Therefore, nn has the form 1pqrst01\,pqr\,st0 for some digits p,q,r,s,tp,q,r,s,t each equal to 0 or 1.

nn is divisible by 6 exactly when it is divisible by 2 and by 3.

Since the ones digit of nn is 0, then it is divisible by 2.

nn is divisible by 3 exactly when the sum of its digits is divisible by 3.

The sum of the digits of nn is 1+p+q+r+s+t1+p+q+r+s+t.

Since each of p,q,r,s,tp,q,r,s,t is 0 or 1, then 11+p+q+r+s+t61 \leq 1+p+q+r+s+t \leq 6.

Thus, nn is divisible by 3 exactly when 1+p+q+r+s+t1+p+q+r+s+t is equal to 3 or to 6.

That is, nn is divisible by 3 exactly when either 2 of p,q,r,s,tp,q,r,s,t are 1s or all 5 of p,q,r,s,tp,q,r,s,t are 1s.

There are 10 ways for 2 of these to be 1s.

These correspond to the pairs pq,pr,ps,pt,qr,qs,qt,rs,rt,stpq, pr, ps, pt, qr, qs, qt, rs, rt, st.

There is 1 way for all 5 of p,q,r,s,tp,q,r,s,t to be 1s.

Thus, there are 1+10=111 + 10 =11 such 7-digit integers.

Want a route through all this instead of an archive? The track puts 2,444 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.