Mixing
Proving that the given set has at most $2^{n-1}$ elements
$begingroup$
Let $n$ be a natural number and $X$ = {$1,2,...,n$}. For subsets $A$ and $B$ of $X$ we define $ADelta B$ to be the set of all those elements of $X$ which belong to exactly one of $A$ and $B$. Let $F$ be a collection of subsets of $X$ such that for any two distinct elements $A$ and $B$ in $F$ the set $A∆B$ has at least two elements. Show that $F$ has at most $2^{n-1}$ elements. Find all such collections $F$ with $2^{n−1}$ elements.
I have no clue on how and where to start. Please help.
combinatorics
edited Jan 5 at 10:34
bof
51.1k457120
asked Jan 5 at 10:03
YellowYellow
16011
$endgroup$
|
show 1 more comment
$begingroup$
Let $n$ be a natural number and $X$ = {$1,2,...,n$}. For subsets $A$ and $B$ of $X$ we define $ADelta B$ to be the set of all those elements of $X$ which belong to exactly one of $A$ and $B$. Let $F$ be a collection of subsets of $X$ such that for any two distinct elements $A$ and $B$ in $F$ the set $A∆B$ has at least two elements. Show that $F$ has at most $2^{n-1}$ elements. Find all such collections $F$ with $2^{n−1}$ elements.
I have no clue on how and where to start. Please help.
combinatorics
edited Jan 5 at 10:34
bof
51.1k457120
asked Jan 5 at 10:03
YellowYellow
16011
$endgroup$
$begingroup$
Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$.
$endgroup$
– Ashish K
Jan 5 at 10:12
$begingroup$
@bof Oops, my bad. You're right.
$endgroup$
– metamorphy
Jan 5 at 10:37
$begingroup$
It's not necessary, but I find it more pleasant to think of such a problem in terms of binary words (bitstrings) of length $n$ instead of subsets. You want a set of binary codewords of length $n$ such that any two different codewords differ in at least $2$ places, a so-called single error detecting code.
$endgroup$
– bof
Jan 5 at 10:53
1
$begingroup$
To see that you can't have more than $2^{n-1}$, observe that the $2^n$ subsets (or words) can be partitioned into pairs, so that each pair differs only in one place; thus your collection can't include more than one from each pair, so it can't contain more than half of the $2^n$ sets.
$endgroup$
– bof
Jan 5 at 10:55
$begingroup$
Hey, what happened to the answer?
$endgroup$
– Yellow
Jan 5 at 12:02
|
show 1 more comment
$begingroup$
Let $n$ be a natural number and $X$ = {$1,2,...,n$}. For subsets $A$ and $B$ of $X$ we define $ADelta B$ to be the set of all those elements of $X$ which belong to exactly one of $A$ and $B$. Let $F$ be a collection of subsets of $X$ such that for any two distinct elements $A$ and $B$ in $F$ the set $A∆B$ has at least two elements. Show that $F$ has at most $2^{n-1}$ elements. Find all such collections $F$ with $2^{n−1}$ elements.
I have no clue on how and where to start. Please help.
combinatorics
edited Jan 5 at 10:34
bof
51.1k457120
asked Jan 5 at 10:03
YellowYellow
16011
$endgroup$
Let $n$ be a natural number and $X$ = {$1,2,...,n$}. For subsets $A$ and $B$ of $X$ we define $ADelta B$ to be the set of all those elements of $X$ which belong to exactly one of $A$ and $B$. Let $F$ be a collection of subsets of $X$ such that for any two distinct elements $A$ and $B$ in $F$ the set $A∆B$ has at least two elements. Show that $F$ has at most $2^{n-1}$ elements. Find all such collections $F$ with $2^{n−1}$ elements.
I have no clue on how and where to start. Please help.
combinatorics
combinatorics
edited Jan 5 at 10:34
bof
51.1k457120
asked Jan 5 at 10:03
YellowYellow
16011
edited Jan 5 at 10:34
bof
51.1k457120
asked Jan 5 at 10:03
YellowYellow
16011
edited Jan 5 at 10:34
bof
51.1k457120
edited Jan 5 at 10:34
bof
51.1k457120
edited Jan 5 at 10:34
bof
51.1k457120
51.1k457120
asked Jan 5 at 10:03
YellowYellow
16011
asked Jan 5 at 10:03
YellowYellow
16011
asked Jan 5 at 10:03
YellowYellow
16011
16011
$begingroup$
Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$.
$endgroup$
– Ashish K
Jan 5 at 10:12
$begingroup$
@bof Oops, my bad. You're right.
$endgroup$
– metamorphy
Jan 5 at 10:37
$begingroup$
It's not necessary, but I find it more pleasant to think of such a problem in terms of binary words (bitstrings) of length $n$ instead of subsets. You want a set of binary codewords of length $n$ such that any two different codewords differ in at least $2$ places, a so-called single error detecting code.
$endgroup$
– bof
Jan 5 at 10:53
1
$begingroup$
To see that you can't have more than $2^{n-1}$, observe that the $2^n$ subsets (or words) can be partitioned into pairs, so that each pair differs only in one place; thus your collection can't include more than one from each pair, so it can't contain more than half of the $2^n$ sets.
$endgroup$
– bof
Jan 5 at 10:55
$begingroup$
Hey, what happened to the answer?
$endgroup$
– Yellow
Jan 5 at 12:02
|
show 1 more comment
$begingroup$
Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$.
$endgroup$
– Ashish K
Jan 5 at 10:12
$begingroup$
@bof Oops, my bad. You're right.
$endgroup$
– metamorphy
Jan 5 at 10:37
$begingroup$
It's not necessary, but I find it more pleasant to think of such a problem in terms of binary words (bitstrings) of length $n$ instead of subsets. You want a set of binary codewords of length $n$ such that any two different codewords differ in at least $2$ places, a so-called single error detecting code.
$endgroup$
– bof
Jan 5 at 10:53
1
$begingroup$
To see that you can't have more than $2^{n-1}$, observe that the $2^n$ subsets (or words) can be partitioned into pairs, so that each pair differs only in one place; thus your collection can't include more than one from each pair, so it can't contain more than half of the $2^n$ sets.
$endgroup$
– bof
Jan 5 at 10:55
$begingroup$
Hey, what happened to the answer?
$endgroup$
– Yellow
Jan 5 at 12:02
$begingroup$
Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$.
$endgroup$
– Ashish K
Jan 5 at 10:12
$begingroup$
Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$.
$endgroup$
– Ashish K
Jan 5 at 10:12
$begingroup$
@bof Oops, my bad. You're right.
$endgroup$
– metamorphy
Jan 5 at 10:37
$begingroup$
@bof Oops, my bad. You're right.
$endgroup$
– metamorphy
Jan 5 at 10:37
$begingroup$
It's not necessary, but I find it more pleasant to think of such a problem in terms of binary words (bitstrings) of length $n$ instead of subsets. You want a set of binary codewords of length $n$ such that any two different codewords differ in at least $2$ places, a so-called single error detecting code.
$endgroup$
– bof
Jan 5 at 10:53
$begingroup$
It's not necessary, but I find it more pleasant to think of such a problem in terms of binary words (bitstrings) of length $n$ instead of subsets. You want a set of binary codewords of length $n$ such that any two different codewords differ in at least $2$ places, a so-called single error detecting code.
$endgroup$
– bof
Jan 5 at 10:53
1
1
$begingroup$
To see that you can't have more than $2^{n-1}$, observe that the $2^n$ subsets (or words) can be partitioned into pairs, so that each pair differs only in one place; thus your collection can't include more than one from each pair, so it can't contain more than half of the $2^n$ sets.
$endgroup$
– bof
Jan 5 at 10:55
$begingroup$
To see that you can't have more than $2^{n-1}$, observe that the $2^n$ subsets (or words) can be partitioned into pairs, so that each pair differs only in one place; thus your collection can't include more than one from each pair, so it can't contain more than half of the $2^n$ sets.
$endgroup$
– bof
Jan 5 at 10:55
$begingroup$
Hey, what happened to the answer?
$endgroup$
– Yellow
Jan 5 at 12:02
$begingroup$
Hey, what happened to the answer?
$endgroup$
– Yellow
Jan 5 at 12:02
|
show 1 more comment
3 Answers
3
active
oldest
votes
$begingroup$
Let us write $X={1,ldots, n}$ and let $P_{n-1}$ be the collection of subsets of $X setminus {n}$. For each $S in P_{n-1}$, let us define $f(S) = S cup {n}$. Now let $P_n$ be the collection of subsets of $X$. Note that
$f(S)$ is defined for each $S in P_{n-1}$;
$f(S) not in P_{n-1}$ for each $S in P_{n-1}$;
If $S$ and $S'$ are distinct sets in $P_{n-1}$ then $f(S) not = f(S')$;
Therefore $P_{n-1}$ and ${f(S); S in P_{n-1}}$ are disjoint and of equal cardinality, and furthermore, $P_{n-1}$ and ${f(S); S in P_{n-1}}$ partition $P_n$.
So write $P_n = {S_1,S_2,ldots, S_{2^n}}$ where the $S_i$s are distinct and where $f(S_i) = S_{i+1}$ for each odd $i$; this is possible by 1. and 4. together. Then $F$ can contain at most one of $S_i$ and $S_{i+1}$ for each odd $i$, as the disjoint union of $S$ and $f(S)$ is precisely ${n}$ which has only 1 < 2 elements.
answered Jan 5 at 18:21
MikeMike
3,507411
$endgroup$
$begingroup$
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
$endgroup$
– Yellow
Jan 6 at 16:18
$begingroup$
See below......
$endgroup$
– Mike
Jan 6 at 16:59
add a comment |
$begingroup$
I'll expand on one of bof's comments. If $n>0$ fix some $ain X$ and pair the subsets of $X$ as $y,,ycup{a}$ with $anotin y$. Not both of these are in $F$ because $yDelta(ycup{a})={a}$, so $|F|$ is at most half the number of subsets of $X$, i.e. $2^{n-1}$ as desired. (I'll leave you to consider the case $n=0$ separately.)
answered Jan 5 at 18:12
J.G.J.G.
24.6k22539
$endgroup$
$begingroup$
This solution is fine, too. But the second part?
$endgroup$
– Yellow
Jan 6 at 16:24
add a comment |
$begingroup$
As far as a collection $F$ with $2^{n-1}$ elements, let $F$ be the set of subsets of $X$ of odd cardinality. [Make sure you see why this works]
The set of subsets of $X$ of even cardinality would work too. [Make sure you see why this works] Thus the set of subsets of even cardinality has, by the above answers, only $2^{n-1}$ elements, which implies that the set $F$ of subsets of $X$ of odd cardinality has $2^{n-1}$ elements. And vice versa.
answered Jan 6 at 16:59
MikeMike
3,507411
$endgroup$
$begingroup$
Alright, thank you.
$endgroup$
– Yellow
Jan 6 at 18:25
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3062577%2fproving-that-the-given-set-has-at-most-2n-1-elements%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let us write $X={1,ldots, n}$ and let $P_{n-1}$ be the collection of subsets of $X setminus {n}$. For each $S in P_{n-1}$, let us define $f(S) = S cup {n}$. Now let $P_n$ be the collection of subsets of $X$. Note that
$f(S)$ is defined for each $S in P_{n-1}$;
$f(S) not in P_{n-1}$ for each $S in P_{n-1}$;
If $S$ and $S'$ are distinct sets in $P_{n-1}$ then $f(S) not = f(S')$;
Therefore $P_{n-1}$ and ${f(S); S in P_{n-1}}$ are disjoint and of equal cardinality, and furthermore, $P_{n-1}$ and ${f(S); S in P_{n-1}}$ partition $P_n$.
So write $P_n = {S_1,S_2,ldots, S_{2^n}}$ where the $S_i$s are distinct and where $f(S_i) = S_{i+1}$ for each odd $i$; this is possible by 1. and 4. together. Then $F$ can contain at most one of $S_i$ and $S_{i+1}$ for each odd $i$, as the disjoint union of $S$ and $f(S)$ is precisely ${n}$ which has only 1 < 2 elements.
answered Jan 5 at 18:21
MikeMike
3,507411
$endgroup$
$begingroup$
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
$endgroup$
– Yellow
Jan 6 at 16:18
$begingroup$
See below......
$endgroup$
– Mike
Jan 6 at 16:59
add a comment |
$begingroup$
Let us write $X={1,ldots, n}$ and let $P_{n-1}$ be the collection of subsets of $X setminus {n}$. For each $S in P_{n-1}$, let us define $f(S) = S cup {n}$. Now let $P_n$ be the collection of subsets of $X$. Note that
$f(S)$ is defined for each $S in P_{n-1}$;
$f(S) not in P_{n-1}$ for each $S in P_{n-1}$;
If $S$ and $S'$ are distinct sets in $P_{n-1}$ then $f(S) not = f(S')$;
Therefore $P_{n-1}$ and ${f(S); S in P_{n-1}}$ are disjoint and of equal cardinality, and furthermore, $P_{n-1}$ and ${f(S); S in P_{n-1}}$ partition $P_n$.
So write $P_n = {S_1,S_2,ldots, S_{2^n}}$ where the $S_i$s are distinct and where $f(S_i) = S_{i+1}$ for each odd $i$; this is possible by 1. and 4. together. Then $F$ can contain at most one of $S_i$ and $S_{i+1}$ for each odd $i$, as the disjoint union of $S$ and $f(S)$ is precisely ${n}$ which has only 1 < 2 elements.
answered Jan 5 at 18:21
MikeMike
3,507411
$endgroup$
$begingroup$
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
$endgroup$
– Yellow
Jan 6 at 16:18
$begingroup$
See below......
$endgroup$
– Mike
Jan 6 at 16:59
add a comment |
$begingroup$
Let us write $X={1,ldots, n}$ and let $P_{n-1}$ be the collection of subsets of $X setminus {n}$. For each $S in P_{n-1}$, let us define $f(S) = S cup {n}$. Now let $P_n$ be the collection of subsets of $X$. Note that
$f(S)$ is defined for each $S in P_{n-1}$;
$f(S) not in P_{n-1}$ for each $S in P_{n-1}$;
If $S$ and $S'$ are distinct sets in $P_{n-1}$ then $f(S) not = f(S')$;
Therefore $P_{n-1}$ and ${f(S); S in P_{n-1}}$ are disjoint and of equal cardinality, and furthermore, $P_{n-1}$ and ${f(S); S in P_{n-1}}$ partition $P_n$.
So write $P_n = {S_1,S_2,ldots, S_{2^n}}$ where the $S_i$s are distinct and where $f(S_i) = S_{i+1}$ for each odd $i$; this is possible by 1. and 4. together. Then $F$ can contain at most one of $S_i$ and $S_{i+1}$ for each odd $i$, as the disjoint union of $S$ and $f(S)$ is precisely ${n}$ which has only 1 < 2 elements.
answered Jan 5 at 18:21
MikeMike
3,507411
$endgroup$
Let us write $X={1,ldots, n}$ and let $P_{n-1}$ be the collection of subsets of $X setminus {n}$. For each $S in P_{n-1}$, let us define $f(S) = S cup {n}$. Now let $P_n$ be the collection of subsets of $X$. Note that
$f(S)$ is defined for each $S in P_{n-1}$;
$f(S) not in P_{n-1}$ for each $S in P_{n-1}$;
If $S$ and $S'$ are distinct sets in $P_{n-1}$ then $f(S) not = f(S')$;
Therefore $P_{n-1}$ and ${f(S); S in P_{n-1}}$ are disjoint and of equal cardinality, and furthermore, $P_{n-1}$ and ${f(S); S in P_{n-1}}$ partition $P_n$.
So write $P_n = {S_1,S_2,ldots, S_{2^n}}$ where the $S_i$s are distinct and where $f(S_i) = S_{i+1}$ for each odd $i$; this is possible by 1. and 4. together. Then $F$ can contain at most one of $S_i$ and $S_{i+1}$ for each odd $i$, as the disjoint union of $S$ and $f(S)$ is precisely ${n}$ which has only 1 < 2 elements.
answered Jan 5 at 18:21
MikeMike
3,507411
edited Jan 5 at 18:27
answered Jan 5 at 18:21
MikeMike
3,507411
answered Jan 5 at 18:21
MikeMike
3,507411
answered Jan 5 at 18:21
MikeMike
3,507411
3,507411
$begingroup$
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
$endgroup$
– Yellow
Jan 6 at 16:18
$begingroup$
See below......
$endgroup$
– Mike
Jan 6 at 16:59
add a comment |
$begingroup$
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
$endgroup$
– Yellow
Jan 6 at 16:18
$begingroup$
See below......
$endgroup$
– Mike
Jan 6 at 16:59
$begingroup$
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
$endgroup$
– Yellow
Jan 6 at 16:18
$begingroup$
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
$endgroup$
– Yellow
Jan 6 at 16:18
$begingroup$
See below......
$endgroup$
– Mike
Jan 6 at 16:59
$begingroup$
See below......
$endgroup$
– Mike
Jan 6 at 16:59
add a comment |
$begingroup$
I'll expand on one of bof's comments. If $n>0$ fix some $ain X$ and pair the subsets of $X$ as $y,,ycup{a}$ with $anotin y$. Not both of these are in $F$ because $yDelta(ycup{a})={a}$, so $|F|$ is at most half the number of subsets of $X$, i.e. $2^{n-1}$ as desired. (I'll leave you to consider the case $n=0$ separately.)
answered Jan 5 at 18:12
J.G.J.G.
24.6k22539
$endgroup$
$begingroup$
This solution is fine, too. But the second part?
$endgroup$
– Yellow
Jan 6 at 16:24
add a comment |
$begingroup$
I'll expand on one of bof's comments. If $n>0$ fix some $ain X$ and pair the subsets of $X$ as $y,,ycup{a}$ with $anotin y$. Not both of these are in $F$ because $yDelta(ycup{a})={a}$, so $|F|$ is at most half the number of subsets of $X$, i.e. $2^{n-1}$ as desired. (I'll leave you to consider the case $n=0$ separately.)
answered Jan 5 at 18:12
J.G.J.G.
24.6k22539
$endgroup$
$begingroup$
This solution is fine, too. But the second part?
$endgroup$
– Yellow
Jan 6 at 16:24
add a comment |
$begingroup$
I'll expand on one of bof's comments. If $n>0$ fix some $ain X$ and pair the subsets of $X$ as $y,,ycup{a}$ with $anotin y$. Not both of these are in $F$ because $yDelta(ycup{a})={a}$, so $|F|$ is at most half the number of subsets of $X$, i.e. $2^{n-1}$ as desired. (I'll leave you to consider the case $n=0$ separately.)
answered Jan 5 at 18:12
J.G.J.G.
24.6k22539
$endgroup$
I'll expand on one of bof's comments. If $n>0$ fix some $ain X$ and pair the subsets of $X$ as $y,,ycup{a}$ with $anotin y$. Not both of these are in $F$ because $yDelta(ycup{a})={a}$, so $|F|$ is at most half the number of subsets of $X$, i.e. $2^{n-1}$ as desired. (I'll leave you to consider the case $n=0$ separately.)
answered Jan 5 at 18:12
J.G.J.G.
24.6k22539
answered Jan 5 at 18:12
J.G.J.G.
24.6k22539
answered Jan 5 at 18:12
J.G.J.G.
24.6k22539
answered Jan 5 at 18:12
J.G.J.G.
24.6k22539
24.6k22539
$begingroup$
This solution is fine, too. But the second part?
$endgroup$
– Yellow
Jan 6 at 16:24
add a comment |
$begingroup$
This solution is fine, too. But the second part?
$endgroup$
– Yellow
Jan 6 at 16:24
$begingroup$
This solution is fine, too. But the second part?
$endgroup$
– Yellow
Jan 6 at 16:24
$begingroup$
This solution is fine, too. But the second part?
$endgroup$
– Yellow
Jan 6 at 16:24
add a comment |
$begingroup$
As far as a collection $F$ with $2^{n-1}$ elements, let $F$ be the set of subsets of $X$ of odd cardinality. [Make sure you see why this works]
The set of subsets of $X$ of even cardinality would work too. [Make sure you see why this works] Thus the set of subsets of even cardinality has, by the above answers, only $2^{n-1}$ elements, which implies that the set $F$ of subsets of $X$ of odd cardinality has $2^{n-1}$ elements. And vice versa.
answered Jan 6 at 16:59
MikeMike
3,507411
$endgroup$
$begingroup$
Alright, thank you.
$endgroup$
– Yellow
Jan 6 at 18:25
add a comment |
$begingroup$
As far as a collection $F$ with $2^{n-1}$ elements, let $F$ be the set of subsets of $X$ of odd cardinality. [Make sure you see why this works]
The set of subsets of $X$ of even cardinality would work too. [Make sure you see why this works] Thus the set of subsets of even cardinality has, by the above answers, only $2^{n-1}$ elements, which implies that the set $F$ of subsets of $X$ of odd cardinality has $2^{n-1}$ elements. And vice versa.
answered Jan 6 at 16:59
MikeMike
3,507411
$endgroup$
$begingroup$
Alright, thank you.
$endgroup$
– Yellow
Jan 6 at 18:25
add a comment |
$begingroup$
As far as a collection $F$ with $2^{n-1}$ elements, let $F$ be the set of subsets of $X$ of odd cardinality. [Make sure you see why this works]
The set of subsets of $X$ of even cardinality would work too. [Make sure you see why this works] Thus the set of subsets of even cardinality has, by the above answers, only $2^{n-1}$ elements, which implies that the set $F$ of subsets of $X$ of odd cardinality has $2^{n-1}$ elements. And vice versa.
answered Jan 6 at 16:59
MikeMike
3,507411
$endgroup$
As far as a collection $F$ with $2^{n-1}$ elements, let $F$ be the set of subsets of $X$ of odd cardinality. [Make sure you see why this works]
The set of subsets of $X$ of even cardinality would work too. [Make sure you see why this works] Thus the set of subsets of even cardinality has, by the above answers, only $2^{n-1}$ elements, which implies that the set $F$ of subsets of $X$ of odd cardinality has $2^{n-1}$ elements. And vice versa.
answered Jan 6 at 16:59
MikeMike
3,507411
edited Jan 6 at 17:16
answered Jan 6 at 16:59
MikeMike
3,507411
answered Jan 6 at 16:59
MikeMike
3,507411
answered Jan 6 at 16:59
MikeMike
3,507411
3,507411
$begingroup$
Alright, thank you.
$endgroup$
– Yellow
Jan 6 at 18:25
add a comment |
$begingroup$
Alright, thank you.
$endgroup$
– Yellow
Jan 6 at 18:25
$begingroup$
Alright, thank you.
$endgroup$
– Yellow
Jan 6 at 18:25
$begingroup$
Alright, thank you.
$endgroup$
– Yellow
Jan 6 at 18:25
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f3062577%2fproving-that-the-given-set-has-at-most-2n-1-elements%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
$begingroup$
Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$.
$endgroup$
– Ashish K
Jan 5 at 10:12
$begingroup$
@bof Oops, my bad. You're right.
$endgroup$
– metamorphy
Jan 5 at 10:37
$begingroup$
It's not necessary, but I find it more pleasant to think of such a problem in terms of binary words (bitstrings) of length $n$ instead of subsets. You want a set of binary codewords of length $n$ such that any two different codewords differ in at least $2$ places, a so-called single error detecting code.
$endgroup$
– bof
Jan 5 at 10:53
1
$begingroup$
To see that you can't have more than $2^{n-1}$, observe that the $2^n$ subsets (or words) can be partitioned into pairs, so that each pair differs only in one place; thus your collection can't include more than one from each pair, so it can't contain more than half of the $2^n$ sets.
$endgroup$
– bof
Jan 5 at 10:55
$begingroup$
Hey, what happened to the answer?
$endgroup$
– Yellow
Jan 5 at 12:02