Application of pigeonhole principle: proving that two subsets include two or more common integers

230 Views Asked by At

If the proposition below is true, show this. If false, give a counterexample.
From the integers from $1$ to $11$, make 10 sets $S_1,S_2, \dots, S_{10}$ each with 4 integers selected. Within each sets, the same number shall not be chosen twice. No matter how $S_1,S_2, \dots, S_{10}$ is selected, two sets $S_i,S_j$($i$ not equal to $j$) include two or more common integers.

Is this related to pigeon principle? $$S_1=\{1,2,3,4\},$$ $$S_2=\{2,3,4,5\},$$ $$S_3=\{4,5,6,7\},$$ $$S_4=\{5,6,7,8\},$$ $$S_5=\{7,8,9,10\},$$ $$S_6=\{8,9,10,11\},$$ $$S_7=\{5,6,2,4\},$$ $$S_8=\{1,5,7,9\},$$ $$S_9=\{4,8,10,11\},$$ $$S_{10}=\{5,7,10,11\}$$

When we choose two of them, there is possibility there are same integer but not all ? If this is related to pigeonhole principle, Is there possibility that sets are hole and number $1$-$11$ is pigeon but what is the relation with in each sets there are four number?

1

There are 1 best solutions below

7
On

HINT (different from lulu's)

Lemma: some integer must appear in $4$ or more sets.

Proof of Lemma: apply pigeonhole based on there being $11$ integers, $10$ sets, each of size $4$. $\square$

Main Claim: some pair $S_i, S_j$ must share $2$ or more integers.

Proof: By Lemma, there is an integer, call it $s$, which appears in (at least) $4$ sets, e.g.:

$$\{s,a,b,c\}, \{s,d,e,f\},\{s,g,h,i\}, \{s,j,k,l\}$$

Use pigeonhole principle again to show two of these sets must share $2$ or more integers. $\square$

Hope you can finish based on the above?