4
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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 $$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – apple Oct 26 '18 at 15:22
  • $\begingroup$ @apple Oh mate, sorry!!! I'll try to correct it. $\endgroup$ – Bruno Reis Oct 26 '18 at 15:28
  • $\begingroup$ @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! $\endgroup$ – Bruno Reis Oct 26 '18 at 15:42
  • $\begingroup$ @apple It's done! See if you can get it. $\endgroup$ – Bruno Reis Oct 26 '18 at 18:21
  • 2
    $\begingroup$ @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. $\endgroup$ – Ingix Oct 26 '18 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.