'selfish' set to be a set which has its own cardinality (number of elements) as an element
up vote
4
down vote
favorite
Define a selfish set to be a set which has its own cardinality (number of elements) as an element. Find, with proof, the number of subsets of ${1, 2, ldots, n}$ which are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish.
My Attempt:
Assume $textbf{A}$ to be a selfish set. If the cardinality of $textbf{A}$ is $c$, then can $textbf{A}$ contain $1,2,3....c-1$. Definitely answer is no. because if it contains $k<c$ then deleting $c-k$ elements except $k$ from $textbf{A}$ gives a subset of k elements contradicting the fact that $textbf{A}$ is minimal selfish.
Thus $textbf{A}$ must contain elements greater than or equal to $c$. But how do I find the minimal selfish sets with order $c$?
combinatorics discrete-mathematics
edited Dec 8 at 10:20
Mutantoe
558411
asked Dec 8 at 6:03
Suraj
1149
add a comment |
up vote
4
down vote
favorite
Define a selfish set to be a set which has its own cardinality (number of elements) as an element. Find, with proof, the number of subsets of ${1, 2, ldots, n}$ which are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish.
My Attempt:
Assume $textbf{A}$ to be a selfish set. If the cardinality of $textbf{A}$ is $c$, then can $textbf{A}$ contain $1,2,3....c-1$. Definitely answer is no. because if it contains $k<c$ then deleting $c-k$ elements except $k$ from $textbf{A}$ gives a subset of k elements contradicting the fact that $textbf{A}$ is minimal selfish.
Thus $textbf{A}$ must contain elements greater than or equal to $c$. But how do I find the minimal selfish sets with order $c$?
combinatorics discrete-mathematics
edited Dec 8 at 10:20
Mutantoe
558411
asked Dec 8 at 6:03
Suraj
1149
Reference note: This question, including the terminology, was problem B1 on the 1996 Putnam.
– jmerry
Dec 8 at 7:51
add a comment |
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Define a selfish set to be a set which has its own cardinality (number of elements) as an element. Find, with proof, the number of subsets of ${1, 2, ldots, n}$ which are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish.
My Attempt:
Assume $textbf{A}$ to be a selfish set. If the cardinality of $textbf{A}$ is $c$, then can $textbf{A}$ contain $1,2,3....c-1$. Definitely answer is no. because if it contains $k<c$ then deleting $c-k$ elements except $k$ from $textbf{A}$ gives a subset of k elements contradicting the fact that $textbf{A}$ is minimal selfish.
Thus $textbf{A}$ must contain elements greater than or equal to $c$. But how do I find the minimal selfish sets with order $c$?
combinatorics discrete-mathematics
edited Dec 8 at 10:20
Mutantoe
558411
asked Dec 8 at 6:03
Suraj
1149
Define a selfish set to be a set which has its own cardinality (number of elements) as an element. Find, with proof, the number of subsets of ${1, 2, ldots, n}$ which are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish.
My Attempt:
Assume $textbf{A}$ to be a selfish set. If the cardinality of $textbf{A}$ is $c$, then can $textbf{A}$ contain $1,2,3....c-1$. Definitely answer is no. because if it contains $k<c$ then deleting $c-k$ elements except $k$ from $textbf{A}$ gives a subset of k elements contradicting the fact that $textbf{A}$ is minimal selfish.
Thus $textbf{A}$ must contain elements greater than or equal to $c$. But how do I find the minimal selfish sets with order $c$?
combinatorics discrete-mathematics
combinatorics discrete-mathematics
edited Dec 8 at 10:20
Mutantoe
558411
asked Dec 8 at 6:03
Suraj
1149
edited Dec 8 at 10:20
Mutantoe
558411
asked Dec 8 at 6:03
Suraj
1149
edited Dec 8 at 10:20
Mutantoe
558411
edited Dec 8 at 10:20
Mutantoe
558411
edited Dec 8 at 10:20
Mutantoe
558411
558411
asked Dec 8 at 6:03
Suraj
1149
asked Dec 8 at 6:03
Suraj
1149
asked Dec 8 at 6:03
Suraj
1149
1149
Reference note: This question, including the terminology, was problem B1 on the 1996 Putnam.
– jmerry
Dec 8 at 7:51
add a comment |
Reference note: This question, including the terminology, was problem B1 on the 1996 Putnam.
– jmerry
Dec 8 at 7:51
Reference note: This question, including the terminology, was problem B1 on the 1996 Putnam.
– jmerry
Dec 8 at 7:51
Reference note: This question, including the terminology, was problem B1 on the 1996 Putnam.
– jmerry
Dec 8 at 7:51
add a comment |
2 Answers
2
active
oldest
votes
up vote
5
down vote
accepted
Your argument is correct.
Lets see if recursion helps.
Let $[n]$ denote the set ${1,2,ldots,n}$, and let $f_n$ denote the
number of minimal selfish subsets of $[n]$. Then the number of
minimal selfish subsets of $[n]$ not containing $n$ is equal to
$f_{n-1}$. On the other hand, for any minimal selfish subset of $[n]$
containing $n$, by subtracting 1 from each element, and then taking
away the element $n-1$ from the set, we obtain a minimal selfish
subset of $[n-2]$ (since $1$ and $n$ cannot both occur in a selfish
set). Conversely, any minimal selfish subset of $[n-2]$ gives rise to
a minimal selfish subset of $[n]$ containing $n$ by the inverse
procedure. Hence the number of minimal selfish subsets of $[n]$
containing $n$ is $f_{n-2}$. Thus we obtain $f_n=f_{n-1}+f_{n-2}$.
Since $f_1=f_2=1$, we have $f_n=F_n$, where $F_n$ denotes the $n$th
term of the Fibonacci sequence.
answered Dec 8 at 6:10
Rakesh Bhatt
917113
add a comment |
up vote
1
down vote
Your logic so far is fine. So what you know is that, since $c$ is in the set, then the other $c-1$ elements must all be at least $c+1$. There are $binom{n-c}{c-1}$ ways to choose them.
Summing over these gives you the total count. It turns out that this gives you the $n^{th}$ Fibonacci number, which you can prove by induction (hint: use Pascal’s identity).
answered Dec 8 at 6:08
platty
3,329320
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',
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%2f3030745%2fselfish-set-to-be-a-set-which-has-its-own-cardinality-number-of-elements-as%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
Your argument is correct.
Lets see if recursion helps.
Let $[n]$ denote the set ${1,2,ldots,n}$, and let $f_n$ denote the
number of minimal selfish subsets of $[n]$. Then the number of
minimal selfish subsets of $[n]$ not containing $n$ is equal to
$f_{n-1}$. On the other hand, for any minimal selfish subset of $[n]$
containing $n$, by subtracting 1 from each element, and then taking
away the element $n-1$ from the set, we obtain a minimal selfish
subset of $[n-2]$ (since $1$ and $n$ cannot both occur in a selfish
set). Conversely, any minimal selfish subset of $[n-2]$ gives rise to
a minimal selfish subset of $[n]$ containing $n$ by the inverse
procedure. Hence the number of minimal selfish subsets of $[n]$
containing $n$ is $f_{n-2}$. Thus we obtain $f_n=f_{n-1}+f_{n-2}$.
Since $f_1=f_2=1$, we have $f_n=F_n$, where $F_n$ denotes the $n$th
term of the Fibonacci sequence.
answered Dec 8 at 6:10
Rakesh Bhatt
917113
add a comment |
up vote
5
down vote
accepted
Your argument is correct.
Lets see if recursion helps.
Let $[n]$ denote the set ${1,2,ldots,n}$, and let $f_n$ denote the
number of minimal selfish subsets of $[n]$. Then the number of
minimal selfish subsets of $[n]$ not containing $n$ is equal to
$f_{n-1}$. On the other hand, for any minimal selfish subset of $[n]$
containing $n$, by subtracting 1 from each element, and then taking
away the element $n-1$ from the set, we obtain a minimal selfish
subset of $[n-2]$ (since $1$ and $n$ cannot both occur in a selfish
set). Conversely, any minimal selfish subset of $[n-2]$ gives rise to
a minimal selfish subset of $[n]$ containing $n$ by the inverse
procedure. Hence the number of minimal selfish subsets of $[n]$
containing $n$ is $f_{n-2}$. Thus we obtain $f_n=f_{n-1}+f_{n-2}$.
Since $f_1=f_2=1$, we have $f_n=F_n$, where $F_n$ denotes the $n$th
term of the Fibonacci sequence.
answered Dec 8 at 6:10
Rakesh Bhatt
917113
add a comment |
up vote
5
down vote
accepted
up vote
5
down vote
accepted
Your argument is correct.
Lets see if recursion helps.
Let $[n]$ denote the set ${1,2,ldots,n}$, and let $f_n$ denote the
number of minimal selfish subsets of $[n]$. Then the number of
minimal selfish subsets of $[n]$ not containing $n$ is equal to
$f_{n-1}$. On the other hand, for any minimal selfish subset of $[n]$
containing $n$, by subtracting 1 from each element, and then taking
away the element $n-1$ from the set, we obtain a minimal selfish
subset of $[n-2]$ (since $1$ and $n$ cannot both occur in a selfish
set). Conversely, any minimal selfish subset of $[n-2]$ gives rise to
a minimal selfish subset of $[n]$ containing $n$ by the inverse
procedure. Hence the number of minimal selfish subsets of $[n]$
containing $n$ is $f_{n-2}$. Thus we obtain $f_n=f_{n-1}+f_{n-2}$.
Since $f_1=f_2=1$, we have $f_n=F_n$, where $F_n$ denotes the $n$th
term of the Fibonacci sequence.
answered Dec 8 at 6:10
Rakesh Bhatt
917113
Your argument is correct.
Lets see if recursion helps.
Let $[n]$ denote the set ${1,2,ldots,n}$, and let $f_n$ denote the
number of minimal selfish subsets of $[n]$. Then the number of
minimal selfish subsets of $[n]$ not containing $n$ is equal to
$f_{n-1}$. On the other hand, for any minimal selfish subset of $[n]$
containing $n$, by subtracting 1 from each element, and then taking
away the element $n-1$ from the set, we obtain a minimal selfish
subset of $[n-2]$ (since $1$ and $n$ cannot both occur in a selfish
set). Conversely, any minimal selfish subset of $[n-2]$ gives rise to
a minimal selfish subset of $[n]$ containing $n$ by the inverse
procedure. Hence the number of minimal selfish subsets of $[n]$
containing $n$ is $f_{n-2}$. Thus we obtain $f_n=f_{n-1}+f_{n-2}$.
Since $f_1=f_2=1$, we have $f_n=F_n$, where $F_n$ denotes the $n$th
term of the Fibonacci sequence.
answered Dec 8 at 6:10
Rakesh Bhatt
917113
answered Dec 8 at 6:10
Rakesh Bhatt
917113
answered Dec 8 at 6:10
Rakesh Bhatt
917113
answered Dec 8 at 6:10
Rakesh Bhatt
917113
917113
add a comment |
add a comment |
up vote
1
down vote
Your logic so far is fine. So what you know is that, since $c$ is in the set, then the other $c-1$ elements must all be at least $c+1$. There are $binom{n-c}{c-1}$ ways to choose them.
Summing over these gives you the total count. It turns out that this gives you the $n^{th}$ Fibonacci number, which you can prove by induction (hint: use Pascal’s identity).
answered Dec 8 at 6:08
platty
3,329320
add a comment |
up vote
1
down vote
Your logic so far is fine. So what you know is that, since $c$ is in the set, then the other $c-1$ elements must all be at least $c+1$. There are $binom{n-c}{c-1}$ ways to choose them.
Summing over these gives you the total count. It turns out that this gives you the $n^{th}$ Fibonacci number, which you can prove by induction (hint: use Pascal’s identity).
answered Dec 8 at 6:08
platty
3,329320
add a comment |
up vote
1
down vote
up vote
1
down vote
Your logic so far is fine. So what you know is that, since $c$ is in the set, then the other $c-1$ elements must all be at least $c+1$. There are $binom{n-c}{c-1}$ ways to choose them.
Summing over these gives you the total count. It turns out that this gives you the $n^{th}$ Fibonacci number, which you can prove by induction (hint: use Pascal’s identity).
answered Dec 8 at 6:08
platty
3,329320
Your logic so far is fine. So what you know is that, since $c$ is in the set, then the other $c-1$ elements must all be at least $c+1$. There are $binom{n-c}{c-1}$ ways to choose them.
Summing over these gives you the total count. It turns out that this gives you the $n^{th}$ Fibonacci number, which you can prove by induction (hint: use Pascal’s identity).
answered Dec 8 at 6:08
platty
3,329320
answered Dec 8 at 6:08
platty
3,329320
answered Dec 8 at 6:08
platty
3,329320
answered Dec 8 at 6:08
platty
3,329320
3,329320
add a comment |
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.
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%2f3030745%2fselfish-set-to-be-a-set-which-has-its-own-cardinality-number-of-elements-as%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
Reference note: This question, including the terminology, was problem B1 on the 1996 Putnam.
– jmerry
Dec 8 at 7:51