Eight tiles are located on an $8\times 8$ board in such a way that no pair of them are in the same row or in the same column. Prove that, among the distances between each pair of tiles, we can find two of them that are equal (the distance between two tiles is the distance between the centers of the squares in which they are located).
Problem
Source: 2003 Peru Cono Sur TST P4
Tags: combinatorics
04.05.2023 04:28
Let us consider the distance between two adjacient center squares as $1$ and also say that $f(x,y)$ means $\sqrt{x^2+y^2}$. When considering the distance between a pair of centers, it can be written in terms of the vertical distance and the horizontal distance by pythagorean theorem as we denoted in the function above. As we are choosing $8$ points that are not in the same row or column, the horizontal distance and vertical distance between any two points must be at least $1$. When we count the total number of distinct distances between any two points, we get: \[f(1,1),\dots, f(7,7).\]However, some of these distances could be equal but there is at most $21$ distinct distances between any two center points. As we are choosing $8$ points, there are a total of $\binom{8}{2}=28$ pairs of distances between any two center points. This means that by the pigeon-hole principle, at least two of these pairs of distances must be the same.
15.12.2024 19:33
Sorry to reply on such an old post, but minor correction, there would be $27$ distinct values of $f(x, y)$ Since, $f(x, y)$ = $f(y, x)$, there would usually be a maximum of $n(n+1)/2$ distinct values, if $x$ and $y$ are chosen from $n$ different values. However, in this case, $f(1, 7) = f(7, 1) = f(5, 5)$, so the count of distinct values decreases further by one.