Pigeonhole principle - Show that it is possible to pick 4 subsets of cardinality 2 with the same absolute difference

55 Views Asked by At

Let $A = \left \{ 1,3,5,\ldots,153,155 \right \}$, and fix a subset $S\subseteq A$ such that $\left | S \right | = 22$.

Show that it is possible to pick $4$ subsets of cardinality of $2$ from $S$ such that the absolute difference between the $2$ numbers in each subset is the same for all $4$ subsets.

I calculated $\frac{155-1-2}{2} +1 = 77$ different differences, and the are $\binom{22}{2} = 231$ ways of picking a size 2 subset from S.

All in all I get that $\left \lceil \frac{231}{77} \right \rceil = 3$

What am I missing?

1

There are 1 best solutions below

2
On BEST ANSWER

We have $\frac{231}{77} = 3$, meaning if every single one of the different differences between pairs in $S$ appear exactly three times, then you're good. If any difference appears with fewer than $3$ pairs, then there must be some difference that appears at least $4$ times as well.

Now consider the largest element and the smallest element of $S$, and their difference.