Each of the triangular numbers that are below 1000 is written on a separate card. Some of these cards are then placed in a circle so that, viewed from the center, the right-hand digit of each card matches the left-hand digit of the card to its right. No tricks are used such as turning a card upside-down.

What's the maximum number of digits that can appear on such a subset of the cards?

The best solution has 12 entries. For instance; 

153 - 3 - 351 - 15 - 55 - 595 - 561 - 105 - 528 - 861 - 171 - 1

All other length 12 solutions are formed from this same set of entries and make use of the fact that each of the palindrome entries (55, 595) and (1, 171) can be switched in order or individually relocated to follow (respectively) 105 or either one of {351, 561}.

Method:

I populated a table for the 44 triangulars less than 1000:

Begins  #Entrances    Exits  Set   

1   9   3*0+2*1+3+2*5   1,10,15,105,120,136,153,171,190 

2   6   0+2*1+3+6+8    21,28,210,231,253,276

3   6   0+1+3+5+6+8    3,26,300,325,351,378

4   5   3*5+2*6         45,406,435,465,496

5   4   1+2*5+8         55,528,561,595

6   4   0+3*6           6,66,630,660

7   4   0+1+3+8         78,703,741,780

8   2   0+1             820,861

9   4   0+1+3+6         91,903,949,990

(Exits, by the way, records the number of occurences of a last digits among the triangular numbers with a given first digit. I.e., for numbers beginning with 6, there is one continuation beginning with 0 and three continuations beginning with 6)

We can exclude the possibility of an appearance of many elements in the ring by examining this table.

1. There are no numbers beginning with 0, so we can eliminate {10,120,190,210,300,630,780,820,990}.

2. 6 is a cul-de sac, i.e., if we move to 6 we can never leave it. Therefore we exclude {136,276,36,406,496,6,66,666,946}. 

3. There are no entrances to 4. Therefore we eliminate {45,435,465}.

4. There are no entrances to 7. Eliminate {78,703,741}.

5. There are no entrances to 2. Eliminate {21,28,231,253}.

6. There are no entrances to 9. Eliminate {91,903}.

7. There is only one entrance to 8, but there are two entrances. We must chose one out of {378, 528} for elimination

8. There are at most 2 exits from 5. We must remove at least one element from the set {15,105,325}.

9. There is only one entrance to 3, but none of {325,351,378} have as yet been definitively excluded. This fact establishes how we are to exercise the choices presented in steps 7 and 8. Namely, we eliminate {325,378}.

Inspection quickly reveals that the remaining elements can be strung together as shown above

Posted by FrankM on 2008-01-15 11:58:46