# What is the maximum value of $n$ with average value 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)

EDIT: I've edited the post because at first I did average as $$\frac{1}{2}\sum a_i$$ instead of $$\frac{1}{i}\sum a_i$$. Below is the corrected answer:

Modeling the problem for maximum or minimum we get:

\begin{align*} \text{max/min }&\sum_{i=1}^{m}b_i\\ \text{such that }& b_11+b_22+\cdots+b_MM=Mk\\ &b_i\in\{0,1\},k\in\mathbb{N} \end{align*}

Suppose $$M=1$$. We can erase the only value: $$1$$, and it's average is $$\frac{1}{1}=1$$ an integer. Therefore max=min=$$1$$.

Suppose $$M=2$$. We can only erase $$2$$, because $$\frac{3}{2}\notin \mathbb{Z}$$. Therefore max=min=$$1$$.

Now let's suppose $$M\geq 3$$. Let's see for what $$M$$'s we can erase all numbers, that is $$n=M$$: $$1+2+\cdots+M = \frac{M(M+1)}{2} = Mk \rightarrow M=2k-1$$ Hence for $$M\in\{3,5,7,9,\cdots\}$$ we can erase all numbers to get it's average as an integer.

We've covered the cases for $$M$$ when it's odd and $$M\geq 3$$. Let's see what happens for the cases where $$M$$ is even, that is, $$M=2q$$. $$1+2+\cdots+2q = \frac{2q(2q+1)}{2} = q(2q+1) = 2q^2+q$$ We want that result to be equal to $$Mk=2qk$$ for some $$k \in \mathbb{N}$$. Therefore if we let $$b_q=0$$ we get the sum as: $$1+2+\cdots + 2q - q = 2q^2+q - q = 2q^2$$ And that is equal to $$2qk$$ for $$k=q$$. Therefore for $$M=2q$$ we get $$n=M-1$$.

That means that when $$M=2q$$ we only need $$b_q=0$$ to guarantee that the average of the sum of the erased numbers is an integer.

Finally see that for $$M\geq 1$$ you can always use the same reasoning for $$M=1$$ for the minimum... You remove $$1$$ and the average of the removed numbers is going to be $$\frac{1}{1}=1$$ that is an integer.

Since we've covered all cases for $$M$$, we're done.

Examples: For $$M=12345$$: $$1 + 2 + \cdots + 12345 = 76205685 \text{ and } \frac{76205685}{12345}=6173$$ For $$M=124=2\cdot 62$$: $$1 + 2 + \cdots + 124 - 62 = 7750 - 62 = 7688 \text{ and } \frac{7688}{124}=62$$

• Thanks for your answer. However, my question is that the average value, means the total sum of numbers divided by the amount of numbers, ($\frac{a_1+a_2+...+a_i}{i}$ is always an integer, not half of the sum. – apple Oct 26 '18 at 15:22
• @apple Oh mate, sorry!!! I'll try to correct it. – Bruno Reis Oct 26 '18 at 15:28
• @apple I've got the result. I just don't have time to post it now. I'll try to post it within 3 hours! – Bruno Reis Oct 26 '18 at 15:42
• @apple It's done! See if you can get it. – Bruno Reis Oct 26 '18 at 18:21
• @Brunu: I don't think you understood the problem correctly. For odd $M$ you only prove that you can get the last sum correctly, that is (comperatively) easy. The problem is to select one number $a_i$ after the other, and after each step have an averge that is an integer. So for $M=5$, the first chosen number must be divisible by $1$ (easy), the sum of the first and second must be divisible by $2$, the sum of the first $3$ must be divisible by $3$, a.s.o, as far as you can get. Reread the description again and I think you will see what you misunderstood. For $M=5$, the max $n$ is e.g. 3. – Ingix Oct 26 '18 at 21:33