Show that there exists a finite set $A \subset \mathbb{R}^2$ such that for every $X \in A$ there are points $Y_1, Y_2, \ldots, Y_{1993}$ in $A$ such that the distance between $X$ and $Y_i$ is equal to 1, for every $i.$
Problem
Source: IMO Shortlist 1993, Brasil 1
Tags: algebra, geometry, point set, distance, combinatorial geometry, IMO Shortlist
15.03.2006 13:43
Take $\omega$ to a primitive $p$th root of unity where $p$ is a prime. Then consider the set $A=\{e_0\omega^0+e_1\omega^1+\ldots+e_{p-2}\omega^{p-2}|e_1,\ldots,e_{p-2}\in\{0,1\}\}$. Then it is clear that $A$ has exactly $2^{p-1}$ members because the minimal polynomial of $\omega$ has degree $p-1$. Now we show that for every $x\in A$ we have at least $p-1$ points with distant one from $x$. Say $x=e_0\omega^0+e_1\omega^1+\ldots+e_{p-2}\omega^{p-2}$ then take $y_i$ to be \[ y_i: =e_0\omega^0+e_1\omega^1+\ldots+e_{i-1}\omega^{i-1}+(1-e_i)\omega^i+e_{i+1}\omega^{i+1}+\ldots+e_{p-2}\omega^{p-2} \] then for each $i$ we have $x-y_i=\omega^i$ or $x-y_i=-\omega^i$ which says their distance is $1$. For our problem just take $p$ to be greater than $1994$.
07.07.2006 20:36
I think we can construct this set inductively. For a set for which every point have two distances of 1 for each vertex we can take an equilateral triangle. Now assume that we have constructed a set with n distances of 1 for every vertex and consider a translatation of it by a vector of length 1 s.t. the two sets does not overlap. The set together with itself translatated by a vector of length 1 have n+1 distances of 1 fr every vertex. The induction is thus complete.
30.08.2009 01:47
A rational lattice point is a point with rational coordinates. There are infinitely many rational lattice point on the unit circle. Take 8000 of them, distributed symmetrically amongst each quadrant and across the lines y=x and y=-x. Now consider a common rational divisor of the difference between the x coordinates of any two of the 8000 points, and make a lattice centered at (0,0) whose unit length is this, spanning the square with vertices (1,1) (1,-1) (-1,1) (-1,-1).
26.04.2023 01:03
Pick an integer $r$ such that the circle \[ x^2 + y^2 = r^2 \]has at least $4 \cdot 1993$ integer solutions. Then choose the set of points of the form $(\frac mr, \frac nr)$ where $-r \le m \le r$ and $-r \le n \le r$ for integers $m$ and $n$. This works.
29.11.2023 03:17
Start with a set $A_0$ which contains a single point, and let $V$ denote the set of unit length vectors on the plane. We will inductively construct the set $A_n$ in the following manner. Take the set $A_{n-1}$ and translate it by some vector $v \in V$ so that no point is mapped to a point in $A_{n-1}$. Such a vector $v$ exists because given any pair of points in $A_{n-1}$ there is at most one element of $V$ which maps one to the other. So, there are at most $\binom{n-1}{2}$ vectors in $V$ that can't be used. Much smaller than the uncountable set $S$. Now consider the graph $G_n$ on vertex set $A_n$ such that if two points in $A_n$ are unit distance, they share an edge. It is not difficult to see that $G_n$ is isomorphic to the $n$'th hypercube graph (or has the $n$'th hypercube graph as a subgraph). Thus, $G_{1993}$ has all vertices of degree at least $1993$ as desired.
29.11.2023 23:32
We claim that a sufficiently large lattice grid with a suitable side length works. Claim: For any positive integer $n$, there exists a positive integer that can be written as a sum of two squares in at least $n$ ways. Proof: Consider $n$ Pythagorean triples with $a^2+b^2=c^2$. We know that the parametrization of primitive Pythagorean triples is $a=m^2-n^2$, $b=2mn$, and $c=m^2+n^2$. Note that any $1\pmod{4}$ prime can be written as the sum of two squares. Since these squares are distinct and nonzero, we can get nonzero values of $a$ and $b$ to form a valid Pythagorean triple whenever $c$ is a 1 mod 4 prime. Thus, let $N$ be the square of the product of the first $n$ primes that are 1 mod 4. For each solution to $a^2+b^2=p^2$ where $p$ is a 1 mod 4 prime dividing $N$, we can scale up by some factor to see that $N$ has a sum of squares representation. Moreover, since all of these are primitive triples, all of these $n$ representations will be distinct, hence proven. Now, back to the main problem. Let $N$ be a positive integer that has at least $1993$ representations as the sum of two squares. Consider a lattice grid with side length $100N$ and distance between adjacent vertices of $\frac{1}{\sqrt{N}}.$ Given any point in the lattice, there exists a lattice square within the whole lattice of side length at least $N$ that contains that point as one of its four corners. Then, WLOG it is the bottom left corner, and the original point was $(x,y)$. If $\Delta x$ and $\Delta y$ are nonnegative integers such that $\Delta x^2+\Delta y^2=N$, then the distance between $(x,y)$ and $(x+\Delta x,y+\Delta y)$ will be 1. Since $N$ has at least 1993 representations as a sum of two squares, we are done.
29.11.2023 23:57
alternatively take $A = \varnothing$ which also works because the condition is vacuously true
06.01.2024 21:47
Here's the anti-solution: Restrict $A$ to $\mathbb Q^2$, and fix some very large $N$ such that there are $10^{10}$ rational points on the unit circle with denominator at most $N$. Now take all rational points with denominator at most $N$ in $[-1, 1] \times [-1, 1]$, such that drawing a unit circle centered at some point in the set hits at least $1993$ other points. This finishes the problem.
10.02.2024 23:22
Solved with alsk. Take two points one apart; then repeat the following $1993$ times: Ctrl A, Ctrl C, Ctrl V, shift one unit in a random direction.