Engrave numbers on 5 keys on a circular keyring so that the numbers on adjacent groups of keys sum to any value between 1 and 21 inclusively.

For example, 1,1,3,6,6 can sum up to any number between 1 and 17 (1=1, 1+1=2, 3=3, 3+1=4, 3+1+1=5, 6=6, 6+1=7, 6+1+1=8, 6+3=9, 6+3+1=10, etc).

The total possible number of sums for a 5-key ring is exactly 21, so that means that every single combination must be used to sum a different number!  All five keys must sum to 21.  If a group of keys sums up to a number between 1 and 10, then there must be a group of keys that sums up to 21 minus that number, so I only need to worry about sums 1 through 10, and the total sum.

Obviously, one of the keys must have a 1.  There cannot be any other 1s, since that would cause two groups to have the same sum.  Therefore, there must be a 2.

There are two possibilities now.  If the 2 is next to the 1, the next number to add would be a 4.  If the 2 is not next to the 1, the next number must be a 3.

I feel I can brute force the rest of the way, but I will stop for a while.

Posted by Tristan on 2005-03-28 20:18:36