Find all positive integer $n$ , such that for all 35-element-subsets of $M=(1,2,3,...,50)$ ,there exists at least two different elements $a,b$ , satisfing : $a-b=n$ or $a+b=n$.
Problem
Source: China South East Mathematical Olympiad 2011
Tags: combinatorics proposed, combinatorics
01.11.2012 20:50
I got n less then 71 can work.
02.11.2012 19:52
Let $A$ be any 35-element subset of $M$. By contradiction that there exists $A$ such that : no $a,b \in A$ exist such that the condition is fulfilled, we will get an upper bound for $n$. We can see that if $a \in A$ then: $n-a \notin A$ and $a-n \notin A$. Let $m$ be the amount of numbers $c$ that satisfy $c \in M $ and $ c \notin A$. We can easily see that if $m > 15$ then $A$ cannot exist (because $A$ needs to have $35$ elements, but only $(50-m)<35$ elements can be in $A$). Let $m$ initially be $0$. Now if we take $a \in A$ such that $a>n$ then, because $a-n \notin A$ and $a-n \in M$ we get that $m$ becomes $m+1$. On the other hand if $a<n$ then $n-a \notin A$, and $n-a \in M$ if and only if $n-a \leq 50$, so $m$ becomes $m+1$ if and only if $n-a \leq 50$. Now we want to minimize $m$ as much as we can, we see that for any $a \in A$, $m$ will grow if $n-a \leq 50$, so we want to get that at least $20$ numbers in $A$ satisfy $n-a>50$ or $n>50+a$. Minimizing $n$ we get $n>70$. By our contradiction we get that $n \leq 70$. So any $n \in [1,70]$ will work.
29.07.2017 16:58
I think n = 70 can't work because {1,2,3,...,35} don't have a+b=70 or a-b=70