Maths Olympiad Prep

Library / /15 of 19

Combinatorics Difficulty 6.5 National olympiad Prove it North Macedonia

Let nn three-digit numbers satisfy the following properties:
(1) No number contains the digit 00.
(2) The sum of the digits of each number is 99.
(3) The units digits of any two numbers are different.
(4) The tens digits of any two numbers are different.
(5) The hundreds digits of any two numbers are different.
Find the largest possible value of nn.

Solution

Let SS denote the set of three-digit numbers that have digit sum equal to 99 and no digit equal to 00. We will first find the cardinality of SS. We start from the number 111111 and each element of SS can be obtained from 111111 by a string of 6A6A's (which means that we add 11 to the current digit). Then for example 324324 can be obtained from 111111 by the string AAGAGAAA. There are in total
8!6!2!=28 \frac{8!}{6! \cdot 2!} = 28
such words, so SS contains 2828 numbers. Now, from the conditions (3), (4) and (5), if abc\overline{abc} is in SS then each of the other numbers of the form c\overline{**c} cannot be in SS, neither b\overline{*b*} can be, nor a\overline{a**}.

Since there are a+b2a+b-2 numbers of the first category, a+c2a+c-2 from the second and b+c2b+c-2 from the third one. In these three categories there are
(a+b2)+(a+c2)+(b+c2)=2(a+b+c)6=296=12 (a+b-2)+(a+c-2)+(b+c-2)=2(a+b+c)-6=2 \cdot 9-6=12
distinct numbers that cannot be in SS if abcabc is in SS. So, if SS has nn numbers, then 12n12n are the forbidden ones that are in SS, but each number from SS can be a forbidden number no more than three times, once for each of its digits, so
n+12n328n285, n + \frac{12n}{3} \le 28 \Leftrightarrow n \le \frac{28}{5},
and since nn is an integer, we get n5n \le 5. A possible example for n=5n=5 is
S={144,252,315,423,531}. S = \{144, 252, 315, 423, 531\}.

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 and solution reproduced as published; topic and difficulty added by this site.