Prove that when dividing a square field among three people, one person must own two points more than 1 km apart

We have a square field with a $1$ km side we need to divide among three people (it doesn't have to be fair, one of them could even get none of it!). How would I prove that at least one of the persons owns two points distant by strictly more than $1$ km ?

The way the square is divided doesn't have any special restriction (for instance, it would even be : all the points with rational distance from the upper left corner goes to the 1st person etc etc)


If someone doesn't have anything, then it's obvious (it would mean that the two others would both have two corners on a side, and by drawing two circles for each we would see that some of the area would not be given to anyone.)

If one of the persons has 3+ corners, it's obvious. Let's suppose one of the persons has at exactly two corners. We can also show easily that if the two other corners belong to the same person, the problem becomes obvious. ($\rightarrow$ we'd just need to draw the circles from the case where one of the persons has no area at all, and then give the area not in the circles to that person. It then becomes obvious that person would own segments on opposite sides, which would imply there are two points verifying the requirement.)

How would I solve it when one person has two corners, and the two others each have one corner ?


Solution 1:

Assume for the sake of contradiction that it is possible to allocate land such that any two points of one person's land lie no more than $1$ km apart.

As you noted one person, say person orange, must have 2 adjacent corners. The maximum amount of land they can then have in addition to those two corners is outlined below (it is governed by the circles of radius 1 centered at the corners).

The other two people, person purple and person green, must then also get the same two corners because for any $\epsilon>0$ there exists an unclaimed piece of land within $\epsilon$ of those corners. The maximum amount of land person purple and person green may have given these constraints is also shown below (again governed by circles of radius 1 centered at the corners).

This leaves the black region impossible to claim. Hence we have the desired contradiction.

Economical Land Grabbing

Solution 2:

WOLOG, say one person has $(0,0), (0,1)$, another has $(1,0)$, and the third has $(1,1)$. Then the person who has $(1,0)$ has the whole left side except the base point and the person who has $(1,1)$ has the whole right side except the base point. Now who gets $(1/2,1)$?