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

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?

• Hint: there are $\binom {11}2=55$ possible pairs of integers taken from $\{1, \cdots, 11\}$. There are $\binom 42=6$ pairs in each of the $S_i$ hence there are $60$ pairs between all the ten $S_i$. – lulu Jan 15 at 0:42
• Pigeonhole principle ? – J. W. Tanner Jan 15 at 0:45
• @J.W.Tanner sorry yes i mean pigeonhole principle – vedss Jan 15 at 0:50
• @AdamRubinson The way I understand the question: "From the $11$ integers $\{1, \cdots, 11\}$ we create $10$ sets $S_i$. Each of them contains exactly $4$ of the $11$ integers. Prove that there are at least two of those sets, $S_i, S_j$ with $i\neq j$ such that $|S_i\cap S_j|≥2$." In the example given in the post, $S_1,S_2$ fit the bill. – lulu Jan 15 at 1:00
• Honestly, my initial hint is $95\%$ of a complete solution...I don't see what else I can say other than writing out the answer. Well, do the warm up exercise I proposed. It's considerably easier than the given problem, and the logic behind that is identical. – lulu Jan 15 at 1:48

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?

• Thankyou, for the proof some integer must appear in 4 more sets, there are 11 integer, but each sets size 4, so by pigeon hole principle, we need at least 3 sets in order two sets out of three have at least 1 same number on it. since there are 10 sets, $\lceil \frac{10}{3} \rceil =4$ ? but I'm not sure what is the pigeon and pigeonhole in this? and i think there are some integer that only appear in 3 sets too, if i put 1..11 to each sets from S1 to 10 then 8,9,10,11 only appear 3 times in S1..S10 sets(?) – vedss Jan 16 at 14:12
• For the Lemma, count the appearances. There are $10$ sets, each of size $4$, so the integers must collectively appear $40$ times. There are $11$ integers. If each one appeared $3$ times or fewer, that cannot fill the $40$ appearances. – antkam Jan 16 at 14:39
• Thankyou for the hint. But i think it should be that some integer must appear in 3 or 4 more sets ? if all integer appear in 4 sets , it must be 44 appearance and need 11 sets? and for the pair, if one integer appear in 4 sets, there are 3 spot left in every sets, and 10 distinct integer left , by pigeon hole principle, we can put 3 different integer in 3 sets, but in fourth sets there must be integer that we already put in the S1,S2, or S3 , so either $S1 \cap S4$ or $S2 \cap S4$ or $S3 \cap S4$ , it this enough to proof? – vedss Jan 17 at 2:54
• for the lemma, you don't care about integers which appear in $3$ sets. all you need is that some integer appears in at least $4$ sets. and for the second part, yes you are right. – antkam Jan 17 at 4:24
• Thankyou but why it has to be 4? and i dont understand the relation between 11 integer, 10 sets and each size 4, for example there are only 6 sets each 4 integer and 11 integer to put, with only 6 sets, we also can get two sets that share two or more integer? – vedss Jan 17 at 5:09