Pigeon Hole Principle question

Question

So for the first step we define the properties that are exhibitted by the 4 cards :

The average powere level of all 4 cards be p: x,y,z,w so (x+y+z+w)/4 = p

and the cards can be split into two pairs each of which also has an average of power level of p:

(x+y)/2 = p , (z+w)/2 = p

Can you hint me where I should go from here?

Answer 1

HINT: Suppose that $\{x,y,z,w\}$ is such a set of four cards, and $x<y<z<w$; then it must be the case that $x+w=y+z=2p$. (Why?) This means that there are positive $a$ and $b$ such that $x=p-a$, $w=p+a$, $y=p-b$, and $z=p+b$. (Why?) And that means that $y-x=a-b=w-z$. (It also means that $z-x=w-y$.)

• Show that if $x<y<z<w$, and $y-x=w-z$, then $\{x,y,z,w\}$ has the desired property.

Suppose that Victor’s $21$ cards are $c_1,c_2,\ldots,c_{21}$, where $c_1<c_2<\ldots<c_{21}$. For $k=1,\ldots,20$ let $d_k=c_{k+1}-c_k$.

• Show that if the $d_k$ are all different, then $d_1+\ldots+d_{20}\ge 210$. What does this tell you about $c_{21}-c_1$? Conclude that two of the differences $d_k$ must be equal.

Answer 2

Feel free to stop reading at any moment if you want to try it by yourself.

Suppose you have taken the cards $x,y,z,w$ with $\frac{x+y+z+w}{4}=p$ and suppose they satisfy your property. Then there are two of these cards such that their average is also $p$. Suppose those two cards are $x$ and $y$. Then $\frac{x+y+z+w}{4}=\frac{x+y}{2}\Leftrightarrow\frac{2x+2y-x-y-z-w}{4}=0\Leftrightarrow x+y-z-w=0\Leftrightarrow x+y=z+w$. Therefore your property is equivalent to the following one: from the four cards $x,y,z,w$ there are at least two of them whose sum is equal to the sum of the other two (obviously if there are two cards satisfying this property, the other two satisfy it too).

Then you can ask yourself how many sums you can make with two cards. Well, the least one has to be $101+102=103$ and the greatest one $199+200=399$, and it is easy to see that you can get any number in between, so there are $197$ possible sums. But, in how many ways can you take $2$ cards from the $21$ you have?

The answer is ${21\choose 2}=210$. Then by the Pigeonhole Principle there is at least two pairs of cards that have the same sum (why?). Let these two pairs be $\{x,y\}$ and $\{z,w\}$ (I use set notation because order isn't important).

It could seem like we are done, since our four cards would be $x,y,z,w$, but let's stop for a minute: what happens if $x=z$? Then we actually wouldn't have four cards, so that wouldn't be a valid answer. The same goes for $x=w$, $y=z$ or $y=w$. Clearly we can't have $x=y$ or $z=w$, since we have chosen pairs of distinct elements.

WLOG assume $x=z$. We have shown that $\{x,y\}$ and $\{z,w\}$ are two different pairs of cards with the same sum, so $x+y=z+w$. But, if $x=z$, then we have $y=w$ and consequently $\{x,y\}=\{z,w\}$. This can't happen, since they were different pairs of cards. Therefore $x\neq z$ (we could show similarly $x\neq w$, $y\neq z$ and $y\neq w$).

So they really were four different cards satisfying that the sum of two of them is equal to the sum of the other two. We are done.