Maths Olympiad Prep

Track / Stage 5 / 362 of 400 #962 of 1964

Problem 962

AIME late
Combinatorics Difficulty 5.9 Find the answer

Using only the digits 2,32,3 and 99, how many six-digit numbers can be formed which are divisible by 66?

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

Official solution

To determine how many six-digit numbers can be formed using only the digits 2,3,2, 3, and 99 that are divisible by 66, we need to consider the properties of numbers divisible by 66. A number is divisible by 66 if and only if it is divisible by both 22 and 33.

1. **Divisibility by 22:**
- A number is divisible by 22 if its last digit is even. Since we are restricted to the digits 2,3,2, 3, and 99, the only even digit available is 22. Therefore, the last digit of our six-digit number must be 22.

2. **Divisibility by 33:**
- A number is divisible by 33 if the sum of its digits is divisible by 33. Let’s denote our six-digit number as abcde2abcde2, where a,b,c,d,ea, b, c, d, e are the first five digits, and the last digit is 22.

- The sum of the digits of the number is a+b+c+d+e+2a + b + c + d + e + 2. For this sum to be divisible by 33, the sum a+b+c+d+ea + b + c + d + e must be congruent to 1(mod3)1 \pmod{3} (since 22(mod3)2 \equiv 2 \pmod{3}).

3. **Possible values for a,b,c,d,ea, b, c, d, e:**
- The digits 33 and 99 are both 0(mod3)0 \pmod{3}.
- The digit 22 is 2(mod3)2 \pmod{3}.

We need to find combinations of a,b,c,d,ea, b, c, d, e such that their sum is 1(mod3)1 \pmod{3}. This can be achieved by having either 22 or 55 digits equal to 22 among a,b,c,d,ea, b, c, d, e.

4. **Case 1: Five 22's**
- If all five digits are 22, then the number is 222222222222. This is a valid number and there is only 11 way to form this number.

5. **Case 2: Two 22's and three other digits**
- We need to choose 22 positions out of 55 for the digit 22. The number of ways to choose 22 positions out of 55 is given by (52)\binom{5}{2}.
- The remaining 33 positions can be filled with either 33 or 99. Each of these 33 positions has 22 choices (either 33 or 99).

Therefore, the number of ways to arrange two 22's and three other digits is:
(52)×23=10×8=80 \binom{5}{2} \times 2^3 = 10 \times 8 = 80

6. Total number of valid six-digit numbers:
- Adding the number of ways from both cases, we get:
1+80=81 1 + 80 = 81

Thus, the total number of six-digit numbers that can be formed using the digits 2,3,2, 3, and 99 and are divisible by 66 is 81\boxed{81}.

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