+0  
 
0
54
3
avatar+531 

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.

 Mar 30, 2020
 #1
avatar
0

The number of ways to order the deck is 1*3*5*7 = 105.

 Mar 31, 2020
 #2
avatar
0

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. 

Guest Apr 6, 2020
 #3
avatar
0

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. 

 Apr 6, 2020

26 Online Users

avatar
avatar
avatar
avatar