# 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

## 1 Answer

One can try the following: start picking t=1 and set sum to 1 and k to 2 and pick the smallest positive unpicked number t such that sum+t is a multiple of k, set sum=sum+t and k=k+1, and repeat until bored or until t exceeds M.

When I try this for small values of M, I do not see t chosen larger than 2k. Further, this process continues until k gets to about M(1 - 1/e). This is a limited sample size, but enough to make a plausible conjecture. In general, I suspect that one can take k up close to M, but not quite because there are few multiples of M-1 and M-2 between the associated triangular numbers. I am confident that k can always progress past M/2 .

The comment I made earlier should show that k can reach floor of square root of M, but sometimes cannot go much further.

Gerhard "Proof Still Work In Progress" Paseman, 2018.10.26.

• The associated sequence 1,4,6,12,20,24,... Is found at oeis.org, with a link to a web site posting problems of the week. Stan Wagon may know more. Gerhard "References Still Work In Progress" Paseman, 2018.10.26. – Gerhard Paseman Oct 26 '18 at 20:16