Maths Olympiad Prep

Track / Stage 6 / 315 of 400 #1315 of 1964

Problem 1315

National olympiad, first round
Number theory Difficulty 6.6 Find the answer

Given that six-digit positive integer ABCDEF\overline{ABCDEF} has distinct digits A,A, B,B, C,C, D,D, E,E, FF between 11 and 88, inclusive, and that it is divisible by 9999, find the maximum possible value of ABCDEF\overline{ABCDEF}.

Proposed by Andrew Milas

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

Official solution

To solve the problem, we need to find the maximum six-digit number ABCDEF\overline{ABCDEF} with distinct digits between 1 and 8 that is divisible by 99. A number is divisible by 99 if and only if it is divisible by both 9 and 11.

1. Divisibility by 9:
A number is divisible by 9 if the sum of its digits is divisible by 9. The digits are distinct and between 1 and 8, so the sum of all possible digits is:
1+2+3+4+5+6+7+8=36 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36
Since 36 is divisible by 9, any permutation of these digits will satisfy the divisibility by 9 condition.

2. Divisibility by 11:
A number is divisible by 11 if the difference between the sum of the digits in the odd positions and the sum of the digits in the even positions is a multiple of 11 (including 0). Let’s denote the digits as A,B,C,D,E,FA, B, C, D, E, F:
(A+C+E)(B+D+F)0(mod11) (A + C + E) - (B + D + F) \equiv 0 \pmod{11}
or
(A+C+E)(B+D+F)11(mod11) (A + C + E) - (B + D + F) \equiv 11 \pmod{11}

3. Maximizing the number:
To maximize ABCDEF\overline{ABCDEF}, we should start with the largest digits and check if they satisfy the divisibility conditions. We will try to place the digits in descending order and check the conditions.

- Start with the largest digits: 8, 7, 6, 5, 4, 3, 2, 1.
- Check the sums of the odd and even positions:
Odd positions: A,C,EEven positions: B,D,F \text{Odd positions: } A, C, E \quad \text{Even positions: } B, D, F
Odd positions sum: 8+6+4=18 \text{Odd positions sum: } 8 + 6 + 4 = 18
Even positions sum: 7+5+3=15 \text{Even positions sum: } 7 + 5 + 3 = 15
1815=3(not a multiple of 11) 18 - 15 = 3 \quad (\text{not a multiple of 11})

- Adjust the digits to satisfy the divisibility by 11 condition. We need to find a permutation where the difference is 0 or 11.

4. Finding the correct permutation:
- Try different permutations while keeping the digits as large as possible.
- After several trials, we find that the permutation 87653412 satisfies both conditions:
Odd positions sum: 8+6+3+1=18 \text{Odd positions sum: } 8 + 6 + 3 + 1 = 18
Even positions sum: 7+5+4+2=18 \text{Even positions sum: } 7 + 5 + 4 + 2 = 18
1818=0(multiple of 11) 18 - 18 = 0 \quad (\text{multiple of 11})

Thus, the maximum possible value of ABCDEF\overline{ABCDEF} that satisfies the given conditions is 87653412\boxed{87653412}.

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