Problem
of the Week
Problem
D and Solution
Arranging
Cards

Problem

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.

There are eleven cards in total. A description of each card is given in the following table.

Card

Picture on the Left

Picture on the Right

Car/Crab

Car

Crab

Car/Walrus

Car

Walrus

Car/Car

Car

Car

Bicycle/Car

Bicycle

Car

Car/Rainbow

Car

Rainbow

Car/Dinosaur

Car

Dinosaur

Dinosaur/Car

Dinosaur

Car

Dinosaur/Airplane

Dinosaur

Airplane

Airplane/Dinosaur

Airplane

Dinosaur

Dinosaur/Bicycle

Dinosaur

Bicycle

Bicycle/Dinosaur

Bicycle

Dinosaur

By following the rules, what is the maximum number of cards Delphine
can arrange in a row?

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\).