Proving that there is an element common to all $35$ sets given certain set restrictions
up vote
5
down vote
favorite
Consider the $35$ sets $A_1,A_2,dots,A_{35}$ such that $|A_i|=27$ for all $1leq i leq 35$, and every triplet of sets have one exactly one element in common to all three. Prove that there is at least one element common to all $35$ sets.
This was a problem given to me by a friend - he asked me to help him with this but I am unable to figure out the answer. He suggested something about contradiction and the pigeonhole principle, but I'm not sure how to continue. He mentioned it was from some sort of Olympiad, but I dont remember which one (something middle eastern?)
I found this similar question online: https://artofproblemsolving.com/community/q1h1699161p10908761
but this doesn't include any restrictions on cardinality, and is only a case for a pairwise disjoint set.
combinatorics algebra-precalculus contest-math
asked Nov 19 at 5:46
user574848
14013
add a comment |
up vote
5
down vote
favorite
Consider the $35$ sets $A_1,A_2,dots,A_{35}$ such that $|A_i|=27$ for all $1leq i leq 35$, and every triplet of sets have one exactly one element in common to all three. Prove that there is at least one element common to all $35$ sets.
This was a problem given to me by a friend - he asked me to help him with this but I am unable to figure out the answer. He suggested something about contradiction and the pigeonhole principle, but I'm not sure how to continue. He mentioned it was from some sort of Olympiad, but I dont remember which one (something middle eastern?)
I found this similar question online: https://artofproblemsolving.com/community/q1h1699161p10908761
but this doesn't include any restrictions on cardinality, and is only a case for a pairwise disjoint set.
combinatorics algebra-precalculus contest-math
asked Nov 19 at 5:46
user574848
14013
1
"...such that $| A_i|=27$ for all $1leq ileq 27$..." Is this a typo? Should it be $1leq ileq 35$ instead?
– YiFan
Nov 22 at 23:04
@YiFan Yes, fixed, thank you
– user574848
Nov 22 at 23:14
Consider A$_1$. There are $binom{34}{2}$= 561 triplets of sets that include A$_1$. BY the pigeonhole principle there is at least 1 element of A$_1$ that is shared by 20 of these triples. Maybe you can keep reducing the problem accordingly.
– Joel Pereira
Nov 23 at 0:09
add a comment |
up vote
5
down vote
favorite
up vote
5
down vote
favorite
Consider the $35$ sets $A_1,A_2,dots,A_{35}$ such that $|A_i|=27$ for all $1leq i leq 35$, and every triplet of sets have one exactly one element in common to all three. Prove that there is at least one element common to all $35$ sets.
This was a problem given to me by a friend - he asked me to help him with this but I am unable to figure out the answer. He suggested something about contradiction and the pigeonhole principle, but I'm not sure how to continue. He mentioned it was from some sort of Olympiad, but I dont remember which one (something middle eastern?)
I found this similar question online: https://artofproblemsolving.com/community/q1h1699161p10908761
but this doesn't include any restrictions on cardinality, and is only a case for a pairwise disjoint set.
combinatorics algebra-precalculus contest-math
asked Nov 19 at 5:46
user574848
14013
Consider the $35$ sets $A_1,A_2,dots,A_{35}$ such that $|A_i|=27$ for all $1leq i leq 35$, and every triplet of sets have one exactly one element in common to all three. Prove that there is at least one element common to all $35$ sets.
This was a problem given to me by a friend - he asked me to help him with this but I am unable to figure out the answer. He suggested something about contradiction and the pigeonhole principle, but I'm not sure how to continue. He mentioned it was from some sort of Olympiad, but I dont remember which one (something middle eastern?)
I found this similar question online: https://artofproblemsolving.com/community/q1h1699161p10908761
but this doesn't include any restrictions on cardinality, and is only a case for a pairwise disjoint set.
combinatorics algebra-precalculus contest-math
combinatorics algebra-precalculus contest-math
asked Nov 19 at 5:46
user574848
14013
asked Nov 19 at 5:46
user574848
14013
edited Nov 22 at 23:14
asked Nov 19 at 5:46
user574848
14013
asked Nov 19 at 5:46
user574848
14013
asked Nov 19 at 5:46
user574848
14013
14013
1
"...such that $| A_i|=27$ for all $1leq ileq 27$..." Is this a typo? Should it be $1leq ileq 35$ instead?
– YiFan
Nov 22 at 23:04
@YiFan Yes, fixed, thank you
– user574848
Nov 22 at 23:14
Consider A$_1$. There are $binom{34}{2}$= 561 triplets of sets that include A$_1$. BY the pigeonhole principle there is at least 1 element of A$_1$ that is shared by 20 of these triples. Maybe you can keep reducing the problem accordingly.
– Joel Pereira
Nov 23 at 0:09
add a comment |
1
"...such that $| A_i|=27$ for all $1leq ileq 27$..." Is this a typo? Should it be $1leq ileq 35$ instead?
– YiFan
Nov 22 at 23:04
@YiFan Yes, fixed, thank you
– user574848
Nov 22 at 23:14
Consider A$_1$. There are $binom{34}{2}$= 561 triplets of sets that include A$_1$. BY the pigeonhole principle there is at least 1 element of A$_1$ that is shared by 20 of these triples. Maybe you can keep reducing the problem accordingly.
– Joel Pereira
Nov 23 at 0:09
1
1
"...such that $| A_i|=27$ for all $1leq ileq 27$..." Is this a typo? Should it be $1leq ileq 35$ instead?
– YiFan
Nov 22 at 23:04
"...such that $| A_i|=27$ for all $1leq ileq 27$..." Is this a typo? Should it be $1leq ileq 35$ instead?
– YiFan
Nov 22 at 23:04
@YiFan Yes, fixed, thank you
– user574848
Nov 22 at 23:14
@YiFan Yes, fixed, thank you
– user574848
Nov 22 at 23:14
Consider A$_1$. There are $binom{34}{2}$= 561 triplets of sets that include A$_1$. BY the pigeonhole principle there is at least 1 element of A$_1$ that is shared by 20 of these triples. Maybe you can keep reducing the problem accordingly.
– Joel Pereira
Nov 23 at 0:09
Consider A$_1$. There are $binom{34}{2}$= 561 triplets of sets that include A$_1$. BY the pigeonhole principle there is at least 1 element of A$_1$ that is shared by 20 of these triples. Maybe you can keep reducing the problem accordingly.
– Joel Pereira
Nov 23 at 0:09
add a comment |
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
Lets assume there is no element common to all 35.
Any set $A_i$ is part of $binom{34}{2} = 561$ triplets. $A_i$ has 27 items. $ 27 cdot 20 = 540 < 561 $, so from the pigeonhole principle some item a in $A_i$ must be in 21 of the triplets. This means that at least 7 other sets must include a, since $binom{7}{2} = 21$. In turn, this means that a is in at least 8 sets (including $A_i$). Among these sets, there are $binom{8}{2} = 28$ pairs.
Lets assume some set $A_j$ does not contain a. $A_j$ must have some item in common with every one of the $28$ pairs.
If an item b is common to $A_j$ and two subsets that contain a, it must not be in any other subset that contains a, since each triplet has only one item in common, so no three sets that include a can share the item b.
This means there must be at least 28 unique elements in $A_j$, but this is impossible since $|A_j| = 27$.
So a must be common to all sets $A_j$, in contradiction to the assumption.
answered Nov 23 at 10:20
Daphna Keidar
1896
Nice proof ! Allow me to suggest an edit : since at the beginning of your proof what you're really doing is fixing an $i$ and not reasoning on all $i$ at once, I think it would be slightly more readable if you put : "$A_1$ is part of 561 triplets and has 27 items , etc."
– Ewan Delanoy
Nov 23 at 11:52
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Lets assume there is no element common to all 35.
Any set $A_i$ is part of $binom{34}{2} = 561$ triplets. $A_i$ has 27 items. $ 27 cdot 20 = 540 < 561 $, so from the pigeonhole principle some item a in $A_i$ must be in 21 of the triplets. This means that at least 7 other sets must include a, since $binom{7}{2} = 21$. In turn, this means that a is in at least 8 sets (including $A_i$). Among these sets, there are $binom{8}{2} = 28$ pairs.
Lets assume some set $A_j$ does not contain a. $A_j$ must have some item in common with every one of the $28$ pairs.
If an item b is common to $A_j$ and two subsets that contain a, it must not be in any other subset that contains a, since each triplet has only one item in common, so no three sets that include a can share the item b.
This means there must be at least 28 unique elements in $A_j$, but this is impossible since $|A_j| = 27$.
So a must be common to all sets $A_j$, in contradiction to the assumption.
answered Nov 23 at 10:20
Daphna Keidar
1896
Nice proof ! Allow me to suggest an edit : since at the beginning of your proof what you're really doing is fixing an $i$ and not reasoning on all $i$ at once, I think it would be slightly more readable if you put : "$A_1$ is part of 561 triplets and has 27 items , etc."
– Ewan Delanoy
Nov 23 at 11:52
add a comment |
up vote
3
down vote
accepted
Lets assume there is no element common to all 35.
Any set $A_i$ is part of $binom{34}{2} = 561$ triplets. $A_i$ has 27 items. $ 27 cdot 20 = 540 < 561 $, so from the pigeonhole principle some item a in $A_i$ must be in 21 of the triplets. This means that at least 7 other sets must include a, since $binom{7}{2} = 21$. In turn, this means that a is in at least 8 sets (including $A_i$). Among these sets, there are $binom{8}{2} = 28$ pairs.
Lets assume some set $A_j$ does not contain a. $A_j$ must have some item in common with every one of the $28$ pairs.
If an item b is common to $A_j$ and two subsets that contain a, it must not be in any other subset that contains a, since each triplet has only one item in common, so no three sets that include a can share the item b.
This means there must be at least 28 unique elements in $A_j$, but this is impossible since $|A_j| = 27$.
So a must be common to all sets $A_j$, in contradiction to the assumption.
answered Nov 23 at 10:20
Daphna Keidar
1896
Nice proof ! Allow me to suggest an edit : since at the beginning of your proof what you're really doing is fixing an $i$ and not reasoning on all $i$ at once, I think it would be slightly more readable if you put : "$A_1$ is part of 561 triplets and has 27 items , etc."
– Ewan Delanoy
Nov 23 at 11:52
add a comment |
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Lets assume there is no element common to all 35.
Any set $A_i$ is part of $binom{34}{2} = 561$ triplets. $A_i$ has 27 items. $ 27 cdot 20 = 540 < 561 $, so from the pigeonhole principle some item a in $A_i$ must be in 21 of the triplets. This means that at least 7 other sets must include a, since $binom{7}{2} = 21$. In turn, this means that a is in at least 8 sets (including $A_i$). Among these sets, there are $binom{8}{2} = 28$ pairs.
Lets assume some set $A_j$ does not contain a. $A_j$ must have some item in common with every one of the $28$ pairs.
If an item b is common to $A_j$ and two subsets that contain a, it must not be in any other subset that contains a, since each triplet has only one item in common, so no three sets that include a can share the item b.
This means there must be at least 28 unique elements in $A_j$, but this is impossible since $|A_j| = 27$.
So a must be common to all sets $A_j$, in contradiction to the assumption.
answered Nov 23 at 10:20
Daphna Keidar
1896
Lets assume there is no element common to all 35.
Any set $A_i$ is part of $binom{34}{2} = 561$ triplets. $A_i$ has 27 items. $ 27 cdot 20 = 540 < 561 $, so from the pigeonhole principle some item a in $A_i$ must be in 21 of the triplets. This means that at least 7 other sets must include a, since $binom{7}{2} = 21$. In turn, this means that a is in at least 8 sets (including $A_i$). Among these sets, there are $binom{8}{2} = 28$ pairs.
Lets assume some set $A_j$ does not contain a. $A_j$ must have some item in common with every one of the $28$ pairs.
If an item b is common to $A_j$ and two subsets that contain a, it must not be in any other subset that contains a, since each triplet has only one item in common, so no three sets that include a can share the item b.
This means there must be at least 28 unique elements in $A_j$, but this is impossible since $|A_j| = 27$.
So a must be common to all sets $A_j$, in contradiction to the assumption.
answered Nov 23 at 10:20
Daphna Keidar
1896
edited Nov 23 at 22:43
answered Nov 23 at 10:20
Daphna Keidar
1896
answered Nov 23 at 10:20
Daphna Keidar
1896
answered Nov 23 at 10:20
Daphna Keidar
1896
1896
Nice proof ! Allow me to suggest an edit : since at the beginning of your proof what you're really doing is fixing an $i$ and not reasoning on all $i$ at once, I think it would be slightly more readable if you put : "$A_1$ is part of 561 triplets and has 27 items , etc."
– Ewan Delanoy
Nov 23 at 11:52
add a comment |
Nice proof ! Allow me to suggest an edit : since at the beginning of your proof what you're really doing is fixing an $i$ and not reasoning on all $i$ at once, I think it would be slightly more readable if you put : "$A_1$ is part of 561 triplets and has 27 items , etc."
– Ewan Delanoy
Nov 23 at 11:52
Nice proof ! Allow me to suggest an edit : since at the beginning of your proof what you're really doing is fixing an $i$ and not reasoning on all $i$ at once, I think it would be slightly more readable if you put : "$A_1$ is part of 561 triplets and has 27 items , etc."
– Ewan Delanoy
Nov 23 at 11:52
Nice proof ! Allow me to suggest an edit : since at the beginning of your proof what you're really doing is fixing an $i$ and not reasoning on all $i$ at once, I think it would be slightly more readable if you put : "$A_1$ is part of 561 triplets and has 27 items , etc."
– Ewan Delanoy
Nov 23 at 11:52
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004570%2fproving-that-there-is-an-element-common-to-all-35-sets-given-certain-set-restr%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
"...such that $| A_i|=27$ for all $1leq ileq 27$..." Is this a typo? Should it be $1leq ileq 35$ instead?
– YiFan
Nov 22 at 23:04
@YiFan Yes, fixed, thank you
– user574848
Nov 22 at 23:14
Consider A$_1$. There are $binom{34}{2}$= 561 triplets of sets that include A$_1$. BY the pigeonhole principle there is at least 1 element of A$_1$ that is shared by 20 of these triples. Maybe you can keep reducing the problem accordingly.
– Joel Pereira
Nov 23 at 0:09