OMM 2002 Problem 4

A domino has two numbers (which may be equal) between $0$ and $6$ , one at each end. The domino may be turned around. There is one domino of each type, so $28$ in all. We want to form a chain in the usual way, so that adjacent dominos have the same number at the adjacent ends. Dominos can be added to the chain at either end. We want to form the chain so that after each domino has been added the total of all the numbers is odd. For example, we could place first the domino $(3,4)$ , total $3 + 4 = 7$ . Then $(1,3)$ , total $1 + 3 + 3 + 4 = 11$ , then $(4,4)$ , total $11 + 4 + 4 = 19$ . What is the largest number of dominos that can be placed in this way? How many maximum-length chains are there?

Attachments: