Competition problem — Combinatorics

Library / /128 of 129

Combinatorics Difficulty 7.4 National Olympiad, round 2 Prove it Slovenia

Twelve balls are numbered by the numbers $1$ , $2$ , $3$ , $\ldots$ , $12$ . Each ball is coloured either red or green, so that the following two conditions are satisfied:

a. If two balls marked by different numbers $a$ and $b$ are coloured red and $a+b < 13$ , then the ball marked by the number $a+b$ is coloured red, too.

b. If two balls marked by different numbers $a$ and $b$ are coloured green and $a+b < 13$ , then the ball marked by the number $a+b$ is also coloured green.

How many ways are there of colouring the balls?

Solution

Assume that the ball denoted by $1$ is red. If the ball denoted by $2$ is also red, then $1+2=3$ , $1+3=4$ , $\ldots$ , $1+11=12$ are also red. So in this case all balls are red.

If the ball denoted by $2$ is green, we have to consider two more cases. If the ball number $3$ is red, then $1+3=4$ , $1+4=5$ , $\ldots$ , $1+11=12$ are also red. If the ball number $3$ is green, then $2+3=5$ is also green. Since $1+4=5$ , $5$ is green and $1$ is red, the ball denoted by $4$ cannot be red and must therefore be green. Then $4+2=6$ , $5+2=7$ , $6+2=8$ , $\ldots$ , $9+2=11$ , $10+2=12$ are also green.

There were three possible cases. If we exchange red and green in the arguments above, we get three more cases. There are $6$ cases altogether, namely: all balls are red, all balls are green, all balls but number $1$ are green, all balls but number $1$ are red, all balls but number $2$ are red or all balls but number $2$ are green.

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.