Re: US Chain Letters

I'm leaving off spoiler space as Ilan has posted good solutions.
The original problem was somewhat tractable without a computer as
one could some eliminate states or see that they could only be the first
or last member of the chain. There are some other ideas that reduce
the dimension search space, similar to your node idea.
For the full 59 pair problem, it needs a computer.
That said, it is interesting to me that there are 9984=256*3*13
different variations but they all use the same 30 choices.
E.g., FMMPPWWVVIIAASSDDCCTTNNCCOOHHIINNMMNNVVAAKKSSCCAALLAARRIIDDE
L. Flynn
On 7/3/2025 3:46 AM, David Entwistle wrote:

On Sun, 22 Jun 2025 20:56:28 -0400, leflynn wrote:
 

Recently Games Magazine had a Wild Card entry where the goal was to find
the longest chain of US States where the last letter of an entry in the
chain had to be the same as the first letter of the next entry.
>
Here are three more challenging problems.
1. Find the longest chain using the two-letter US Post office codes for
the 50 states.
2. Same as 1. but add the postal codes for the District of Columbia and
the five US Territories for a total of 56 two-letter codes.
3. Same as 2. but add the postal codes for the three Possessions.
>
https://faq.usps.com/s/article/What-are-the-USPS-abbreviations-for-U-S-

states-and-territories

>
L. Flynn

 Nice problem.
 Does anyone have a strategy, other than getting a machine to do all the
hard work, to approach this problem?
 Shuffling cards didn't get me near an optimal solution - not in the time i
allowed. A matrix showing first letters across, and second letters down,
with a mark where the zip code is valid, seems useful, but didn't lead to
an obvious solution.
 I'm happy for a machine to do some of the work, but I'd be happier if the
approach was something other than "blindly" trying every avenue and
keeping the best solution.
 Some thoughts... It would seem sensible to consider "nodes" which only
have one route between them first and try and include those in any
solution. The letter matrix idea reminds me of a electronic switching
matrix. For some reason Kirchoff and his current and voltage laws keeps
coming to mind.