Maths Olympiad Prep

Track / Stage 3 / 182 of 260 #182 of 1964

Problem 182

AMC 10/12, early questions
Combinatorics Difficulty 3.5 Find the answer

How many positive integers less than 10,000 have at most two different digits?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

First, let's count numbers with only a single digit. We have nine of these for each length, and four lengths, so 36 total numbers.
Now, let's count those with two distinct digits. We handle the cases "0 included" and "0 not included" separately.
There are (92){9 \choose 2} ways to choose two digits, AA and BB. Given two digits, there are 2n22^n - 2 ways to arrange them in an nn-digit number, for a total of (212)+(222)+(232)+(242)=22(2^1 - 2) + (2^2 - 2) + (2^3 -2) + (2^4 - 2) = 22 such numbers (or we can list them: AB,BA,AAB,ABA,BAA,ABB,BAB,BBA,AAAB,AABA,ABAA,AB, BA, AAB, ABA, BAA, ABB, BAB, BBA, AAAB, AABA, ABAA, BAAA,AABB,ABAB,BAAB,ABBA,BABA,BBAA,ABBB,BABB,BBAB,BBBABAAA, AABB, ABAB, BAAB, ABBA, BABA, BBAA, ABBB, BABB, BBAB, BBBA). Thus, we have (92)22=3622=792{9 \choose 2} \cdot 22 = 36\cdot22 = 792 numbers of this form.
Now, suppose 0 is one of our digits. We have nine choices for the other digit. For each choice, we have 2n112^{n - 1} - 1 nn-digit numbers we can form, for a total of (201)+(211)+(221)+(231)=11(2^0 - 1) + (2^1 - 1) + (2^2 - 1) + (2^3 - 1) = 11 such numbers (or we can list them: A0,A00,A0A,AA0,A000,AA00,A0A0,A00A,AAA0,AA0A,A0AAA0, A00, A0A, AA0, A000, AA00, A0A0, A00A, AAA0, AA0A, A0AA). This gives us 911=999\cdot 11 = 99 numbers of this form.
Thus, in total, we have 36+792+99=92736 + 792 + 99 = \boxed{927} such numbers.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.