Let $n$ be positive integer, set $M = \{ 1, 2, \ldots, 2n \}$. Find the minimum positive integer $k$ such that for any subset $A$ (with $k$ elements) of set $M$, there exist four pairwise distinct elements in $A$ whose sum is $4n + 1$.
Problem
Source: CSEMO 2005-3
Tags: induction, pigeonhole principle, combinatorics unsolved, combinatorics
18.07.2005 05:03
There exist the generlized problem in the imo shotlists (1995-2001, it is in a book so i dont know which year ) . and it is this : Let $n,m,k$ be natural numbers such that $ \ 1< n \le m-1 \le k$) .find the maximum of the numbers of the subset $S$ form the set $\{1,2,3,...,k\}$ which sum of the each $n$ elements of $S$ dont be equal to $m$. And i am going to check for the answer of it
18.07.2005 05:10
Well we can easily show that the answer is $\le k - \alpha$ where $\alpha $ is the biggest natural number such that is $\le \frac{m}{n}-\frac{n-1}{2}$ and by my supprise the answer is exactly $k - \alpha$ and the proof is by the induction on the $n$ . and the proof is highly complicated for me at least
18.07.2005 13:02
$k=n+3$ will do. to start with note that the set $\{n-1,n,n+1,n+2,\ldots,2n\}$ is a set of $n+2$ elements and has a minimum sum (with $4$ distinct elements) of $n-1+n+n+1+n+2=4n+2$, so $k\geq n+3$.also for a set of size atleast $n+2$ we can form pairs of distinct elements that sum to $2n$ and pigeonhole $\Rightarrow$ there exists a pair of distinct elements with sum $2n$.once we remove such a pair from the $n+3$-set and we are still left with an $n+1$ set from which another pair,this time with sum $2n+1$ (again pigeonhole) can be extracted and so we are through.
22.07.2005 00:03
a minor adjustment (your proof is correct): After you have chosen a pair that adds up to 2n. Now you need to subtract 4, not 2, elements from the k. (because say a+b=2n, not only will we not be able to use a and b in forming a pair with sum 2n+1, we can't use 2n+1-a and 2n+1-b either.) But now we have effectively narrowed now the number of valid pairs that add up to 2n to just n-2, which means another pigeonhole indeed gets us home. (So you see, it's not because we have 2n+1 elements and n possible pairs, but cuz we have 2n-1 elements and n-1 possible pairs.)
22.07.2005 00:50
well any subset of $\{1,2,\ldots,2n\}$ of size $n+1$ contains a pair of distinct elements which sum up to $2n+1$.this is independent of what i do before getting to that $n+1$-set. the more important thing is to get the sum to $2n$ first because choosing $n+1$ elements from $\{1,2,\ldots,2n\}$ will not guarantee $\textbf{two}$ distinct elements to add up to $2n$, for eg:$\{1,2,\ldots,n-1,n,2n\}$.