12
$\begingroup$

The coach asks you take as many soccer balls as possible and put those balls onto the field with the condition that

For any arbitrary set of three balls, at least two of those balls are exactly 10 metres apart.

With this condition,

What is the maximum number of balls can you put into the field?

$\endgroup$
  • $\begingroup$ Do we know the size of the field? $\endgroup$ – boboquack Nov 10 '17 at 21:33
  • $\begingroup$ @boboquack large enough $\endgroup$ – Oray Nov 10 '17 at 21:34
  • $\begingroup$ Can the balls be placed on top of things such that they are held up in the air (say on top of a tall pole)? $\endgroup$ – ColdFrog Nov 10 '17 at 21:56
  • 1
    $\begingroup$ @ColdFrog it is 2D question, balls are not flying :) $\endgroup$ – Oray Nov 10 '17 at 21:58
12
$\begingroup$

You can get at least:

7

Take:

Two 60-120 rhombi with 10 metre sides, join them at a 60 degree tip and rotate one so that the opposite tips are 10 metres apart.

Like so (not to scale, lines indicate distances of 10m):

Drawing obviously not to scale

Then place a soccer ball at each vertex.

Why this works:

By the pigeonhole principle, two balls must be in the same rhombus. Now, if they were in the middle two vertices or adjacent to each other around the edge of that rhombus, they would be 10m apart. Otherwise, they must be at opposite tips, but then there is no place for the third ball.

EDIT: Nicer diagram from here:

Moser Spindle

EDIT 2: Pjotr5 has a near proof of optimality - kudos to them. Let's finish it off.

We will:

Try to construct a unit graph by going around the 8 vertices clockwise from the top-left vertex

Process:

ABC
ABCD
ABCDE

But then:

When we try to construct F, it must be one unit from D and one unit from E. However, they are two units apart and A is already halfway between them, so F and A would have to coincide. So we cannot construct a unit-distance graph with this graph either.

$\endgroup$
7
$\begingroup$

An approach to proving optimality (proof by computer)

Suppose we have a configuration of $n$ points $x_1, \dots, x_n$ that satisfies the condition stated in the problem. Then consider the complete graph $K_n$ on $n$ vertices with a two-coloring of the edges where we color an edge $(i,j)$ blue if the distance between them is the required distance (10 meter) and red if it isn't, call this graph together with its coloring $G$. According to the conditions of the problem, $G$ cannot contain a clique of size $3$ for which every edge has the color red. It is also an easy exercise to show that it is impossible to draw $4$ points in the plane such that they all have the same distance from each other. In terms of our graph $G$ this says that $G$ cannot contain a clique of size $4$ for which every edge has the color blue. These two conditions give an upper bound for the number of vertices that $G$ can have using Ramsey's theorem. Namely, the upper bound for $n$ is given by $n \leq R(4,3) -1$.

Unfortunately $$R(4,3)-1 = 8,$$ so this does not prove that the configuration given by boboquack is optimal, but it does show that it is at least close. Now we can turn to the computer to investigate if there are any possible configurations with $n=8$, suppose that $G$ is a graph belonging to such a configuration. On this page we can find that our graph $G$ must, up to isomorphism, be one of these three graphs (I have only drawn the blue edges): enter image description here

We are now essentially looking for a unit-distance drawing of one of these graphs. Or, in other words, we are looking to prove or disprove that any of these graphs are unit distance graphs. As is stated on that page, a unit distance graph cannot contain the complete bipartite subgraph $K_{2,3}$. This immediately excludes the first two of these three possibilities considering the following image.

enter image description here

So finally proving that the solution given by boboquack is indeed an optimal one boils down to proving/disproving that the following graph is a unit distance graph.

enter image description here

This can be turned into a purely algebraic problem for which the computer might be able to confirm that a solution does or does not exist.

We can give every vertex of this graph real coordinates $(x_i, y_i)$. Now we want to simultaneously solve all the equations $(x_i-x_j)^2 + (y_i - y_j)^2 = 1$ for all edges $(i,j)$. We can let Mathematica have a crack at this for this particular graph using the following input.enter image description hereAfter some consideration, the computer yields False, which means that Mathematica thinks that a solution does not exist. If we trust the software and the hardware involved this completes the proof and shows that $n=7$ is optimal.

I suspect that there are also more clever ways to show that this is actually not a unit distance graph, maybe a way that someone on this website would be able to provide.

$\endgroup$
  • 3
    $\begingroup$ Finished off your proof! $\endgroup$ – boboquack Nov 11 '17 at 22:38
  • $\begingroup$ @boboquack Well done! A good hands-on approach :) $\endgroup$ – Pjotr5 Nov 12 '17 at 9:26
6
$\begingroup$

Here is a 2D configuration which allows

6

balls:

Put four of them on the corners of a square with edge length of 10m. Than stand an equilateral triangle on two opposite edges, and put two balls to the third corner of those triangles.

Proof that there are always 2 balls 10m apart among any 3:

As there are only two non-square corner placed balls, at least one of the three has to be a corner of the square (by symmetry, we can assume it's the one marked with red on the image). That one has three balls which are exactly 10 m apart from it (the blue ones): one that shares a triangle-edge with it, one that shares a square-edge with it, and one that shares an edge which belongs both to the square and a triangle. If any of these three is among the chosen three, we are done. If not, it means, the other two balls chosen are the non-neighbouring two (the yellow ones), but those happen to be 10m apart from each other. an image is worth a thousand words

$\endgroup$
  • $\begingroup$ FYI: good explanation with a good graph but there is better answer. $\endgroup$ – Oray Nov 10 '17 at 22:31
  • 1
    $\begingroup$ You don't need the square - by pigeonhole principle two balls must be in the same triangle and therefore two of the balls are 10m apart. $\endgroup$ – boboquack Nov 10 '17 at 22:31
2
$\begingroup$

I first came across this problem when a variant was asked (SPOILER WARNING) in a Spanish national newspaper in 2011. That variant gives the answer,

7 points

and asks for the configuration. The following proof that there is a unique configuration also shows that it is indeed the maximum. I shall call two points "connected" if they are at the appropriate distance.

Lemma 1: there is no $K_4$ (group of four points all connected)

In other words, the graph of the points does not contain a subgroup like this:

K4

A connected shape like that is called a regular tetrahedron, and is not planar. Alternatively, if we take two of the points then the points which are connected with both of them are the intersections of the circles centred on the two and with suitable radius:

Two equilateral triangles, sharing a side

And it is easy to show that the distance between those two points of intersection is $\sqrt 3$ times too large.

Lemma 2: there is no $K_{3,2}$ (group of five points in which three are each connected to the remaining two)

In other words, the graph does not contain a subgraph like:

Square with one diagonal and points at the corner and centre

If it did, we would have three distinct intersections between two circles, which is not possible.

Lemma 3: each of the points is connected to at least three others, and at least one is connected to four or more

Suppose that there are $n$ points in the graph and point $P$ is connected to no more than $n - 5$. Then there are four points which are neither $P$ nor connected to $P$; but the triangle formed of $P$ and any two of those points must have one connected edge, and it doesn't include $P$; so those four points must form $K_4$ in violation of lemma 1.

If $n > 7$ then this shows that each point is connected to at least four others. If $n = 7$ then it shows that each point is connected to at least three others; but since $3 \times 7 = 21$ is odd and the number of half-edges must be even, at least one must be connected to four or more.

No point is connected to more than four others, and points which are connected to four others have one of two configurations

Let us choose one of the points with the highest order (number of edges) and call it $A$. It is connected to at least four points (lemma 3). Let us choose four of those points and call them $B,C,D,E$. What are the possible subgraphs induced by $\{B,C,D,E\}$? Up to isomorphism the possible graphs on four points are:

11 cases

of which we can eliminate I, II, III, and VI because they have triples with no edge; and XI immediately by lemma 1. Since all four points are connected to $A$ we can also eliminate VII, IX, and X by lemma 1. Case VIII is also impossible: observe the following diagram for case V, and see that it would require $B$ and $E$ to be connected, when they are at twice the required distance. The only possible cases are IV and V:

Case IV: two equilateral triangles joined at a vertex; case V: three equilateral triangles in a strip

Clearly in case V it is impossible for $A$ to be connected to a fifth point, $F$: if we consider the four points $B,C,D,F$ we see that they would have to form another case V, which puts $F$ opposite $D$ on the circle, and then $CEF$ has three points all at $\sqrt 3$ times the required distance.

In case IV it is also impossible for $A$ to be connected to a fifth point, $F$. If we consider the triple $BDF$ then $F$ must be connected either to $B$ or to $D$; without loss of generality we shall assume $B$, but then $BCEF$ must form a case V and we fall into the same trap.

Therefore $A$ is connected to precisely four other points.

There is a unique solution

Label the points which are not connected to $A$ starting at $F$.

Note that they form a complete graph, by the same argument as used for lemma 3, and therefore there are at most three of them. We assume that there are at least two, $F$ and $G$, and allow for the possibility that there is a third, $H$.

Note that none of these points can be connected to more than two of $BCDE$, by lemma 2 ($A$ and the higher labelled point being the part of size 2).

Consider case V. By lemma 3, $B$ must be connected to (without loss of generality) $F$. Then $F$ cannot be connected to $D$ (lemma 2, with $B$ and $D$ as the part of size 2) or to $E$ (since $A$ occupies the only point which is at the right distance from both $B$ and $E$). Then the triple $CEF$ forces $F$ to be connected to $C$, fixing the position of $F$ as extending the triangle strip. By similar reasoning, a different higher point $G$ must be connected to $D$ and $E$, extending the triangle strip. But then $F$ and $G$ are not connected, giving a contradiction. Thus we rule out case V, and are left only with case IV.

We have disconnected pairs $(B, D),\;(B, E),\;(C, D),\;(C, E)$: each higher labelled point must connect to an element from each pair.

Without loss of generality, let $F$ connect to $B$. Then it cannot connect to $D$ (since it must also connect to one of $C$ or $E$, and that would be three of $BCDE$), and similarly it cannot connect to $E$; it must connect to $C$. Similarly, $G$ must connect to $D$ and $E$. Now we cannot have an $H$, since it would also have to connect to $B$ and $C$ (in violation of lemma 2) or to $D$ and $E$ (likewise). Therefore we have only seven points, and their connectivity graph is

Moser spindle

The geometry of the equilateral triangles combined with the connection $FG$ also forces a unique embedding, up to affine transforms.

$\endgroup$
0
$\begingroup$

The problem relies in the arbitrary set rule. 2 out of 3 balls must be 10m from each other. Depends on how you read that.

But I take it to mean that for every set of 3 balls that are in the total set, 2 of those 3 must be 10m away.

So the answer would be 4. In a square where each side is 10m, you cannot select a set who doesn't meet those conditions. The size of the field doesn't matter so long as that it is larger than 10x10m

Wait! Edit!

Realize there's a way to do it better.

A hexagon where the distance of the two equilateral triangles that make it up are 10m sides. So 6, not 4.

$\endgroup$
  • 1
    $\begingroup$ We've already got 7, actually, but good job for getting 6! Tip for the future: maybe take a look at the other answers before posting. $\endgroup$ – boboquack Nov 11 '17 at 0:26

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.