Olympiad Maths Prep

Track / Stage 6 / 284 of 400 #1284 of 2000

Problem 1284

National olympiad, first round
Combinatorics Difficulty 6.5 Find the answer

Let AA be the number of 2019-digit numbers, that is made of 2 different digits (For example 101...12016010\underbrace{1...1}_{2016}0 is such number). Determine the highest power of 3 that divides AA.

Official solution

1. **Define A A :**
Let A A be the number of 2019-digit numbers made of 2 different digits. We can split A A into two parts:
A=A0+A1 A = A_0 + A_1
where A0 A_0 is the number of 2019-digit numbers made of the digit 0 0 and another digit k k (where 1k9 1 \le k \le 9 ), and A1 A_1 is the number of 2019-digit numbers made of two different non-zero digits.

2. **Calculate A0 A_0 :**
- A number containing only the digits k k and 0 0 must begin with k k (since it is a 2019-digit number and cannot start with 0).
- The remaining 2018 digits can be any combination of k k and 0 0 , except the configuration with all 2018 digits being k k .
- For a fixed k k , there are 220181 2^{2018} - 1 such numbers.
- Since there are 9 possible values for k k (from 1 to 9), we have:
A0=9×(220181) A_0 = 9 \times (2^{2018} - 1)

3. **Calculate A1 A_1 :**
- Let a,b{1,2,,9} a, b \in \{1, 2, \ldots, 9\} with ab a \neq b .
- A number which begins with the digit a a can continue with any combination of a a and b b , except the configuration with all 2018 digits being a a .
- Similarly, a number which begins with the digit b b can continue with any combination of a a and b b , except the configuration with all 2018 digits being b b .
- Hence, there are 2×(220181) 2 \times (2^{2018} - 1) numbers containing only the digits a a and b b (i.e., 220181 2^{2018} - 1 numbers beginning with a a and 220181 2^{2018} - 1 numbers beginning with b b ).
- With the elements of the set {1,2,,9} \{1, 2, \ldots, 9\} , we can form (92)=36 \binom{9}{2} = 36 distinct pairs (a,b) (a, b) (since (a,b) (a, b) and (b,a) (b, a) are not distinct).
- Therefore:
A1=36×2×(220181)=72×(220181) A_1 = 36 \times 2 \times (2^{2018} - 1) = 72 \times (2^{2018} - 1)

4. **Combine A0 A_0 and A1 A_1 :**
A=A0+A1=9×(220181)+72×(220181)=81×(220181) A = A_0 + A_1 = 9 \times (2^{2018} - 1) + 72 \times (2^{2018} - 1) = 81 \times (2^{2018} - 1)

5. **Determine the highest power of 3 that divides A A :**
A=81×(220181)=34×(220181) A = 81 \times (2^{2018} - 1) = 3^4 \times (2^{2018} - 1)
We need to find ν3(220181) \nu_3(2^{2018} - 1) .

6. **Calculate ν3(220181) \nu_3(2^{2018} - 1) :**
- We use the fact that 261(mod9) 2^6 \equiv 1 \pmod{9} (since 26=641(mod9) 2^6 = 64 \equiv 1 \pmod{9} ).
- Since 2018=6×336+2 2018 = 6 \times 336 + 2 , we have:
22018=(26)336×221336×44(mod9) 2^{2018} = (2^6)^{336} \times 2^2 \equiv 1^{336} \times 4 \equiv 4 \pmod{9}
- Therefore:
220181413(mod9) 2^{2018} - 1 \equiv 4 - 1 \equiv 3 \pmod{9}
- This implies:
ν3(220181)=1 \nu_3(2^{2018} - 1) = 1

7. Combine the results:
ν3(A)=ν3(34)+ν3(220181)=4+1=5 \nu_3(A) = \nu_3(3^4) + \nu_3(2^{2018} - 1) = 4 + 1 = 5

The final answer is ν3(A)=5 \boxed{ \nu_3(A) = 5 }

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