14

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 ?

Caleb Stanford
  • 45,895
Hippalectryon
  • 7,730

3 Answers3

25

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

Peter Woolfitt
  • 21,114
  • 1
    I get the point graphically, but how would i make a real proof ? – Hippalectryon May 22 '14 at 22:33
  • This is actually a real proof. In essence one person must have two corners, but because that person can't get some of the points very very near those corners, the other two people also have to get the same corners, which leaves a particular region impossible to get. – Peter Woolfitt May 22 '14 at 22:38
  • 12
    A person owning both $(0,0)$ and $(1,0)$ cannot own $(1,\epsilon)$ and cannot own $(0,2\epsilon)$, nor can a second person own these two points, hence each of the three persons owns one of these four points. The point $(\frac12,1)$ is too far from each of these four points (provided $\epsilon$ is small enough) – Hagen von Eitzen May 22 '14 at 22:42
  • @HagenvonEitzen Elegantly done! – Peter Woolfitt May 22 '14 at 22:47
1

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)$?

Ross Millikan
  • 374,822
  • 'the person who has (1,0) has the whole left side except ...' isn't that just a special example ? I need a general proof – Hippalectryon May 22 '14 at 22:25
  • No, because neither of the others can own it. All of that side is more than 1 km from both $(0,1)$ and $(1,1)$ Peter Woolfitt has a nice diagram-turn it upside down for my coordinates. – Ross Millikan May 22 '14 at 22:26
  • Could you make a figure ? I think the problem comes from the fact that we didn't set up the coordinates the same way – Hippalectryon May 22 '14 at 22:28
  • If you turn Peter Woolfitt's diagram upside down you have my argument. Because orange and green have points on the right, purple has to own the whole left. Similarly, green has to own the whole right. My point of failure is the center of the side that is black. – Ross Millikan May 22 '14 at 22:31
  • Oh okay I see. My coordinates system was different, that's why I didn't understand :) – Hippalectryon May 22 '14 at 22:32
  • There may be LOG: you could have one person with $(0,0)$ and $(0,1)$ and a second person with $(1,0)$ and $(1,1)$. In that case a problem could be that $(\frac13,0)$ and $(\frac23,1)$ would be too far apart to both be covered by the third person. – Henry May 23 '14 at 09:57
  • @Henry: In the original question OP only asked about the case with the corners 2-1-1. My WOLOG was distributing them. Your example is a good one for the 2+2 case. – Ross Millikan May 23 '14 at 14:20
1

Suppose not, so that we have a partition of the square into 3 sets $P_a,P_b,P_c$. We know the 4 corners are assigned somehow to the 3 people (person $a,b$ and $c$) so someone has at least 2 corners which must be adjacent, since the diagonal is length $\sqrt{2}$. We end up (WLOG by symmetry and since no one can have 3 vertices) with vertices labelled in clockwise order $a,a,b,c$. Draw in the biggest region possible to assign to person $a$ (the intersection of the discs of radius 1 about the two $a$ vertices with the square). The rest of the square must be assigned to person $b$ and $c$. Person $b$ has all points in a small neighborhood of its adjacent $a$ vertex since these points are further than 1 away from vertex $c$. Similarly for the adjacent $a$ vertex to $c$ and points assigned to $c$. Then the largest regions assignable to $b$ (similarly $c$) are contained in the intersections of the discs about $b$ and its adjacent vertex $a$ (similarly $c$ and its adjacent vertex a). But now look at the union of the largest possible region for $a$,$b$, and $c$, and it does not cover the whole square. Contradiction.

Ryan Vitale
  • 1,890