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. Please comment below if the questions are unclear)

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Oct 26 '18 at 0:38
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Oct 26 '18 at 20:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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