0
$\begingroup$

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?

$\endgroup$
19
  • 4
    $\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
    Commented Jan 15, 2020 at 0:42
  • 2
    $\begingroup$ Pigeonhole principle ? $\endgroup$
    – J. W. Tanner
    Commented Jan 15, 2020 at 0:45
  • 1
    $\begingroup$ @J.W.Tanner sorry yes i mean pigeonhole principle $\endgroup$
    – vedss
    Commented Jan 15, 2020 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
    Commented Jan 15, 2020 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
    Commented Jan 15, 2020 at 1:48

1 Answer 1

Reset to default
1
$\begingroup$

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?

$\endgroup$
7
  • $\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
    Commented Jan 16, 2020 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
    Commented Jan 16, 2020 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
    Commented Jan 17, 2020 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
    Commented Jan 17, 2020 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
    Commented Jan 17, 2020 at 5:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .