Winnie has a deck of 8 cards where each card has a number from 1 to 4, inclusive, and each number appears twice in the deck. One at a time, Winnie reveals the top card and places it on the table. If two cards have matching numbers, she removes both of them from the table before revealing the next card. Of the 8! possible orderings of the deck, find the number of orderings such that there is never more than two distinct numbers on the table at a time.
That does not work, as this question needs recursion. Also MathCuber, I know what this is from, and please stop cheating on AOPS w26 homework. You paid money for this class, don't waste it. here's the solution for you, but without numbers. Figure it out yourself.
Consider a deck with cards. We have choices for the first card. Let the first number be . Furthermore, let be the number of valid arrangements for the remaining cards. We have the base case since there is 1 card left. For , there are three cases for the next cards:
Case 1: The 2nd card is also . This leaves numbers in the deck. There are choices for the 3rd card and arrangements for the remaining cards.
Case 2: The next two cards are then , where There are choices for the second card and 1 choice for the third card. Notice that this takes both cards out of the deck and leaves on the table, so it is as if we started with numbers. There are arrangements for the remaining cards.
Case 3: The next two cards are then , where There are choices for the second card and 1 choice for the third card. Notice that this takes both cards out of the deck and leaves on the table, so it is as if we started with numbers. There are arrangements for the remaining cards.
This gives the recurrence relationApplying this recurrence relation to gives us
There are 8 choices for the first card, so the answer is
The above suggests that a closed form solution iswhich we can prove by induction. Then since we have choices for the first card, the total number of arrangements is
btw answer is 10368
you posted on stackexchange, you're def cheating.
That does not work, as this question needs recursion. Also MathCuber, I know what this is from, and please stop cheating on AOPS w26 homework. You paid money for this class, don't waste it. here's the solution for you, but without numbers. Figure it out yourself.
Consider a deck with cards. We have choices for the first card. Let the first number be . Furthermore, let be the number of valid arrangements for the remaining cards. We have the base case since there is 1 card left. For , there are three cases for the next cards:
Case 1: The 2nd card is also . This leaves numbers in the deck. There are choices for the 3rd card and arrangements for the remaining cards.
Case 2: The next two cards are then , where There are choices for the second card and 1 choice for the third card. Notice that this takes both cards out of the deck and leaves on the table, so it is as if we started with numbers. There are arrangements for the remaining cards.
Case 3: The next two cards are then , where There are choices for the second card and 1 choice for the third card. Notice that this takes both cards out of the deck and leaves on the table, so it is as if we started with numbers. There are arrangements for the remaining cards.
This gives the recurrence relationApplying this recurrence relation to gives us
There are 8 choices for the first card, so the answer is
The above suggests that a closed form solution iswhich we can prove by induction. Then since we have choices for the first card, the total number of arrangements is
btw answer is 10368
you posted on stackexchange, you're def cheating.