Serbian Mathematical Olympiad

Ответ. $\lfloor n/2 \rfloor$.

Решение. Upper bound. Assume one of the written numbers is greater than $\lfloor n/2 \rfloor$, say, $\text{GCD}(a, b) = d > \lfloor n/2 \rfloor$. Then the larger of the numbers $a, b$ must be at least $2d$, which exceeds $n$ - a contradiction. Therefore, each written GCD cannot exceed $\lfloor n/2 \rfloor$, and thus the number of distinct GCDs cannot be greater than $\lfloor n/2 \rfloor$.

Example. Let's partition all numbers from $1$ to $n$ into chains of the form $a, 2a, 4a, 8a, \dots, 2^k a$, where $a$ is an odd number not exceeding $n$. Write these chains consecutively in a row. Then for any natural number $d \le \lfloor n/2 \rfloor$, there exists a chain containing $d$ where the number following $d$ is $2d$. We see that every natural number $d \le \lfloor n/2 \rfloor$ will appear on the sheet.