16th Mexico 2002 Problem B1 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?
16, 3456 Solution The first domino put down must have an odd total, subsequent dominos must have an even total. One of the numbers of the first domino will be odd and the other even. So any domino put next to the odd number must be odd, odd. Similarly any domino put next to the even number must be even, even. There are 12 dominos with one odd and one even number, 6 with two odd numbers, and 10 with two even numbers. Thus there are 12 choices for the first domino. Consider first the dominos added at the odd end. Suppose the odd number on the first domino is a. Let the other two odd numbers (in {1,3,5}) be b and c. We have two choices for the first non-double. It must be ab or ac. Ignoring doubles, the order is then determined. For example, after ab we must put bc, then ca. Now the aa can be put either in front of the ab or after the ca. There is only one position for each of the other two doubles. Thus we have 4 possible ways to add the 6 odd-odd dominos at the odd end. Now consider the even end. Again we start by ignoring the doubles. There are 6 non-doubles: 02, 04, 06, 24, 26, 46. Each number not at one of the two ends of the subchain of even-even non-doubles must occur an even number of times. But we have four numbers each of which appears an odd number of times in the complete set of six. So we must exclude at least one even-even non-double. Suppose the even number on the odd-even domino is A and that the other even numbers are B, C, D. The first non-double in the even-even subchain can be AB, AC or AD. There are then two choices for the second. For example, if the first was AB, the second can be BC or BD. Suppose the second was BC. Then the remaining choices are AB, BC, CA, AD, DC or AB, BC, CA, AD, DB or AB, BC, CD, DA, AC. In each case we have two choices for AA (before AB or next to CA) and two choices for the other double which can go at an end, but only one choice for the other two doubles, so 4 ways of placing the doubles. Hence 3·2·3·4 = 72 possibilities in all for the even-even subchain. Thus the maximum length is 1 + 6 + 9 = 16, and there are 12·4·72 = 3456 maximal length chains. 16th Mexican 2002 © John Scholes jscholes@kalva.demon.co.uk 5 March 2004 Last corrected/updated 5 Mar 04