Given positive integers $a,b,$ find the least positive integer $m$ such that among any $m$ distinct integers in the interval $[-a,b]$ there are three pair-wise distinct numbers that their sum is zero. Proposed by Marian Tetiva, Romania
Problem
Source: 1st TASIMO Day2, Problem4
Tags: combinatorics
19.05.2024 13:10
Leaving the above, as it seems like a natural fakesolve approach which many people might do. Big thanks to @Marinchoo for pointing out with a counterexample that the answer is not the most expected one. Here is a hopefully corrected version. (I guess the case-bash could be structurally simplified, though I prefer not to bother, and would be surprised if some substantially different idea works in this problem.)
Without loss of generality treat $a \geq b$ and let $t$ be the smallest non-negative element of the set. We try to upper bound the cardinality of the set assuming it does not contain three distinct elements summing to $0$.
Now introduce $m \leq a$ as the largest element of the set. Eliminating $[0,t-1]$ and $[m+1, a]$ leaves us with at most $a+b+1 - t - (a-m) = b + 1 + m - t$ numbers.
Therefore, the answer is $\max(a,b) + 2$ if $a\neq b$ or $a=b$ is odd, and $a+3$ if $a=b$ is even.
21.05.2024 07:15
05.06.2024 15:03
Answer: \[ m= \left\{ \begin{array}{lr} 2k+3 & a=b=2k,k\in \mathbb{N} \\ \max(a,b)+2 & \text{otherwise} \end{array} \right. \] Construction: For the second case $\max(a,b)+1$ is insufficient considering one of $[-a,0]$ or $[0,b]$. For the first case $2k+2$ is insufficient considering the set $[-2k,-k]\cup [k,2k]$. Bound: If $0$ is included in the $m$ elements the result is obvious so assume otherwise. Induct on the larger element until it is one more then the smaller one (if they are not already equal). If both endpoints are not included in the $m$ elements we can repeat this process. Case 1: $(a,b)=(2k,2k+1)$ Assume that $-2k$ and $2k+1$ were chosen amongst the $n$ elements. Then their are $2k-1$ pairs that sum to $2k$ or $-2k-1$. Thus $m=2k+3$ will ensure three elements that sum to $0$. Case 2: $(a,b)=(2k-1,2k)$ Assume that $-2k+1$ and $2k$ were chosen amongst the $n$ elements. Then their are $2k-2$ pairs that sum to $2k-1$ or $-2k$. Thus $m=2k+2$ will ensure three elements that sum to $0$. Case 3: $(a,b)=(2k+1,2k+1)$ Assume that $-2k-1$ and $2k+1$ were chosen amongst the $n$ elements. Then their are $2k$ pairs that sum to $2k+1$ or $-2k-1$. Thus $m=2k+3$ will ensure three elements that sum to $0$. Case 4: $(a,b)=(2k,2k)$ Assume that $-2k$ and $2k$ were chosen amongst the $n$ elements. Then their are $2k-2$ pairs that sum to $2k$ or $-2k$. Thus $m=2k+3$ will ensure three elements that sum to $0$.