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?

  • 3
    $\begingroup$ 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$. $\endgroup$ – lulu Jan 15 at 0:42
  • 2
    $\begingroup$ Pigeonhole principle ? $\endgroup$ – J. W. Tanner Jan 15 at 0:45
  • 1
    $\begingroup$ @J.W.Tanner sorry yes i mean pigeonhole principle $\endgroup$ – vedss Jan 15 at 0:50
  • 1
    $\begingroup$ @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. $\endgroup$ – lulu Jan 15 at 1:00
  • 1
    $\begingroup$ 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. $\endgroup$ – 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?

| cite | improve this answer | |
  • $\begingroup$ 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(?) $\endgroup$ – vedss Jan 16 at 14:12
  • $\begingroup$ 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. $\endgroup$ – antkam Jan 16 at 14:39
  • $\begingroup$ 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? $\endgroup$ – vedss Jan 17 at 2:54
  • $\begingroup$ 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. $\endgroup$ – antkam Jan 17 at 4:24
  • $\begingroup$ 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? $\endgroup$ – vedss Jan 17 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.