Maths Olympiad Prep

Library / /533 of 740

Algebra Difficulty 5.2 AIME, harder Prove it United States

Problem:
Compute the number of ways to pick a 3-element subset of
{101+1,102+1,103+1,104+1,105+1,106+1,107+1} \left\{10^{1}+1,10^{2}+1,10^{3}+1,10^{4}+1,10^{5}+1,10^{6}+1,10^{7}+1\right\}
such that the product of the 3 numbers in the subset has no digits besides 0 and 1 when written in base 10.

Solution

Solution:
Given a subset {10a+1,10b+1,10c+1}\left\{10^{a}+1,10^{b}+1,10^{c}+1\right\}, we can directly expand the product of its elements:
(10a+1)(10b+1)(10c+1)=10a+b+c+10b+c+10a+c+10a+b+10a+10b+10c+1. \left(10^{a}+1\right)\left(10^{b}+1\right)\left(10^{c}+1\right)=10^{a+b+c}+10^{b+c}+10^{a+c}+10^{a+b}+10^{a}+10^{b}+10^{c}+1 .
In order for all digits to be 0 or 1, all 7 numbers a+b+c,b+c,a+c,a+b,a,b,ca+b+c, b+c, a+c, a+b, a, b, c should be distinct and nonzero, with the latter being guaranteed.
Without loss of generality, we can assume c>b>ac>b>a. Then,
a+b+c>b+c>a+c>max(a+b,c) a+b+c>b+c>a+c>\max (a+b, c)
and
min(a+b,c)>b>a \min (a+b, c)>b>a
so the only two numbers that could be the same are a+ba+b and cc.
There are 9 triples (a,b,c)(a, b, c) where 1a<b<c71 \leq a<b<c \leq 7 and a+b=ca+b=c, namely (1,2,3),(1,3,4),(1,4,5)(1,2,3),(1,3,4),(1,4,5), (1,5,6),(1,6,7),(2,3,5),(2,4,6),(2,5,7)(1,5,6),(1,6,7),(2,3,5),(2,4,6),(2,5,7), and (3,4,7)(3,4,7). The remaining triples (a,b,c)(a, b, c) all work, so the answer is (73)9=26\binom{7}{3}-9=26.

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.