<p>You’re right. This is a difficult problem. Let me try to point some of these sharp students in the right direction. A good strategy would be to start with smaller sets. First count the minimal selfish subsets of {1}, then of {1,2}, then {!,2,3} and so on. For the first few it’s easy to just list them. Then later we can look for a pattern. Can anyone do it for these smaller sets?</p>
<p>Is the answer 36? <em>crosses fingers</em></p>
<p>Edit: I think I got it wrong</p>
<p>Is it 2^9 or 512?</p>
<p>36 is not correct. Feel free to post your reasoning - then I can tell you if you’re on the right track.</p>
<p>Let’s tackle some smaller problems first. </p>
<p>Let X<em>n = {1,2,3,…,n} (So A = X</em>10 = {1,2,3,4,5,6,7,8,9,10} for example)</p>
<p>Tell me how many minimal selfish subsets X_1 has.</p>
<p>Do the same for X<em>2, X</em>3, and X_4.</p>
<p>We’ll get to X_10 eventually.</p>
<p>Oh no. My bad. I meant 512 selfish subsets.</p>
<p>@Jeffrey</p>
<p>Are you counting ALL selfish subsets? (not just minimal ones)</p>
<p>Then yes, X<em>n has 2^{n-1} selfish subsets. In particular, A = X</em>10 has 2^9 = 512 selfish subsets.</p>
<p>Now just count the minimal ones.</p>
<p>I don’t understand your explanation of “Minimal” subset. Can you give an example?</p>
<p>Yeah… I had a feeling I was wrong. I’ll try to post my reasoning.</p>
<p>I gave an example in the problem itself. Here’s a smaller example:</p>
<p>{1,2} is selfish , but not minimal because {1} is a selfish subset. </p>
<p>However, {2,3} is a minimal selfish set becasue any nonempty subset has only 1 element, but 1 isn’t in the set.</p>
<p>Then, is the total number of minimal selfish set 512-8 = 504?</p>
<p>pckeller’s and your problems are extremely intriguing. It’s difficult but interesting…</p>
<p>I take back my answer… I’ll post again… :)</p>
<p>Are there 81 minimal selfish subsets?</p>
<p>This is way more difficult than anything that would be on the SAT; this is definitely late AMC/early AIME level. Not sure if my solution is right but I’ll give it a go.</p>
<p>Okay, let’s start with 1. How many minimal selfish subsets contain 1? Only {1}, of course, because if you had anything else in, you could take everything besides the 1 out and end up with a selfish set.</p>
<p>Now let’s move on to 2. How many minimal selfish subsets contain 2? Well, we know 1 can’t be an element. We have to add something, since {2} by itself doesn’t work, but if we add more than 1 element, we could take out all but two of them, leaving 2 in, and get a selfish set. So we want to add exactly one element, and we can do this 8C1 ways.</p>
<p>What about 3? Same reasoning (we want to add 2 elements), and we can do it 7C2 ways. Then 4 is 6C3 and 5 is 5C4. Adding it all up gives 55.</p>
<p>55 happens to be 1+2+3+…10! And the same problem for A={1,2,…,8} gives an answer of 21, which is 1+2+…6. I can’t see why that would be true, or if that’s just coincidence; I’ll think on it more later I guess.</p>
<p>I feel like I’m only trying to get the correct answer.</p>
<p>My reasoning:</p>
<p>Subset with 1 number: None of them are minimal selfish.
Subset with 2 numbers: 2 has to be included, and 1 cannot be included. (1<em>8)/ = 8 subsets
Subset with 3 numbers: 3 has to be included, and 1-2 cannot be included. (1</em>7<em>6)/2! = 21
Subset with 4 numbers: 4 has to be included, and 1-3 cannot be included. (1</em>6<em>5</em>4)/3! = 20
Subset with 5 numbers: 5 has to be included, and 1-4 cannot be included. (1<em>5</em>4<em>3</em>2)/4! = 5
Subset with 6-10 numbers: 6 has to be included, and 1-5 cannot be included. (none)</p>
<p>8 + 21 + 20 + 5 = 54 total minimal selfish subsets.</p>
<p>@Conquerer </p>
<p>It looks like you got the correct answer for X<em>10 and X</em>8, and your reasoning looks correct. Your final statement about sums is not correct though (but I think you’re on the right track). </p>
<p>For example, X<em>2 has just 1 minimal selfish subset (what is it?), and X</em>3 has 2 minimal selfish subsets (what are they?)</p>
<p>@Jeffrey</p>
<p>Looks like you also got the answer for X_10 the same way that Conquerer did.</p>
<p>Now can you tell me how many minimal selfish subsets X_n has for arbitrary n?</p>
<p>In triangle ABC on a coordinate plane, the coordinates of A are (-4,4) and the coordinates of B are (4,4). If the area of triangle ABC is 24, what are the coordinates of C?</p>
<p>^ Either (0,-2) or (0,10).</p>
<p>veethiv: anywhere on the line y = -2 or y = 10.</p>
<p>DrSteve: Aha, they’re Fibonacci numbers. A<em>n = F</em>n where F<em>n = F</em>n-1 + F<em>n-2 and F</em>1 = F_2 = 1. Now the question is, why?</p>
<p>You can sort of ‘make’ the minimal selfish subsets of A<em>n out of those of A</em>n-1 and A<em>n-2. A</em>n has all of the minimal selfish subsets that A<em>n-1 has. Now, we could add 5 to any one of them, but doing only that would make the subset not selfish anymore! Alternatively, we could simply add one to every element of a minimal selfish subset of A</em>n-1, and then add n on. That would work since it’s definitely still minimal and the smallest number matches the cardinality. There’s only one problem: A<em>n-1 has selfish subsets containing n-1, which would be increased to n. Then we’d be counting n ‘twice’, and that’s bad. What’s another name for the minimal selfish subsets of A</em>n-1 that don’t contain n-1? A_n-2.</p>
<p>Thus, A<em>n = A</em>n-1 + A_n-2.</p>
<p>Example: The sets for 5 are {1}, {2,3}, {2,4}, {2,5}, and {3,4,5}. This has all the ones from the 4 element set: {1}, {2,3}, and {2,4}. The ones from the 3 element set are {1} and {2,3} and those become {2,5} and {3,4,5} respectively.</p>
<p>Very nice conqueror! Let me clarify what you’re saying just a bit. </p>
<p>There is 1 minimal selfish subset of X_1 = {1}, namely {1} itself.</p>
<p>There is also 1 minimal selfish subset of X_2 = {1,2}: {1}</p>
<p>There are 1+1=2 minimal selfish subsets of X<em>3 = {1,2,3}. These are {1}, and {2,3}. We get the first one by just taking the same subset of X</em>2. We get the second one by taking {1} from X_1, adding 1 to each element, and throwing in 3, ie {1+1,3} = {2,3}</p>
<p>There are 2+1=3 minimal selfish subsets of X<em>4 = {1,2,3,4}. These are {1},{2,3}, and {2,4}. The first 2 are the same as the subsets of X</em>3, and we get the last one by adding one to each element of X_2 and throwing in 4. {2+1,4} = {3,4}</p>
<p>In general, we get the minimal subsets of X<em>n by taking the minimal selfish subsets of X</em>{n-1} and then, for each minimal selfish subset of X<em>{n-2} we add 1 to each element, and throw in n. Thus we see that |X</em>n|=f<em>n where f</em>n is the nth term in the fibonacci sequence.</p>
<p>The fibonacci sequence is 1,1,2,3,5,8,13,21…
In particular, X_8 has 21 minimal selfish subsets.</p>
<p>This thread just blows my mind.</p>