Competition problem — Combinatorics

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

The lottery cards of a certain lottery contain all nine-digit numbers that can be formed with the digits $1$ , $2$ and $3$ . There is exactly one number on each lottery card. There are only red, yellow and blue lottery cards. Two lottery numbers that differ from each other in all nine digits always appear on cards of different color. Someone draws a red card and a yellow card. The red card has the number $122222222$ and the yellow card has the number $222222222$ . The first prize goes to the lottery card with the number $123123123$ . What color(s) can it possibly have? Prove your answer.

Solution

Solution:

First, it can in fact be red, if, say, cards are colored based on the first digit only ( $1=$ red, $2=$ yellow, $3=$ blue $)$ . We now endeavor to show it must be red.

Consider the cards $333133133$ and $331331331$ : they each differ in all their digits from $122222222$ and from $222222222$ , so they must both be blue. Now $211311311$ differs in all its digits from both $122222222$ and $333133133$ , so it must be yellow. Finally, $123123123$ differs in all its digits from both $331331331$ and $211311311$ , so it must be red.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.