Dani has 10 cards, each with a number on one side. The numbers on the cards are 10, 15, 27, 33, 34, 35, 64, 65, 143, and 323. The cards are placed on a table with the numbers facing up.
Dani takes a card and flips it over so it is now face down. Of the remaining cards that are still face up, the next card she flips over must have a prime factor in common with the card she last flipped over. She continues in this way until either all the cards have been flipped over, or she is unable to flip any of the cards that remain face up.
List all the possible orders in which Dani can flip the cards so that all cards get flipped over.
We will start by writing down the prime factors for each of the numbers on the cards.
| Number | Prime Factors |
|---|---|
| 10 | 2, 5 |
| 15 | 3, 5 |
| 27 | 3 |
| 33 | 3, 11 |
| 34 | 2, 17 |
| 35 | 5, 7 |
| 64 | 2 |
| 65 | 5, 13 |
| 143 | 11, 13 |
| 323 | 17, 19 |
Notice the number 323 shares a prime factor with only the number 34. That means we must start (or end) with 323.
If we start with 323, then the next number must be 34. From 34, the next number could be 64 or 10. If the next number were 10, then in order to eventually flip over the 64 card, the 64 must follow the 10, and at this point no more cards can be flipped. Therefore, in order to flip all the cards, the first four numbers flipped must be 323, 34, 64, and then 10.
From this point, we can draw lines between numbers that share prime factors to create the following diagram.
We now need to figure out the number of paths through the diagram, starting at 10, that use each number exactly once.
After 10, the next number can be 35, 65, or 15. In each case, we carefully trace through all possible paths.
Case 1: The number 35 follows the number 10. That gives us the following five possible paths:
35, 15, 65, 143, 33, 27
35, 15, 27, 33, 143, 65
35, 65, 15, 27, 33, 143
35, 65, 143, 33, 27, 15
35, 65, 143, 33, 15, 27
Case 2: The number 65 follows the number 10. That gives us the following two possible paths:
65, 143, 33, 27, 15, 35
65, 35, 15, 27, 33, 143
Case 3: The number 15 follows the number 10. That gives us the following two possible paths:
15, 27, 33, 143, 65, 35
15, 35, 65, 143, 33, 27
Therefore, starting with the card numbered 323, we have found that there is a total of nine orders for flipping the cards:
323, 34, 64, 10, 35, 15, 65, 143, 33, 27
323, 34, 64, 10, 35, 15, 27, 33, 143, 65
323, 34, 64, 10, 35, 65, 15, 27, 33, 143
323, 34, 64, 10, 35, 65, 143, 33, 27, 15
323, 34, 64, 10, 35, 65, 143, 33, 15, 27
323, 34, 64, 10, 65, 143, 33, 27, 15, 35
323, 34, 64, 10, 65, 35, 15, 27, 33, 143
323, 34, 64, 10, 15, 27, 33, 143, 65, 35
323, 34, 64, 10, 15, 35, 65, 143, 33, 27
Note that each of these can be reversed. Therefore, there are 18 orders in which Dani can flip the cards so that all cards get flipped over. They are the 9 orders listed above and the reverse of each.