10
$\begingroup$

Here is an (unoriginal) question which I found quite nice. I've got no idea where the original question came from.

Given 6 points in a $3\times4$ rectangle, prove that two lie within $\sqrt{5}$ of each other.

This might help: Pigeonhole Principle

Edit: Although this has been solved, there is a nicer 'proof without words' solution which is still out there : )

$\endgroup$
  • 2
    $\begingroup$ Related. $\endgroup$ – Ankoganit May 16 '17 at 9:03
  • $\begingroup$ Oh, sorry. I wasn't aware that the problem had been posted already. $\endgroup$ – Wen1now May 16 '17 at 9:19
7
$\begingroup$

Assume for contradiction that the points are each more than $\sqrt 5$ away from each other crow-flies. Divide the rectangle into twelve unit squares. We can't have two points in (or on the border of) the same square (it has a diagonal of $\sqrt 2$ and they can't be further apart than opposite ends of the diagonal), nor in orthogonally adjacent squares (as the 2×1 domino that forms them has a diagonal of $\sqrt 5$). Thus, they must be placed in a checkerboard pattern, with each point in/on the border of exactly one square, and all those squares being the same colour when checkerboard shading is used. Without loss of generality (that is, we can choose the coordinate system such that) the points are on a1, a3, b2, b4, c1, c3.

Consider the point on b2, and take the square in {a1, a3, c1, c3} whose centre is closest to that point. The b2 point can't be more than one unit in each orthogonal direction away from the centre of the square (or else it would be closer to a different square in that set). This means that it can't be more than $1{1\over2}$ units in each orthogonal direction away from the most distant point within that square. This means it has a total crow-flies distance of $\sqrt{2 \times ({3\over2})^2} = \sqrt{2 \times {9\over4}} = \sqrt{9\over2}=\sqrt{4{1\over2}}$ away from that point, contradicting our assumption that the points are each at least $\sqrt 5$ away from each other.

Incidentally, this reasoning strongly implies that the true maximum spacing between 6 points in a 3×4 rectangle is less than $\sqrt{5}$, but doesn't itself deduce what that spacing is. That might make for an interesting follow-up puzzle.

$\endgroup$
  • $\begingroup$ I believe the true maximum is $\frac{\sqrt{336}}{6}-1$ from an intuitive argument (put four points in the corners, then try to minimise the distances). But maybe my maths is wrong. $\endgroup$ – Wen1now May 16 '17 at 1:41
6
$\begingroup$

The puzzle’s poser suggested a proof without words.

Here, in any case, is a proof without further prose, as the diagram contains some words and this sentence ends with a link to a 3-cornered shape whose interior points are all within a maximum distance of each other.


Note that 5 circles can’t quite fill the bill.

$\endgroup$

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.