2
$\begingroup$

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?

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

2 Answers 2

Reset to default
4
$\begingroup$

The answer is

9

One way to do this is:

solution

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

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

sidenote:

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ Why is it impossible? $\endgroup$
    – algebra1
    Dec 13, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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.