Mixing
$n$-element subsets of the set $1,2, …, 2n$.
Clash Royale CLAN TAG#URR8PPP
up vote
6
down vote
favorite
There are $binom2n n$, $n$-element subsets of the set $1,2, ..., 2n$. I am studying the question whether one can choose from these subsets $frac12binom2n n$ subsets such that:
i) each element from $1$ to $2n$ belongs to exactly $frac14 cdotbinom2n n$ of the selected subsets;
ii) any two selected subsets had at least one common element.
If $n$ is a power of two, then the answer is no, because then $binom2n n$ is not divisible by $4$.
If $n$ is not a power of two, then $binom2n n$ is divisible by $4$. For $n = 3$ I found an example:
$$1,2,3,1,2,4,1,3,5,1,4,6,1,5,6$$
$$2,3,6,2,4,5,2,5,6,3,4,5,3,4,6$$
I do not know what the answer is for other $n$, for example, when $n = 9$.
Computer check is too big.
combinatorics binomial-coefficients combinatorial-designs
edited Jul 17 at 18:28
Mike Earnest
15.5k11645
asked Jul 16 at 11:31
Roman83
14.3k31754
add a comment |Â
up vote
6
down vote
favorite
There are $binom2n n$, $n$-element subsets of the set $1,2, ..., 2n$. I am studying the question whether one can choose from these subsets $frac12binom2n n$ subsets such that:
i) each element from $1$ to $2n$ belongs to exactly $frac14 cdotbinom2n n$ of the selected subsets;
ii) any two selected subsets had at least one common element.
If $n$ is a power of two, then the answer is no, because then $binom2n n$ is not divisible by $4$.
If $n$ is not a power of two, then $binom2n n$ is divisible by $4$. For $n = 3$ I found an example:
$$1,2,3,1,2,4,1,3,5,1,4,6,1,5,6$$
$$2,3,6,2,4,5,2,5,6,3,4,5,3,4,6$$
I do not know what the answer is for other $n$, for example, when $n = 9$.
Computer check is too big.
combinatorics binomial-coefficients combinatorial-designs
edited Jul 17 at 18:28
Mike Earnest
15.5k11645
asked Jul 16 at 11:31
Roman83
14.3k31754
By the way, all your binomial coefficients were upside down; I've fixed that for you.
– J.G.
Jul 16 at 11:33
@J.G.: Thank you!
– Roman83
Jul 16 at 11:36
I would have thought that provided $binom2nn$ is a multiple of $20$, which it is for $n=3,9,13,14,15,17,18,19,20,21,22,23,24$ and many more, then there is a simple extension to your example for $n=3$. Other cases such as $n=5,6,7,10,11,12,25$ might need a different approach
– Henry
Jul 16 at 11:49
add a comment |Â
up vote
6
down vote
favorite
up vote
6
down vote
favorite
There are $binom2n n$, $n$-element subsets of the set $1,2, ..., 2n$. I am studying the question whether one can choose from these subsets $frac12binom2n n$ subsets such that:
i) each element from $1$ to $2n$ belongs to exactly $frac14 cdotbinom2n n$ of the selected subsets;
ii) any two selected subsets had at least one common element.
If $n$ is a power of two, then the answer is no, because then $binom2n n$ is not divisible by $4$.
If $n$ is not a power of two, then $binom2n n$ is divisible by $4$. For $n = 3$ I found an example:
$$1,2,3,1,2,4,1,3,5,1,4,6,1,5,6$$
$$2,3,6,2,4,5,2,5,6,3,4,5,3,4,6$$
I do not know what the answer is for other $n$, for example, when $n = 9$.
Computer check is too big.
combinatorics binomial-coefficients combinatorial-designs
edited Jul 17 at 18:28
Mike Earnest
15.5k11645
asked Jul 16 at 11:31
Roman83
14.3k31754
There are $binom2n n$, $n$-element subsets of the set $1,2, ..., 2n$. I am studying the question whether one can choose from these subsets $frac12binom2n n$ subsets such that:
i) each element from $1$ to $2n$ belongs to exactly $frac14 cdotbinom2n n$ of the selected subsets;
ii) any two selected subsets had at least one common element.
If $n$ is a power of two, then the answer is no, because then $binom2n n$ is not divisible by $4$.
If $n$ is not a power of two, then $binom2n n$ is divisible by $4$. For $n = 3$ I found an example:
$$1,2,3,1,2,4,1,3,5,1,4,6,1,5,6$$
$$2,3,6,2,4,5,2,5,6,3,4,5,3,4,6$$
I do not know what the answer is for other $n$, for example, when $n = 9$.
Computer check is too big.
combinatorics binomial-coefficients combinatorial-designs
edited Jul 17 at 18:28
Mike Earnest
15.5k11645
asked Jul 16 at 11:31
Roman83
14.3k31754
edited Jul 17 at 18:28
Mike Earnest
15.5k11645
edited Jul 17 at 18:28
Mike Earnest
15.5k11645
edited Jul 17 at 18:28
Mike Earnest
15.5k11645
15.5k11645
asked Jul 16 at 11:31
Roman83
14.3k31754
asked Jul 16 at 11:31
Roman83
14.3k31754
asked Jul 16 at 11:31
Roman83
14.3k31754
14.3k31754
By the way, all your binomial coefficients were upside down; I've fixed that for you.
– J.G.
Jul 16 at 11:33
@J.G.: Thank you!
– Roman83
Jul 16 at 11:36
I would have thought that provided $binom2nn$ is a multiple of $20$, which it is for $n=3,9,13,14,15,17,18,19,20,21,22,23,24$ and many more, then there is a simple extension to your example for $n=3$. Other cases such as $n=5,6,7,10,11,12,25$ might need a different approach
– Henry
Jul 16 at 11:49
add a comment |Â
By the way, all your binomial coefficients were upside down; I've fixed that for you.
– J.G.
Jul 16 at 11:33
@J.G.: Thank you!
– Roman83
Jul 16 at 11:36
I would have thought that provided $binom2nn$ is a multiple of $20$, which it is for $n=3,9,13,14,15,17,18,19,20,21,22,23,24$ and many more, then there is a simple extension to your example for $n=3$. Other cases such as $n=5,6,7,10,11,12,25$ might need a different approach
– Henry
Jul 16 at 11:49
By the way, all your binomial coefficients were upside down; I've fixed that for you.
– J.G.
Jul 16 at 11:33
By the way, all your binomial coefficients were upside down; I've fixed that for you.
– J.G.
Jul 16 at 11:33
@J.G.: Thank you!
– Roman83
Jul 16 at 11:36
@J.G.: Thank you!
– Roman83
Jul 16 at 11:36
I would have thought that provided $binom2nn$ is a multiple of $20$, which it is for $n=3,9,13,14,15,17,18,19,20,21,22,23,24$ and many more, then there is a simple extension to your example for $n=3$. Other cases such as $n=5,6,7,10,11,12,25$ might need a different approach
– Henry
Jul 16 at 11:49
I would have thought that provided $binom2nn$ is a multiple of $20$, which it is for $n=3,9,13,14,15,17,18,19,20,21,22,23,24$ and many more, then there is a simple extension to your example for $n=3$. Other cases such as $n=5,6,7,10,11,12,25$ might need a different approach
– Henry
Jul 16 at 11:49
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Here is a method for when $2n-1$ is prime, and $2nchoose n$ is a multiple of 4.
Let $M=1,2,ldots,2n-1$.
Let $B$ be the collection of $(n-1)$-element subsets of $M$.
$C$ will be a subset of half the sets in $B$, as follows:
Start with $C$ empty. Pick any $bin B$ that has not been chosen. Put it in $C$, along with its offsets $b_i=g+ipmod2n-1:gin b$. For example, if $2n-1=11$, and $b=1,2,4,6,7$, then you also include in $C$:
$$2,3,5,7,8,3,4,6,8,9,4,5,7,9,10,5,6,8,10,11,6,7,9,11,1,7,8,10,1,2,8,9,11,2,3,9,10,1,3,4,10,11,2,4,5,11,1,3,5,6$$
So you put $2n-1$ sets at a time into $C$. Keep adding sets from $B$ into $C$ until you have exactly half. Each number from $1$ to $2n-1$ appears in the same number of sets in $C$. We will later include $2n$ in each of these sets.
Let $D$ be the collection of $n$-element subsets of $M$, none of which is the complement of a $cin C$. Each number from $1$ to $2n-1$ also appears in the same number of elements of $D$.
Your set is $ccup2n:cin Ccup D$
All the numbers from $1$ to $2n-1$ appear equally in $C$, and in $D$. $2n$ appears in half the sets; so all appear in exactly half the sets.
If two sets come from the $C$ side, they have $2n$ in common.
If two sets come from the $D$ side, they have $2n$ elements from the numbers in $M$, so some element is in both sets.
If a set comes from $C$ and one from $D$, recall that $C$ and $D$ were chosen so that $ccup dneq M$, so they have an element in common.
answered Jul 16 at 13:44
Michael
2,577213
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Here is a method for when $2n-1$ is prime, and $2nchoose n$ is a multiple of 4.
Let $M=1,2,ldots,2n-1$.
Let $B$ be the collection of $(n-1)$-element subsets of $M$.
$C$ will be a subset of half the sets in $B$, as follows:
Start with $C$ empty. Pick any $bin B$ that has not been chosen. Put it in $C$, along with its offsets $b_i=g+ipmod2n-1:gin b$. For example, if $2n-1=11$, and $b=1,2,4,6,7$, then you also include in $C$:
$$2,3,5,7,8,3,4,6,8,9,4,5,7,9,10,5,6,8,10,11,6,7,9,11,1,7,8,10,1,2,8,9,11,2,3,9,10,1,3,4,10,11,2,4,5,11,1,3,5,6$$
So you put $2n-1$ sets at a time into $C$. Keep adding sets from $B$ into $C$ until you have exactly half. Each number from $1$ to $2n-1$ appears in the same number of sets in $C$. We will later include $2n$ in each of these sets.
Let $D$ be the collection of $n$-element subsets of $M$, none of which is the complement of a $cin C$. Each number from $1$ to $2n-1$ also appears in the same number of elements of $D$.
Your set is $ccup2n:cin Ccup D$
All the numbers from $1$ to $2n-1$ appear equally in $C$, and in $D$. $2n$ appears in half the sets; so all appear in exactly half the sets.
If two sets come from the $C$ side, they have $2n$ in common.
If two sets come from the $D$ side, they have $2n$ elements from the numbers in $M$, so some element is in both sets.
If a set comes from $C$ and one from $D$, recall that $C$ and $D$ were chosen so that $ccup dneq M$, so they have an element in common.
answered Jul 16 at 13:44
Michael
2,577213
add a comment |Â
up vote
2
down vote
accepted
Here is a method for when $2n-1$ is prime, and $2nchoose n$ is a multiple of 4.
Let $M=1,2,ldots,2n-1$.
Let $B$ be the collection of $(n-1)$-element subsets of $M$.
$C$ will be a subset of half the sets in $B$, as follows:
Start with $C$ empty. Pick any $bin B$ that has not been chosen. Put it in $C$, along with its offsets $b_i=g+ipmod2n-1:gin b$. For example, if $2n-1=11$, and $b=1,2,4,6,7$, then you also include in $C$:
$$2,3,5,7,8,3,4,6,8,9,4,5,7,9,10,5,6,8,10,11,6,7,9,11,1,7,8,10,1,2,8,9,11,2,3,9,10,1,3,4,10,11,2,4,5,11,1,3,5,6$$
So you put $2n-1$ sets at a time into $C$. Keep adding sets from $B$ into $C$ until you have exactly half. Each number from $1$ to $2n-1$ appears in the same number of sets in $C$. We will later include $2n$ in each of these sets.
Let $D$ be the collection of $n$-element subsets of $M$, none of which is the complement of a $cin C$. Each number from $1$ to $2n-1$ also appears in the same number of elements of $D$.
Your set is $ccup2n:cin Ccup D$
All the numbers from $1$ to $2n-1$ appear equally in $C$, and in $D$. $2n$ appears in half the sets; so all appear in exactly half the sets.
If two sets come from the $C$ side, they have $2n$ in common.
If two sets come from the $D$ side, they have $2n$ elements from the numbers in $M$, so some element is in both sets.
If a set comes from $C$ and one from $D$, recall that $C$ and $D$ were chosen so that $ccup dneq M$, so they have an element in common.
answered Jul 16 at 13:44
Michael
2,577213
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Here is a method for when $2n-1$ is prime, and $2nchoose n$ is a multiple of 4.
Let $M=1,2,ldots,2n-1$.
Let $B$ be the collection of $(n-1)$-element subsets of $M$.
$C$ will be a subset of half the sets in $B$, as follows:
Start with $C$ empty. Pick any $bin B$ that has not been chosen. Put it in $C$, along with its offsets $b_i=g+ipmod2n-1:gin b$. For example, if $2n-1=11$, and $b=1,2,4,6,7$, then you also include in $C$:
$$2,3,5,7,8,3,4,6,8,9,4,5,7,9,10,5,6,8,10,11,6,7,9,11,1,7,8,10,1,2,8,9,11,2,3,9,10,1,3,4,10,11,2,4,5,11,1,3,5,6$$
So you put $2n-1$ sets at a time into $C$. Keep adding sets from $B$ into $C$ until you have exactly half. Each number from $1$ to $2n-1$ appears in the same number of sets in $C$. We will later include $2n$ in each of these sets.
Let $D$ be the collection of $n$-element subsets of $M$, none of which is the complement of a $cin C$. Each number from $1$ to $2n-1$ also appears in the same number of elements of $D$.
Your set is $ccup2n:cin Ccup D$
All the numbers from $1$ to $2n-1$ appear equally in $C$, and in $D$. $2n$ appears in half the sets; so all appear in exactly half the sets.
If two sets come from the $C$ side, they have $2n$ in common.
If two sets come from the $D$ side, they have $2n$ elements from the numbers in $M$, so some element is in both sets.
If a set comes from $C$ and one from $D$, recall that $C$ and $D$ were chosen so that $ccup dneq M$, so they have an element in common.
answered Jul 16 at 13:44
Michael
2,577213
Here is a method for when $2n-1$ is prime, and $2nchoose n$ is a multiple of 4.
Let $M=1,2,ldots,2n-1$.
Let $B$ be the collection of $(n-1)$-element subsets of $M$.
$C$ will be a subset of half the sets in $B$, as follows:
Start with $C$ empty. Pick any $bin B$ that has not been chosen. Put it in $C$, along with its offsets $b_i=g+ipmod2n-1:gin b$. For example, if $2n-1=11$, and $b=1,2,4,6,7$, then you also include in $C$:
$$2,3,5,7,8,3,4,6,8,9,4,5,7,9,10,5,6,8,10,11,6,7,9,11,1,7,8,10,1,2,8,9,11,2,3,9,10,1,3,4,10,11,2,4,5,11,1,3,5,6$$
So you put $2n-1$ sets at a time into $C$. Keep adding sets from $B$ into $C$ until you have exactly half. Each number from $1$ to $2n-1$ appears in the same number of sets in $C$. We will later include $2n$ in each of these sets.
Let $D$ be the collection of $n$-element subsets of $M$, none of which is the complement of a $cin C$. Each number from $1$ to $2n-1$ also appears in the same number of elements of $D$.
Your set is $ccup2n:cin Ccup D$
All the numbers from $1$ to $2n-1$ appear equally in $C$, and in $D$. $2n$ appears in half the sets; so all appear in exactly half the sets.
If two sets come from the $C$ side, they have $2n$ in common.
If two sets come from the $D$ side, they have $2n$ elements from the numbers in $M$, so some element is in both sets.
If a set comes from $C$ and one from $D$, recall that $C$ and $D$ were chosen so that $ccup dneq M$, so they have an element in common.
answered Jul 16 at 13:44
Michael
2,577213
answered Jul 16 at 13:44
Michael
2,577213
answered Jul 16 at 13:44
Michael
2,577213
answered Jul 16 at 13:44
Michael
2,577213
2,577213
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853329%2fn-element-subsets-of-the-set-1-2-2n%23new-answer', 'question_page');
);
Post as a guest
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
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
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
By the way, all your binomial coefficients were upside down; I've fixed that for you.
– J.G.
Jul 16 at 11:33
@J.G.: Thank you!
– Roman83
Jul 16 at 11:36
I would have thought that provided $binom2nn$ is a multiple of $20$, which it is for $n=3,9,13,14,15,17,18,19,20,21,22,23,24$ and many more, then there is a simple extension to your example for $n=3$. Other cases such as $n=5,6,7,10,11,12,25$ might need a different approach
– Henry
Jul 16 at 11:49