5
$\begingroup$

You are given the next map where many flags are shown on their corresponding countries.

enter image description here

Construct a forest of maximal weight such that:

  • There exist at most one edge between two flags if and only if the associated countries share at least one border. For instance, France and Belgium could be linked. Island must be a single node tree because it does not share any border.
  • The weight of any edge is the sum of the number of colors on the two flags. France's flag has 3 colors and Belgium's flag also has 3 colors, which means that linking France to Belgium will weight 6 in the objective.

To help you more: Portugal has 6 colors on its flag and Spain 2, you must link the two countries in a maximal solution and the associated edge will weight 6+2=8 in the objective!

To help you even more

As a starting point and to illustrate the requirements here is an obviously non-optimal solution of value 115. You can optimize it in GeoGebra here.

enter image description here

European Countries and Number of Different Colors in Their Flags (please discard any unnecessary occurrence or add one if necessary)

  1. Albania – 2 colors (red, black)
  2. Andorra – 4 colors (blue, yellow, red, white)
  3. Armenia – 3 colors (red, blue, orange)
  4. Austria – 2 colors (red, white)
  5. Azerbaijan – 4 colors (blue, red, green, white)
  6. Belarus – 4 colors (red, green, white, pink pattern)
  7. Belgium – 3 colors (black, yellow, red)
  8. Bosnia and Herzegovina – 3 colors (blue, yellow, white)
  9. Bulgaria – 3 colors (white, green, red)
  10. Croatia – 5 colors (red, white, blue, black, yellow)
  11. Cyprus – 3 colors (white, copper-orange, green)
  12. Czech Republic – 3 colors (white, red, blue)
  13. Denmark – 2 colors (red, white)
  14. Estonia – 3 colors (blue, black, white)
  15. Finland – 2 colors (white, blue)
  16. France – 3 colors (blue, white, red)
  17. Georgia – 2 colors (white, red)
  18. Germany – 3 colors (black, red, yellow)
  19. Greece – 2 colors (blue, white)
  20. Hungary – 3 colors (red, white, green)
  21. Iceland – 3 colors (blue, white, red)
  22. Ireland – 3 colors (green, white, orange)
  23. Italy – 3 colors (green, white, red)
  24. Kazakhstan (partly in Europe) – 2 colors (sky blue, gold)
  25. Kosovo – 3 colors (blue, yellow, white)
  26. Latvia – 2 colors (red, white)
  27. Liechtenstein – 3 colors (blue, red, yellow)
  28. Lithuania – 3 colors (yellow, green, red)
  29. Luxembourg – 3 colors (red, white, light blue)
  30. Malta – 3 colors (white, red, gray/silver for cross)
  31. Moldova – 4 colors (blue, yellow, red, brown/gold for emblem)
  32. Monaco – 2 colors (red, white)
  33. Montenegro – 4 colors (red, gold/yellow, blue, white)
  34. Netherlands – 3 colors (red, white, blue)
  35. North Macedonia – 2 colors (red, yellow)
  36. Norway – 3 colors (red, white, blue)
  37. Poland – 2 colors (white, red)
  38. Portugal – 4 colors (green, red, yellow, white)
  39. Romania – 3 colors (blue, yellow, red)
  40. Russia – 3 colors (white, blue, red)
  41. San Marino – 3 colors (white, light blue, yellow/gold)
  42. Serbia – 4 colors (red, blue, white, yellow/gold)
  43. Slovakia – 4 colors (white, blue, red, yellow)
  44. Slovenia – 4 colors (white, blue, red, yellow)
  45. Spain – 3 colors (red, yellow, white)
  46. Sweden – 2 colors (blue, yellow)
  47. Switzerland – 2 colors (red, white)
  48. Turkey – 2 colors (red, white)
  49. Ukraine – 2 colors (blue, yellow)
  50. United Kingdom – 3 colors (red, white, blue)
  51. Vatican City – 2 colors (yellow, white)
Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Just to make sure I understand the question, isn’t this just an application of Kruskal’s algorithm for finding the maximum spanning tree given a weighted graph? $\endgroup$ Commented Jul 1, 2025 at 14:18

1 Answer 1

Reset to default
6
$\begingroup$

Working in from the edges, focusing on countries or groups of countries enclosed by just one or two countries and making maximum use of higher-weighted countries, it's pretty straightforward to reach this point:

enter image description here

Continuing to work inward from the north and south and make maximum use of Croatia, I get this for a total value of, if my count is correct, 292:

enter image description here

I don't believe this can be improved on but there are obviously many different ways it can be connected up.

N.B. The OP's description includes Kosovo, but the map provided excludes it; this answer is based on the map and therefore excludes Kosovo. If necessary, Kosovo can be connected to Serbia with no further alterations, bringing the total to 299.

P.S. Gibraltar is a dependency of the UK, not legally part of it, therefore the UK does not have a border with Spain. If we do count the Gibraltar-Spain border, we can connect the UK to Spain for another 6 points, and by the same logic connect the UK to Cyprus through Akrotiri for another 3.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Don't forget that the UK shares a land border with Spain via Gibraltar. And Cyprus, which I just learned studying Google Maps. Cyprus also borders Turkey if we count disputed borders, but that doesn't change anything since UK has a more valuable flag. $\endgroup$ Commented Jul 1, 2025 at 14:14
  • $\begingroup$ @Bearmarshal Gibraltar isn't part of the UK, it's a British Overseas Territory (dependency). This is a different legal status, not equivalent to territories like Hawaii or French Guiana which are located distantly but are an integral part of the sovereign country. The UK doesn't share a border with Cyprus for the same reason. Cyprus doesn't border Turkey in any case, Northern Cyprus claims full independence, so if we recognize it we simply add another flag worth 2 points. $\endgroup$ Commented Jul 1, 2025 at 14:22
  • $\begingroup$ Ah, thanks, I stand corrected! $\endgroup$ Commented Jul 1, 2025 at 14:25
  • 1
    $\begingroup$ @Bearmarshal it's definitely worth a P.S., thanks for bringing it up :-) $\endgroup$ Commented Jul 1, 2025 at 14:28

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.