Track / Stage 3 / 79 of 260 #559 of 2444

Problem 559

AMC 10/12, early questions

Combinatorics Difficulty 3.6 Multiple choice CEMC Gauss (Grade 8) · Canada · 2024

The Gaussbot factory assembles robots. Each robot comes in one of
three colours: red, blue, or green. Each robot also has a number stamped
on its head: $1$ , $2$ , $3$ , or $4$ . The $n$ th robot assembled is the first robot to
have the same colour and the same number as a previously assembled
robot. What is the greatest possible value of $n$ ?

Pick one

Official solutions — 2

Solution 1

There are $3$ different
colours and $4$ different numbers,
and therefore $3\times 4=12$
different kinds of robots that may be assembled. (These are R1, R2, R3,
R4, B1, B2, B3, B4, G1, G2, G3, G4, where R, B, G represent the $3$ colours red, blue, green.)

Since there are $12$ different kinds
of robots, it is possible that the first $12$ robots assembled are all different
from one another.

In this case, the $13$ th robot
assembled would be the first robot to have the same colour and the same
number as a previously assembled robot, and thus the greatest possible
value of $n$ is $13$ .

Notes:

It is possible that the first duplicate occurs earlier, but we
want the latest that it can occur.
There must be a duplicate robot among the first $13$ assembled, and so $n<14$ .
This solution makes use of the Pigeonhole principle – a
concept worth further investigation.

Solution 2

Since there are $12$ different kinds
of robots, it is possible that the first $12$ robots assembled are all different
from one another.

In this case, the $13$ th robot
assembled would be the first robot to have the same colour and the same
number as a previously assembled robot, and thus the greatest possible
value of $n$ is $13$ .

Notes:

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.