8
$\begingroup$

You are given the following map of US:

mainland USA

And the 48 US states without Alaska and Hawaii:

  1. Alabama
  2. Arizona
  3. Arkansas
  4. California
  5. Colorado
  6. Connecticut
  7. Delaware
  8. Florida
  9. Georgia
  10. Idaho
  11. Illinois
  12. Indiana
  13. Iowa
  14. Kansas
  15. Kentucky
  16. Louisiana
  17. Maine
  18. Maryland
  19. Massachusetts
  20. Michigan
  21. Minnesota
  22. Mississippi
  23. Missouri
  24. Montana
  25. Nebraska
  26. Nevada
  27. New Hampshire
  28. New Jersey
  29. New Mexico
  30. New York
  31. North Carolina
  32. North Dakota
  33. Ohio
  34. Oklahoma
  35. Oregon
  36. Pennsylvania
  37. Rhode Island
  38. South Carolina
  39. South Dakota
  40. Tennessee
  41. Texas
  42. Utah
  43. Vermont
  44. Virginia
  45. Washington
  46. West Virginia
  47. Wisconsin
  48. Wyoming

Using the above map, you must place circular lines (without width) such that all 48 states have exactly one circle on it. It is fine if the same circle leaves and reenters the same state.

How many circles do you need at minimum? A trivial non-optimized answer is 48 circles, one per state! However, you can use one circle to touch Washington, Oregon, California and more.

This puzzle was inspired by All Europe Countries Segmented

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ For those who aren't familiar with U.S. geography, it would be helpful to have the states colour-coded, or otherwise distinguishable. I count 50 different regions on the map above. I assume that in two cases, two of those regions are part of the same state, but I have no idea which ones. $\endgroup$ Commented yesterday
  • $\begingroup$ (actually 51 regions, but I did manage to recognize the shape of Maryland, and inferred that it is actually one region, but looks like two due to the thickness of the border lines on the provided map) $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ Are we to use plane circles on this particular projection (which projection?), or actual circles on the real geoid? $\endgroup$ Commented 20 hours ago

3 Answers 3

Reset to default
13
$\begingroup$

4 circles!

Step 1: find "all" 100,000+ sets of states that a circle can touch (convolution makes this fast enough)
Step 2: solve exact cover problem (meet-in-the-middle)

My code found ~500 solutions, and it was fun to browse through them. See some of them below.

Find the phony!

enter image description here
enter image description here
enter image description here
enter image description here
enter image description here
enter image description here
enter image description here
enter image description here
enter image description here
enter image description here
enter image description here
enter image description here
enter image description here

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ I guess the "phony" is reveal spoiler number 6 of those, where reveal spoilerthe purple circle claims to pass exactly between two of the orange areas. $\endgroup$ Commented 20 hours ago
  • $\begingroup$ And #5 is dodgy too, with Montana cut by 2 circles, and Florida's border has not been crossed. I think a single good map would be better than an array of dubious ones. Please don't leave it to readers to filter them. Which one is your solution? $\endgroup$ Commented 19 hours ago
  • $\begingroup$ Another phony is #8 because of the alternating two-coloring of the Four Corners states. $\endgroup$ Commented 14 hours ago
  • $\begingroup$ What is the minimum if each circle must cover a contiguous region? $\endgroup$ Commented 14 hours ago
  • $\begingroup$ @RobPratt do you mean that states must share a land border that is not a point? $\endgroup$ Commented 13 hours ago
10
$\begingroup$

Here is the answer with

6 circles.

as trial and error:

enter image description here

I wrote a code to find a better option and I got

5

as below graph

enter image description here

another solution:

enter image description here

I believe this is optimal.

Note: My code works by generating tens of thousands of imaginary circles of all different sizes across the map to see which states they touch, and then it uses a Constraint Programming solver to pick the absolute smallest handful of those circles that perfectly touches every state exactly one time.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I wonder if you can get Alaska and/or Hawaii in there too... the left-most circle sure seems to be going off in the right direction. $\endgroup$ Commented yesterday
  • $\begingroup$ @Carmeister I believe it is possible. $\endgroup$ Commented 20 hours ago
0
$\begingroup$

I have done it with 6 circles. I don't know if that is minimal.

enter image description here

Improve this answer
$\endgroup$
2
  • 9
    $\begingroup$ What about Ohio ('two states' above circle 7)? $\endgroup$ Commented yesterday
  • 8
    $\begingroup$ Also Wisconsin (in the interior of circle 10). $\endgroup$ Commented yesterday

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.