# Is it possible to find the minimum or maximum value of $n$ average values must be an integer

Let $$M$$ be a positive integer greater than $$1$$. All integers from $$1$$ to $$M$$ were written on a board.

Each time we erase a positive integer on the board in a way that the average value of all numbers that have been erased must always be an integer.

Assume that there are $$n$$ numbers that have been erased ($$1 \leq n \leq M$$, $$n$$ is not a constant number). The process will end with $$n$$ numbers if and only if it is impossible to erase the $$(n+1)th$$ number so that the average value of $$n+1$$ erased numbers can be an integer.

For all possible ways to erase the numbers, what is the maximum and the minimum value that $$n$$ can reach?

For example, with $$M=3$$, we have the maximum of $$n$$ is $$3$$ (choose $$a_1=1$$, $$a_2=3$$, $$a_3=2$$ ) , the minimum value of $$n$$ is $$1$$ (choose $$a_1=2$$, then it is impossible to choose $$a_2=1$$ or $$a_2=3$$ because $$\frac{2+1}{2}, \frac{2+3}{2}$$ are not integers). For larger $$n$$, I thought that I can solve with Chinese Remainder Theorem, but I didn't know how to use it.

Is it possible to find the minimum or maximum value of $$n$$?. If not, what are the conditions of $$M$$ so that the minimum or maximum value of $$n$$ can be found?

(Sorry, English is my second language, so the questions may unclear for some readers. Please comment below if the questions are unclear)

• It is possible to choose poorly and not reach p for a prime p slightly larger than squareroot of M. Let such a prime p have at most p-1 multiples in 1..M. If you have maintained the integer mean up to n=p-1, then you have run out of multiples to get to p. Otherwise start with non multiples adding up to a multiple of p. I suspect few non multiples of p are needed to maintain the integer average. Also, for n smaller than square root M, there is always enough of the right residue class to use, so the smallest n is O(M^1/2). Gerhard "Now Thinking On Biggest N" Paseman, 2018.10.25. – Gerhard Paseman Oct 26 '18 at 0:38