Let $n$ be a positive integer. Initially a few positive integers are written on the blackboard. On one move Igor chooses two numbers $a, b$ of the same parity on the blackboard and writes $\frac{a+b} {2}$. After a few moves the numbers on the blackboard were exactly $1, 2, \ldots, n$. Find the smallest possible number of positive integers that were initially written on the blackboard.
Problem
Source: Serbia Additional IMO TST 2024, P2 (out of 4)
Tags: combinatorics
30.05.2024 14:41
redacted
30.05.2024 14:59
The answer is $1$ if $n$ is one, $2$ if $n$ is one more then a power of two, and $3$ otherwise: Construction: If $n=2^k-1$. Then write the numbers $1$ and $2^k+1$. Notice we can generate $2^{k-1}+1$ and can construct $[2^{k-1}+1]$ by induction. By symmetry we can also construct the other half of the numbers. Otherwise, let $k$ be the largest integer such that $2^k+1<n$. Then write $1$, $2^k+1$, and $n$ on the blackboard. Notice we can construct $[2^k+1]$ and then by averaging with $n$ we can construct $2^k+2,2^k+3,\dots$ in that order. Here is an example for $n=16$: $$1,9,16$$$$1,5,9,16$$$$1,3,5,7,9,16$$$$1,2,3,4,5,6,7,8,9,16$$$$1,2,3,4,5,6,7,8,9,10,11,12,16$$$$1,2,3,4,5,6,7,8,9,10,11,12,13,14,16$$$$1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16$$ Bound: Ignore the case $n=1$. Notice that we must include $1$ and $n$ on the board. But if $n$ is not one more than a power of two we can not divide the interval $[1,n]$ sufficiently.
30.05.2024 15:52
Answer: If $n\geq 3$ is in form $2^k+1,$ then $2$ numbers are enough and if it's not in form $2^k+1$, then $3$ numbers are enough. $1$ for $n=1$ and $2$ for $n=2$. Upper Bound: If we write $1,2^1+1$ on the board, we can write $1,2,3$. Assume that all numbers can be written between $1,2^k+1$ for $k=1,2,...,m$. Let's prove that we can do it for $m+1$. We write $\frac{1+2^{m+1}+1}{2}=2^m+1$ and by induction we can write all numbers between $1$ and $2^m+1$. By writing $\frac{(2^{m+1}+1)+(2i-1)}{2}=2^m+i$ for $i=2,3,...,2^m$ respectively, we get all numbers. For $2^{m+1}+1>n>2^m+1,$ we write $1,2^m+1,2^m+t=n$. By the previous step, we can write $1,2,...,2^m,2^m+1$. Then we write $\frac{(2^m+t)+(2^m-t+2i)}{2}=2^m+i$ for $i=2,3,...,t$ respectively, and we get all numbers. Lower Bound: We need at least $2$ numbers since we cannot get more than a number with exactly one number. Hence we need $2$ numbers for $2^k+1$. For $2^{k+1}+1>2^k+t>2^k+1$, let $a,b$ be the written numbers at initial position. Since $\frac{a+b}{2}<n$, $2^k+t\in \{a,b\}$. WLOG $b=2^k+t$. Also $\frac{a+b}{2}>1$ thus $a=1$. Let $n=2^lm+1$ where $m$ is odd. We claim that all numbers which can be written are $\equiv 1(mod \ m)$. It's true for $1,2^lm+1$. And $\frac{mx+1+my+1}{2}=m(\frac{x+y}{2})+1\equiv 1(mod \ m)$ which gives the desired claim.$\blacksquare$