Question 429803: you have a set of intergers 1-20 you make subsets of six numbers. Such that no one number is subsequet to the one before it(eg. 1,2...3,4..15,16..19,20 etcc)
good case (2,4,7,11,13,19)
bad case (1,2,4,11,14,17)
bad case (4,7,11,13,14,19)
the answer is 5005?
Answer by richard1234(7193)   (Show Source):
You can put this solution on YOUR website! Suppose we mark chosen numbers with an X, and unchosen numbers with an O. For a given chosen number n, we can mark that number with an X and n+1 with an O, then proceed with n+2. Hence, we will see a string of twenty characters with some "XO"s and "O"s.
For example, the subset {2,5,7,10,16,19} can be expressed as
O[XO]O[XO][XO]O[XO]OOOO[XO]O[XO].
For such a subset, there will be six [XO] strings and eight O's (since 6*2 + 8 = 20). There are 14C6 = 3003 ways to arrange these strings to form a 20-character sequence.
The only flaw is if the number 20 is chosen, because there can be no O afterwards. To account for these possibilities, we fix 20 to be X, and choose five elements out of the remaining 19 (we can do this because 19 is guaranteed to be O). Here, there will be five [XO] strings and 9 O's, so the number of combinations is 14C5 = 2002.
Therefore, the total number of ways is 3003 + 2002 = 5005.
|
|
|
