There are N people are sitting around a circular table. Let’s call them P1, P2, . . . , PN , in order. P1 is sitting between P2 and PN . P2 is sitting between P1 and P3. P3 is sitting between P2 and P4, and so on.You need to select a non-empty subset of these people, such that no two adjacent people are selected. Find the total number of ways in which you can do so.For example, suppose N = 3, then we have P1, P2 and P3. If we select P1, then neither P2 nor P3 can be selected. So, the only valid selections are {P1}, {P2}, {P3}.So there are three possible ways, and hence the answer would be 3. Suppose N = 4, then we have P1, P2, P3 and P4. The possible subsets are {P1}, {P2}, {P3}, {P4}, {P1, P3}, {P2, P4}. So the answer would be 6.Find the answer for the following values of N:(a) N = 11(b) N = 13(c) N = 15ANS:- (a)198(b) 520 (c) 1363This question was from pen & paper test
Answers
Total of 198 Subsets
Step-by-step explanation:
First, your count for subsets of 22 is off. When you choose P4P4, you have already counted pairing that up with P1P1 and P2P2, and so you only have 66 more options, rather than 77. So, you get 8+8+7+6+5+4+3+2+1=448+8+7+6+5+4+3+2+1=44 options.
However, an easier way to count this is to say that for *each * person we can pick 88 others, giving 11⋅8=8811⋅8=88 options. Of course, now you need to rule out double-counting: first picking P1P1 and then picking P6P6 gives you the same subset as first picking P6P6 and then picking P1P1. So, you need to divide by 22. In other words, there are 882=44882=44 possible subsets of size 22
Second: what about subsets of size 33? For example, you can pick P1P1, P4P4, and P8P8. You didn't count that subset, or any subset of size 33. And you also didn't consider subsets of size 44 or 55. Now, any subset of size 66 or larger will be impossible (do you see why?), but you will have to count the subsets of size 33, 44, and 55.
OK, how many subsets of size 33 are there?
You can again start with P1P1, pick P3P3 as a second person, and then have a choice of 66 (P5P5 through P10P10) as a third. So, that's 66 options. Then, still staying with P1P1, you can pick P4P4 as your second person, but now you have only 55 persons left (P6P6 through P10P10) for the third one. So, that's another 55 options. Choosing P5P5 as the scone gives 44 options ... and continuing this, you get 6+5+4+3+2+1=216+5+4+3+2+1=21 options with P1P1 as the first person. This, of course, repeats for all 1111 people, so you get 11⋅21=23111⋅21=231 options. But again, you are overcounting, because for any subset of 33, you could have picked any of those 44 as your 'first' person. As such, every triple got counted 33 times, and so you have 2313=772313=77 possible subsets of size 3
For Subsets of 4
Again, start with P1P1, add P3P3, then P5P5, and now you have 44 options left (P7P7 though P10P10). Now we can make the third person P6P6, and that gives you 3+2+1=63+2+1=6 options. Likewise, you get 2+1=32+1=3 and 11 one more while having P1P1 as the second person. So, there are 10+6+3+1=2010+6+3+1=20 subsets with P1P1 as the first person. Again, multiply by 1111 ... and divide by 44, since each subset gets counted 44 times, since we could have started going around with each of the 44 people in each subset. So: 11⋅204=55
For Subsets of 5
With P1P1, P3P3, P5P5, and P7P7 you have 22 options left. You can also make P8P8 the fourth person, and now there is 11 option left. You can make the third P6P6, and that also leads to 11 options, and finally you can pick P4P4 as the second, for a final option. Total: 55 subsets with P1P1. Again, multiply by 1111, and divide by size of subsets: 11⋅55=1111⋅55=11 possibilities.
Total
11+44+77+55+11=19811+44+77+55+11=198 subsets