6
$\begingroup$

This is a variation of List of US-states without common letters . This is supposed to be more difficult and challenging than the original problem.

Create a list of US-States, one name per line, such that no two consecutive States in the list do contain any common letter (and such that each State occurs at most once).

This is an example:

Texas
Wyoming
Utah
New York

You have 2 tasks:

  1. Determine the maximum number $N$ of States in such a list.
  2. Determine the maximum number $L$ of letters in such a list (that is, the sum of the lengths of all the States' names in the list).

The second task is probably more difficult than the first one. I will accept only answers with a complete solution. If nobody comes up with a solution within 72 hours, I will add a hint.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Assuming a state can't appear twice in the list (if it could, then the answer to both questions is infinite):

The maximum length of the list is 21, and the maximum of L is 151, or 149 if you don't count spaces in two-word states.

Counting or not counting spaces does not affect the resulting list of states, which is:

  1. Florida,
  2. Kentucky
  3. Idaho
  4. New Jersey
  5. Oklahoma
  6. Tennessee
  7. Colorado
  8. Mississippi
  9. New York
  10. Alabama
  11. Connecticut
  12. Alaska
  13. Vermont
  14. Hawaii
  15. Oregon
  16. Utah
  17. Wyoming
  18. Texas
  19. Ohio
  20. Nevada
  21. Missouri

I spent about an hour writing a quick Java program to determine the result. Source code here: https://github.com/jakerobb/SEPuzzling-USStatesProblem

The program recursively tests every possible list, making sure that each permutation is valid before recursing further down that branch of the tree. It discovers every possible valid leaf (16,636,162 of them, from 1-length to the 21-item maximum), and keeps track of the longest one it has found as it goes.

On my computer (a decked-out late 2013 27" iMac with a 3.5-3.9GHz Haswell i7), it takes about 45 seconds to find the answer.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Can you prove it? What's the logical process that led you to this solution? $\endgroup$
    – leoll2
    Mar 18, 2015 at 19:58
  • 1
    $\begingroup$ I wrote a Java application that searches through all possible answers. It is about three hundred lines (counting whitespace, imports, everything), split across three classes, one of which is an enum with the fifty states. Do you want me to share the code? $\endgroup$
    – JakeRobb
    Mar 18, 2015 at 20:01
  • $\begingroup$ Yeah, the code would be appreciated. If you don't have enough room here, upload it somewhere and share the link. $\endgroup$
    – leoll2
    Mar 18, 2015 at 20:03
  • $\begingroup$ It's going on GitHub in the next few minutes. $\endgroup$
    – JakeRobb
    Mar 18, 2015 at 20:05
  • 1
    $\begingroup$ After it's done trying the entire chain of possibilities starting with A B C D, it will try A B C E all the way to A B C Z, then A B D * through to A B Z *, then A C *, then A D *, then A E *. It never inserts anything, but it does try every possibility. (this is a kinda weird way to describe it, since A-Z don't correlate directly to any state. It tries the states in alphabetical order, as defined in the State enum.) $\endgroup$
    – JakeRobb
    Mar 18, 2015 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.