19
$\begingroup$

The question:

$8$ ants are placed on the edges of the unit cube. Prove that there exists a pair of ants at a distance not exceeding $1$.

My Idea 1:

I was trying to find out how the ants will have to be placed so that we can do some logic building to show that there is a pair of ants not exceeding distance 1.

My Idea 2:

The sum of distances between two ants is greater than ie. $\binom82$. If this is disproven then we are done as if less than $\binom82$ then there has to be one which is not exceeding 1.

I am more towards idea 2 thanks for any help...

Thank you so much

Edit: maybe we can use the min of the distances which one ant is connected to and then prove it with 8.

Edit: I forgot to mention the source... II Caucasus Mathematical Olympiad. I was solving the past year problems and found this wonderful question.

$\endgroup$
1
  • $\begingroup$ It's starting to look like for $d$ dimension unit cube (line, square, cube ...) and $2^d$ points on edges, there'll always be $2$ with distance at most $1$ ? $\endgroup$ Commented Oct 26, 2024 at 9:38

2 Answers 2

Reset to default
58
$\begingroup$

The number 8 in the question makes me immediately think: what does a cube have 8 of? 6 faces, 12 edges — but 8 vertices. So is there some way to associate the 8 ants with the 8 vertices that might help?

Well, we can assign each ant to its nearest vertex. What now? Each ant must be at most distance $\frac{1}{2}$ from its nearest vertex — so if two ants have the same nearest vertex, then they’re $\leq 1$ from each other crawling along the edges, so certainly $\leq 1$ in absolute distance (as the woodworm bores). What about if each ant has a different nearest vertex? Then every vertex has some assigned ant. Now take the ant that’s furthest from its assigned vertex — call that ant Anthony, and call his distance from his vertex $a$. Then Anthony is $1-a$ from the other end of his edge; but that vertex has an ant of its own, at distance $\leq a$ (since Anthony was the furthest-from-his-own-vertex); so the distance between these two ants is $\leq (1-a) + a = 1$ along edges, and so again, $\leq 1$ as the woodworm bores.

$\endgroup$
0
26
$\begingroup$

If there are any two ants on the same closed edge of the cube, then the distance of those two ants is at most one, so we are done. Otherwise, the ants are arranged so no two ants are on the same edge.

Thinking of the cube as an abstract graph (with eight vertices and twelve edges), consider this subgraph. An edge is included in the subgraph if and only if there is an ant on that closed edge of the cube. Since any closed edge contains at most one ant, there are at least eight edges in this subgraph. Therefore, the subgraph has a cycle.

Say the cycle has $c$ edges. Ignoring the rest of cube, this cycle is a rectilinear loop of length $c$. There are $c$ ants on this loop, dividing the loop into $c$ sections. The shortest section has length at most one. But then the two ants at the ends of the shortest section are also at distance at most one, because Euclidean distance is dominated by rectilinear distance.

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.