The Big and the Small Kingdom are both rectangular islands and divided into rectangular landscape. In each province there is a road that runs along one of the diagonals. On each island exist roads that make a closed route, which does not go through any point several times. The picture shows the Little Kingdom, which has six area:

enter image description here

The Great Kingdom has an odd number of landscapes. How many landscapes does the Great Empire have at least?

  • $\begingroup$ I'm guessing you're using kingdom and empire as being the same thing? $\endgroup$ – DrunkWolf Dec 13 '15 at 13:28
  • $\begingroup$ Are "landscape" and "province" and "area" the same thing? Are "Big" and "Great" the same thing? $\endgroup$ – Kevin Dec 14 '15 at 17:11

The answer is


One way to do this is:


  • 1
    $\begingroup$ Can you prove that there are no solutions for islands with 1, 3, 5, or 7 provinces? $\endgroup$ – Kevin Dec 15 '15 at 15:07

The answer is

5, in case it's ok to not go through all squares.

In the general case

We note that you can't possible have a path with less then 4 squares.

In the case where we don't have to go through all squares

5 is the lowest odd number higher then 4, so if we can find a solution, we have proof that this is the optimal solution. Luckily such a solution is easily found
enter image description here


Just because the Big kingdom has less landscapes then the Small kingdom doesn't mean they're smaller.

  • $\begingroup$ Why is it impossible? $\endgroup$ – algebra1 Dec 13 '15 at 21:04
  • $\begingroup$ Let's not waste time on that. It is possible for odd numbers, the question is pointed at "what is the smallest [...]" which indicates that it does exist a solution. I can post one later if you want. $\endgroup$ – algebra1 Dec 13 '15 at 21:14
  • $\begingroup$ @algebra1 i'd like to see that to be honest, love to be wrong :) That said, i did provide a solution for the question you had. $\endgroup$ – DrunkWolf Dec 13 '15 at 21:17
  • $\begingroup$ Love your solution too, only it is not a correct one. In the text it says that every landscape has a road within it. I'll post a picture of a solution. $\endgroup$ – algebra1 Dec 13 '15 at 21:20
  • $\begingroup$ @algebra1 it is correct as written, sure you say each landscape has a road, but you only ask for a closed road, not one that uses all subroads $\endgroup$ – DrunkWolf Dec 13 '15 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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