1) Alice wants to color the integers between 2 and 8 (inclusive) using $k$ colors. She wishes that if $m$ and $n$ are integers between 2 and 8 such that $m$ is a multiple of $n$ and $m \neq n$, then $m$ and $n$ are of different colors. Determine the smallest integer $k$ for which Alice can color the integers $2,3, \ldots, 8$ using $k$ colors.
2) Alice wants to color the integers between 2 and 31 (inclusive) using $k$ colors. She wishes that if $m$ and $n$ are integers between 2 and 31 such that $m$ is a multiple of $n$ and $m \neq n$, then $m$ and $n$ are of different colors. Determine the smallest integer $k$ for which Alice can color the integers $2,3, \ldots, 31$ using $k$ colors.
In this problem, we are looking for the smallest integer $k$ satisfying a certain property. Suppose we want to show that the smallest integer sought is the integer $c$. There will then be two parts to the proof. On the one hand, it is necessary to show that if an integer $k$ satisfies the property, then $k \geqslant c$, on the other hand, it is necessary to show that we can indeed find a coloring of the integers with $c$ colors.

1) First, let's try to color the integers as we go in a naive way:

- We color 2 with the first color
- We also color 3 with the first color (it is possible because 2 does not divide 3).
- 4 is divisible by 2, so we cannot color it with the same color as 2, we therefore color it with another color (the second color).
- We can color 5 with the first color.
- 6 being divisible by 2 and 3, we color it with the second color.
- We can color 7 with the first color.
- But 8 is divisible by 2 and 4, it must therefore be colored with a third color.

We have thus obtained a coloring with 3 colors of the integers from 2 to 8. It is now necessary to verify that 3 colors are necessarily required in a coloring satisfying the property of the statement. In the previous construction, the problem was to color 8. Indeed, 8 is a multiple of 4 and 2 and 4 is a multiple of 2. Thus 4 cannot have the same color as 2 and 8 cannot have the same color as 2 or 4. Therefore, at least 3 different colors are needed to color $2,4,8$, so the smallest number of colors necessary is $k=3$.

2) Here, let's be inspired by the first question. We saw that $2,4,8$ were the numbers bringing a constraint in the coloring. We notice that these are powers of 2. We can therefore conjecture that the powers of 2 play an important role in the problem. Among the integers from 2 to 32, there are 5 powers of $2: 2,4,8$ and 16. As 2 divides $4,8,16,2$ must necessarily be of a different color from the other 3. As 4 divides $8,16,4$ must necessarily be of a different color from the other 2. Similarly, as 8 divides 16, $2,4,8,16$ must necessarily have different colors from each other. Therefore, at least 4 different colors are needed.

Conversely, we are looking for a coloring of the integers from 2 to 32 using exactly 4 colors. We can in fact continue the previous coloring by coloring each integer as we go with the smallest possible color. We get the following coloring:

1. The numbers colored with color 1 are $2,3,5,7,11,13,17,19,23,29,31$
2. The numbers colored with color 2 are $4,6,9,10,14,15,21,22,25,26$
3. The numbers colored with color 3 are $8,12,18,20,27,28,30$
4. The numbers colored with color 4 are 16,24

We do indeed have a correct coloring with 4 colors, so the minimum number of colors is 4.

Alternative solution: As in the previous case, we show that for the first question, at least 3 colors are needed and at least 4 in the second.

Here we propose to generalize the previous coloring: we construct a coloring with the optimal number of colors to color the integers from 2 to $r$, with $r \geqslant 2$. Let $n \geqslant 2$, and let $n=p_{1}^{a_{1}} \times \cdots \times p_{k}^{a_{k}}$ be its prime factorization. We will color $n$ with the color $a_{1}+\cdots+a_{k}$ (note that since $n \geqslant 2$, we indeed have $a_{1}+\cdots+a_{k} \geqslant 1$). Let's show that this coloring is correct: let $m \neq n$ be two integers such that $m$ divides $n$. Let $n=p_{1}^{a_{1}} \times \cdots \times p_{k}^{a_{k}}$ be its prime factorization. $m$ necessarily writes as $m=p_{1}^{b_{1}} \times \cdots \times p_{k}^{b_{k}}$ with $b_{1} \leqslant a_{1}, \ldots b_{k} \leqslant a_{k}$. Since $m \neq n$, there must necessarily be an $i$ such that $a_{i} \neq b_{i}$, so $a_{i}>b_{i}$. Thus we must have $a_{1}+\cdots+a_{k}>b_{1}+\cdots+b_{k}$, so $m$ and $n$ are indeed of different colors.

If $n \leqslant 8$ and $n=p_{1}^{a_{1}} \times \cdots \times p_{k}^{a_{k}}$ then $2^{3}=8 \geqslant n \geqslant 2^{a_{1}+\cdots+a_{k}}$ so $a_{1}+\cdots+a_{k} \leqslant 3$, the coloring uses at most 3 colors for the integers from 2 to 8, so for the first question, the minimal $k$ is 3.

If $n \leqslant 31$ and $n=p_{1}^{a_{1}} \times \cdots \times p_{k}^{a_{k}}$ then $2^{5}=32>n \geqslant 2^{a_{1}+\cdots+a_{k}}$ so $a_{1}+\cdots+a_{k}n$. Let $j$ be an integer such that $2 \leqslant j \leqslant n$. Let $l$ be the largest integer such that $2^{l} \leqslant j$ and similarly $2^{l+1}>j$. Since $2 \leqslant j \leqslant n<2^{k+1}$, we have $1 \leqslant l<k+1$, so $1 \leqslant l \leqslant k$. We will color $j$ with the color $l$.

Note that since $1 \leqslant l \leqslant k$, this coloring uses at most $k$ colors. Since $2 \leqslant 2 \leqslant 4 \leqslant \cdots \leqslant 2^{k} \leqslant n$, the $2^{j}$ for $1 \leqslant j \leqslant k$ are between 2 and $n$, and since $2^{j}$ is colored with the color $j$, the coloring uses exactly $j$ colors.

This coloring also satisfies the property of the statement: let $m, n$ such that $m$ divides $n$ and $m \neq n$. Let $j$ be the color of $m$, we have $m \geqslant 2^{j}$. Since $m$ divides $n$ and $m \neq n, n \geqslant 2 m \geqslant 2^{j+1}$, so $n$ cannot be colored with the color $j$, otherwise we would have $n<2^{j+1}$.

In particular for $n=8$, since $2^{3}=8<2^{4}$, the proposed coloring uses 3 colors and for $n=31$, since $2^{4} \leqslant n<2^{5}$, the coloring uses 4 colors. Thus for the first question, the minimal $k$ is 3, for the second it is 4.

Comment: In this exercise, each question contained two parts. For example, for question 2), it was necessary to show on the one hand that we can color the integers with 4 colors, on the other hand, it is necessary to show that, whatever the coloring, it always uses at least 4 colors. It is only by treating each point separately that one could get the maximum score. Moreover, a large part of the students made good progress on the problem and provided a valid coloring with the right number of colors.