Pigeonhole principle, choosing 1-8 numbers out of 27

155 Views Asked by At

prove that for every 8 choosen numbers from 10 to 36 you can always make equalities. number can be used once.

examples.

let say that the choosen numbers are

10, 11, 12, 15, 18, 25, 32, 36

you can write

11+25=36 or 10+12+18=15+25.

i tried to prove for summation for every 2 numbers $$\binom{8}{2}=28 $$

but there are 51 different summation of 2 differend numbers Lets say that the nombers are a b c d e f g h 2 out of 8 is valid because the subsets (ab) and (ac) cannot be equal so they cannot be compared But 3 of 8 can be (abc) and (ade) and they can be equal so it is not valid So i can use only use 2 out of 8 Baybe i am in the wrong direction.

that's the closest i got

1

There are 1 best solutions below

5
On

Let $S\subset\{10,11,12,\ldots,36\}$ be an arbitray subset of eight integers. The set $S$ itself has $2^8=256$ subsets. Of these $255$ are non-empty. For any subset $U\subset S$, $U\neq\emptyset$, let's denote by $\Sigma(U)$ the sum of elements of $U$. The smallest possible value of $\Sigma(U)$ is clearly $$ \Sigma(\{10\})=10, $$ and the largest possible value of $\Sigma(U)$ is $$ \Sigma(\{36,35,34,\ldots,29\})=4\cdot65=260. $$ These cannot occur for subsets of the same set $S$, but we don't need to worry about that. No matter what the set $S$ is, the $255$ numbers $\Sigma(U),U\subseteq S, U\neq\emptyset$, are all integers in the range $[10,260]$. That range has $251$ integers, so by the pigeonhole principle there exists two distinct subsets $U_1,U_2\subseteq S$ with the property that $$ \Sigma(U_1)=\Sigma(U_2). $$ Getting warmer, but let's not forget that a single element of $S$ can only be used once. In other words, the two sets $U_1,U_2$ should be disjoint. But this does not really form an obstacle for us. For if $V=U_1\cap U_2$ is non-empty, then, denoting $U_1'=U_1\setminus V$ and $U_2'=U_2\setminus V$, we see that $$\Sigma(U_i)=\Sigma(U_i')+\Sigma(V)$$ for $i=1,2$. Therefore $$ \Sigma(U_1')=\Sigma(U_1)-\Sigma(V)=\Sigma(U_2)-\Sigma(V)=\Sigma(U_2'). $$ Thus the disjoint subsets $U_1'$ and $U_2'$ have equal set sums. Because obviously neither of $U_1,U_2$ can be a subset of the other, both $U_1'$ and $U_2'$ are non-empty.