Proving that the given set has at most $2^{n-1}$ elements
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 2 days ago
bof
50.5k457119
asked 2 days ago
Anu Radha
608
New contributor
Anu Radha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
|
show 1 more comment
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 2 days ago
bof
50.5k457119
asked 2 days ago
Anu Radha
608
New contributor
Anu Radha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$.
– Ashish K
2 days ago
@bof Oops, my bad. You're right.
– metamorphy
2 days ago
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.
– bof
2 days ago
1
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.
– bof
2 days ago
Hey, what happened to the answer?
– Anu Radha
2 days ago
|
show 1 more comment
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 2 days ago
bof
50.5k457119
asked 2 days ago
Anu Radha
608
New contributor
Anu Radha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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 2 days ago
bof
50.5k457119
asked 2 days ago
Anu Radha
608
New contributor
Anu Radha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
bof
50.5k457119
asked 2 days ago
Anu Radha
608
New contributor
Anu Radha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
bof
50.5k457119
edited 2 days ago
bof
50.5k457119
edited 2 days ago
bof
50.5k457119
50.5k457119
asked 2 days ago
Anu Radha
608
New contributor
Anu Radha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
Anu Radha
608
asked 2 days ago
Anu Radha
608
608
New contributor
Anu Radha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Anu Radha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Anu Radha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$.
– Ashish K
2 days ago
@bof Oops, my bad. You're right.
– metamorphy
2 days ago
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.
– bof
2 days ago
1
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.
– bof
2 days ago
Hey, what happened to the answer?
– Anu Radha
2 days ago
|
show 1 more comment
Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$.
– Ashish K
2 days ago
@bof Oops, my bad. You're right.
– metamorphy
2 days ago
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.
– bof
2 days ago
1
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.
– bof
2 days ago
Hey, what happened to the answer?
– Anu Radha
2 days ago
Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$.
– Ashish K
2 days ago
Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$.
– Ashish K
2 days ago
@bof Oops, my bad. You're right.
– metamorphy
2 days ago
@bof Oops, my bad. You're right.
– metamorphy
2 days ago
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.
– bof
2 days ago
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.
– bof
2 days ago
1
1
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.
– bof
2 days ago
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.
– bof
2 days ago
Hey, what happened to the answer?
– Anu Radha
2 days ago
Hey, what happened to the answer?
– Anu Radha
2 days ago
|
show 1 more comment
3 Answers
3
active
oldest
votes
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 yesterday
Mike
3,148211
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
– Anu Radha
19 hours ago
See below......
– Mike
19 hours ago
add a comment |
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 yesterday
J.G.
23.2k22137
This solution is fine, too. But the second part?
– Anu Radha
19 hours ago
add a comment |
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 19 hours ago
Mike
3,148211
Alright, thank you.
– Anu Radha
17 hours ago
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
});
}
});
Anu Radha is a new contributor. Be nice, and check out our Code of Conduct.
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
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 yesterday
Mike
3,148211
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
– Anu Radha
19 hours ago
See below......
– Mike
19 hours ago
add a comment |
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 yesterday
Mike
3,148211
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
– Anu Radha
19 hours ago
See below......
– Mike
19 hours ago
add a comment |
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 yesterday
Mike
3,148211
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 yesterday
Mike
3,148211
edited yesterday
answered yesterday
Mike
3,148211
answered yesterday
Mike
3,148211
answered yesterday
Mike
3,148211
3,148211
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
– Anu Radha
19 hours ago
See below......
– Mike
19 hours ago
add a comment |
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
– Anu Radha
19 hours ago
See below......
– Mike
19 hours ago
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
– Anu Radha
19 hours ago
Well, alright, the solution is fine, but does this explain the second part of the question $?$ If so, can you tell how?
– Anu Radha
19 hours ago
See below......
– Mike
19 hours ago
See below......
– Mike
19 hours ago
add a comment |
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 yesterday
J.G.
23.2k22137
This solution is fine, too. But the second part?
– Anu Radha
19 hours ago
add a comment |
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 yesterday
J.G.
23.2k22137
This solution is fine, too. But the second part?
– Anu Radha
19 hours ago
add a comment |
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 yesterday
J.G.
23.2k22137
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 yesterday
J.G.
23.2k22137
answered yesterday
J.G.
23.2k22137
answered yesterday
J.G.
23.2k22137
answered yesterday
J.G.
23.2k22137
23.2k22137
This solution is fine, too. But the second part?
– Anu Radha
19 hours ago
add a comment |
This solution is fine, too. But the second part?
– Anu Radha
19 hours ago
This solution is fine, too. But the second part?
– Anu Radha
19 hours ago
This solution is fine, too. But the second part?
– Anu Radha
19 hours ago
add a comment |
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 19 hours ago
Mike
3,148211
Alright, thank you.
– Anu Radha
17 hours ago
add a comment |
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 19 hours ago
Mike
3,148211
Alright, thank you.
– Anu Radha
17 hours ago
add a comment |
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 19 hours ago
Mike
3,148211
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 19 hours ago
Mike
3,148211
edited 18 hours ago
answered 19 hours ago
Mike
3,148211
answered 19 hours ago
Mike
3,148211
answered 19 hours ago
Mike
3,148211
3,148211
Alright, thank you.
– Anu Radha
17 hours ago
add a comment |
Alright, thank you.
– Anu Radha
17 hours ago
Alright, thank you.
– Anu Radha
17 hours ago
Alright, thank you.
– Anu Radha
17 hours ago
add a comment |
Anu Radha is a new contributor. Be nice, and check out our Code of Conduct.
Anu Radha is a new contributor. Be nice, and check out our Code of Conduct.
Anu Radha is a new contributor. Be nice, and check out our Code of Conduct.
Anu Radha is a new contributor. Be nice, and check out our Code of Conduct.
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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
Hint: If $|X|=n$, then cardinality of the power set of $X$ is $2^{n}$.
– Ashish K
2 days ago
@bof Oops, my bad. You're right.
– metamorphy
2 days ago
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.
– bof
2 days ago
1
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.
– bof
2 days ago
Hey, what happened to the answer?
– Anu Radha
2 days ago