There are 85 subsets with 5 numbers beetween {1,2,..,11}. proof there are 2 subsets (A and B) that min(A)=min(B) , med(A)=med(B), max(A)=max(B).

Question

med (A) = 3rd num in the subset.

example : for A = {2,3,5,8,11} min (A) = 2 , med (A) = 5 , max (A) = 11.

I tried to solve it with Pigeonhole principle , but I can't find how to get 84 holes to 85 pigeons (= subsets).

Answer 1

If we take from each subset min, med and max element, they will form a triplet $(a,b,c)$ with the property that $b>a+1$, $c>b+1$. So we essentially are asking the question how many of these triplets exist.

In other words, we want to find how many ways are there to place 3 balls into 11 linearly placed boxes, so no 2 balls are neighbours.

We first place 8 empty boxes leaving gaps between them. There are 9 gaps if we count the space to the left or to the right as gap. There are $\binom93=84$ ways to place 3 boxes with balls in them. Thus, there are only 84 possible triplets of $(\min,\mathrm{med}, \max)$ that your subsets can have. Apply pigeonhole principle now.