16. Gianni owns 60 balls, numbered from 1 to 60. One day, after realizing he had lost ball number 1, he decides to color the remaining 59 balls, following this rule: each number must have the same color as all its multiples. At most, how many different colors can Gianni use to color the 59 balls?
(A) 2 (B) 10
(C) 8
(D) 17
(E) 12

## Unione Matematica Italiana  PROGETTO OLIMPIADI DI MATEMATICA

Ministry of Education, University and Research

Scuola Normale Superiore

T2 Archimedes Games - Biennio Competition

## November 25, 2015

- The test consists of 16 problems; each question is followed by five answers indicated by the letters (A), (B), (C), (D), (E).
- Only one of these answers is correct, the other 4 are wrong. Each correct answer is worth 5 points, each wrong answer is worth 0 points, and each problem left unanswered is worth 1 point.
- For each of the problems, you must write the letter corresponding to the answer you believe is correct in the grid reported below. No erasures or corrections on the grid are allowed. The use of any type of calculator or communication device is not permitted.

## The time you have to complete the test is 2 hours.

 Good luck and have fun! NAME

LAST NAME

class:

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Problem 16. The answer is (C).

If $p$ is a prime number such that $2 p \leq 60$, since 2 and $p$ have a common multiple among those used, it follows that the balls numbered $2, 2p$, and also $p$ must be colored the same way. Therefore, once the color for ball $\mathrm{n}^{\circ} 2$ is chosen, the same color must be used for all prime numbers that do not exceed 30 and, consequently, for all balls that have such numbers among their factors.

The only numbers that remain excluded, therefore, from the color chosen for ball $\mathrm{n}^{\circ} 2$ are the prime numbers greater than 30, namely $31, 37, 41, 43, 47, 53, 59$, which Gianni can color freely.

Thus, it is possible to use at most 8 colors.

(Problem proposed by A. Pesare)