Tamarkin D:

In the class, there are 16 students. Every month, the teacher divides the class into two groups.

What is the minimum number of months that must pass so that every two students end up in different groups at some point?
Example. The figure shows how to divide a class into two groups so that any two students are in different groups in at least one of the four months. Each student corresponds to a column in the table, and each month corresponds to a row. A zero in a cell of the table means that the student is in the first group, and a one means that the student is in the second group. Since there are no identical columns, any two students are in different groups at least one month out of the four.

|  | $\mathbf{1}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{4}$ | $\mathbf{5}$ | $\mathbf{6}$ | $\mathbf{7}$ | $\mathbf{8}$ | $\mathbf{9}$ | $\mathbf{1 0}$ | $\mathbf{1 1}$ | $\mathbf{1 2}$ | $\mathbf{1 3}$ | $\mathbf{1 4}$ | $\mathbf{1 5}$ | $\mathbf{1 6}$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $\mathbf{1}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| $\mathbf{2}$ | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| $\mathbf{3}$ | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| $\mathbf{4}$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |

Evaluation. We will prove that it is impossible to meet the condition in three months. We will construct a similar $3 \times 16$ table. In a column, zeros and ones can be arranged in only 8 ways, so there will be two identical columns. The students corresponding to these columns will be in the same group for all three months.

## Answer

4 months.