Delphine has cards that each contain two pictures; one on the left side of the card and one on the right side of the card. Delphine arranges some of these cards in a row according to the following rules.
The picture on the right side of any card in the row is the same as the picture on the left side of the card to its right.
Cards can not be rotated.
The following diagram shows all of Delphine’s cards. Arrows out of a card indicate the possible card(s) that could be placed to its right.
By following the rules, what is the maximum number of cards Delphine can arrange in a row?
This problem was inspired by a past Beaver Computing Challenge (BCC) problem.
By following the rules, Delphine can arrange \(9\) cards in a row. One example of a row of \(9\) cards is shown below.
Note that it is possible to find other rows of \(9\) cards.
To determine whether or not we can arrange more than \(9\) cards in a row, look at the three circled cards in the diagram.
In the diagram, there are no arrows going out of any of these three cards because the picture on the right side of each of the cards is not on the left side of any other card. It follows that if any of these cards are used, they must be the rightmost card in the row. However any row that Delphine creates can contain only one rightmost card, so at least two of these cards cannot be used. Therefore, the maximum number of cards Delphine can arrange in a row is \(9\).