7
$\begingroup$

Consider 2 countries, A,B that have discovered a new planet, the size of Earth.

They have decided to split the planet into regions of minimum area $10^3 m^2$ and maximum area $10^5 m^2$, with borders that are not self-intersecting and further the region shouldn’t be split into multiple parts that are separated. They can claim a region of requested shape and area anywhere on the planet as long as it doesn’t overlap with any other region previously claimed. They further alternate in picking regions. They decide A goes first. Then B, then A and so on (alternating picks). The entire planet is claimable and the planet can be assumed to be a perfect sphere.

Further, there is provision to reward the better strategist: whoever places the last region, gets the other country’s smallest region as a reward. Which country will get more land? Explain clearly why and how.


It's unclear what the objective of the countries is. You can assume what you think is reasonable. Some possibilities:

  1. They want to maximize their claimed area first and second, to claim more area than the opponent.
  2. They want to maximize their area first, and minimize the area of the opponent second.
  3. To claim more area than the opponent.

Bonus: Is it possible to calculate (or $\epsilon$-approximate) the total final area of each country? If so, what is it?


Edit: Changed from Original Description that asked for a contiguous border.

$\endgroup$
3
  • 2
    $\begingroup$ Is this new planet 100% claimable land, or are there sections of the surface that cannot be claimed like oceans? $\endgroup$ Oct 17, 2022 at 8:29
  • 1
    $\begingroup$ Does one country tries to maximize the surface it gets or the difference between its surface and the one its concurrent gains ? In another word, does A prefer to have 1000m² even if B gets 2000m², or to have 500m² and B 100m² ? $\endgroup$
    – Evargalo
    Oct 17, 2022 at 11:51
  • $\begingroup$ Added some clarifications $\endgroup$
    – Cris
    Oct 17, 2022 at 13:53

3 Answers 3

9
$\begingroup$

I'm presuming here that each player's primary goal is to win (i.e. claim, or otherwise be rewarded with) as much land as possible, and that a secondary, tie-breaking goal is to minimize the amount of land won by the other player. I'm also assuming that by "contiguous border" you mean that each region must be defined by a single and non-self-intersecting contour, which means that in addition to each region being contiguous, donut-shaped regions are not allowed. (One couldn't construct a donut-shaped region by extending a C-shaped region until its points touched, as the shared border point would then not be a "border" at all.)

Observe that the first region is limited in a way that no later region is limited: It cannot separate the unclaimed land into multiple contiguous areas, because of the contiguous border condition. WLOG, assume that this first region is a circular-ish blob.

In contrast, B's first region can split the remaining unclaimed land into as many distinct areas as B likes. An example region would be a star-shaped region, whose center is the antipode to the first placed regions, and all of whose outer points reach around the globe to touch the first region. An N-pointed star will split the remaining area into N regions. N can then be chosen such that all regions are below $10^3 m^2$.

If B chose to do this, they would get A's first region (as a reward), and their own; the remainder of the world would presumably become an exceedingly annoying set of fantastically long and thin wildlife preserves. This would be the optimal strategy if the players' primary and secondary objectives were reversed.

B's other, friendlier option is to pick N such that the unclaimed areas are between $10^3 m^2$ and $(2*10^3 - \epsilon) m^2$. Once that happens, A and B alternate picking these areas until they run out; at that point who got the bonus region would depend on whether that number was odd or even. (If B were to make one of those regions larger than twice the minimum, it would give A extra flexibility to flip the odd/even.) Of course, B picks an even N, and subject to that condition makes the areas as large as possible (since B will end up with two more of them than A.)

So the final area is pretty close between the two; B is ahead of A by nearly $3*10^3 m^2$. (A chose to spite B by taking only the minimum size area once, making that the smallest region that B wins. There's a similar size unclaimed area.)

Incidentally,

Most of the regions of the globe will be about a millimeter wide on average, and nearly 20,000 km long. If you're looking to move there, maybe pick one of the first regions.

Edit to incorporate the OP's clarifications:

The elaborated description of "contiguous" appears to allow for enclaves (regions fully enclosing other regions, or fully enclosing unclaimed areas). In this case, the initiative (and the advantage) belongs to player A, who can create a swiss-cheese first region with unclaimed holes slightly less than twice the minimum region area. The reasoning proceeds as before but with roles reversed, except that B doesn't get to place a "big region" and A ends up with $10^5 + 3*10^3$ more land than B.

$\endgroup$
0
3
$\begingroup$

I will assume that the whole surface of the planet is claimable.

One possible answer is that

country B essentially gains sole access to the planet by shutting out country A completely. Officially B will only have a total claim of about $2\cdot 10^5\ m^2$.

Strategy:

Country A makes the first move and claims some area, presumably as large as is allowed. Country B can now claim a complicated tentacled shape that splits all remaining unclaimed land into small regions smaller than the minimal claimable amount. Country A cannot make a second claim, and B then gains A's smallest and only region too, leaving A with nothing.
Here's how B can determine the shape of their claim. Suppose B were to claim a small region on the opposite side of the planet to A's claim. The unclaimed area is then topologically the same as the surface of a cylinder, a kind of ring. Slice that surface up into strips that run from A's regions to B's initial region, alternating between a strip of $999\ m^2$ area that remains unclaimed, and an arbitrarily thin strip that B will add to its current claim. These strips can be thin enough to keep B's total claim area smaller than $10^5\ m^2$. The unclaimed strips border A's region, so are not fully surrounded by B.

$\endgroup$
4
  • $\begingroup$ Why couldn't country A apply the very same strategy B uses in this answer for the first piece of land they claim ? $\endgroup$
    – Evargalo
    Oct 17, 2022 at 11:48
  • 2
    $\begingroup$ @Evargalo Because the first region cannot separate the remaining area into multiple parts. $\endgroup$
    – Sneftel
    Oct 17, 2022 at 11:49
  • $\begingroup$ @Sneftel : I am unsure whether leaving unclaimed enclaves within a claimed area is allowed... If yes, then it is possible. $\endgroup$
    – Evargalo
    Oct 17, 2022 at 11:56
  • $\begingroup$ @Evargalo As I read it, the "contiguous border" condition rules out enclaves. (Unintentionally, I think, but there you go.) $\endgroup$
    – Sneftel
    Oct 17, 2022 at 11:56
1
$\begingroup$

Here's my attempt for this problem.

Consider the objective of maximizing the area first and secondarily winning

The first country can place a sufficiently narrow ring that goes around the planet, around the equator. As a result, the planet is split into two symmetrical sections.

Now any region player B places, country A can mirror this region in the opposite part of the planet, i.e. the symmetrical w.r.t. either the center of the planet, or w.r.t the ring. enter image description here

As a result, country A always has a response to B. B can therefore B deduce that whatever it does, A will be able to get a region from them. So B needs to try to have at least a region of minimum area (so that what A takes is as little as possible).

Further, B, given the above, needs to get as much of the remaining area possible. However B is aware that A will be able to get at least as much area as B can get, in the remaining time. Therefore B can focus on getting 50% of the remaining area.

At this point, I make an assumption that A cannot do anything better than 50% of the remaining planet after the planet is being split and B is the first to pick. So A can compromise for 50%.

B after having calculated that it can do at most 50% of the remaining planet, and so can A, he proceeds by covering the northern sector of the planet through rings, and A can respond with the symmetric ring on the southern of the planet. This is a tiling problem in effect which the two countries need to perform.

B can always choose appropriately the area between 10^3 and 10^5 m^2 such that, it perfectly covers the entire remaining upper planet (it can be calculated by solving a simple equation).

Therefore A gets the area of the initial ring the lower half of the planet plus a bonus area of necessarily $10^3 m^2$. B gets the upper part of the planet minus that one area. enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ I was almost going to give this answer, except incorrectly reversed because I overlooked the first step. Anyway, while this demonstrates who wins, is it possible that they could win by a bigger margin by following a different strategy (even if the other one also chooses optimally)? $\endgroup$
    – Ed Murphy
    Oct 20, 2022 at 4:46

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.