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

Question

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)

Answer 1

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.