Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1971 IMO Problems/Problem 5"

(Created page with "Prove that for every natural number m; there exists a finite set S of points in a plane with the following property: For every point A in S; there are exactly m points in S which...")
 
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
−
Prove that for every natural number m; there exists a finite set S of points
+
==Problem==
−
in a plane with the following property: For every point A in S; there are
+
Prove that for every natural number <math>m</math>; there exists a finite set <math>S</math> of points in a plane with the following property: For every point <math>A</math> in <math>S</math>; there are exactly <math>m</math> points in <math>S</math> which are at unit distance from <math>A</math>.
−
exactly m points in S which are at unit distance from A.
+
 
 +
==Solution 1==
 +
I shall prove a more general statement about the unit distance graph(<math>V=\mathbb{R}^2</math>, adjacency iff the Euclidean distance between the points is <math>1</math>) and this will follow as a consequence.
 +
if <math>G,H</math> occur as unit distance graphs, then so does <math>G\times H</math>( here <math>G\times H</math> is described as <math>V(G\times H)=V(G)\times V(H), (v_1,w_1)\leftrightarrow (v_2,w_2) \Leftrightarrow v_1=v_2,w_1\leftrightarrow w_2</math> or <math>v_1\leftrightarrow v_2,w_1=w_2</math>).
 +
this is seen by describing the vertices by complex numbers. suppose there is an embedding of <math>G</math> by the complex numbers <math>v_1,v_2\ldots,v_n</math> and for <math>H</math> by the numbers <math>w_1,w_2,\ldots, w_m</math>. we claim that for some choice of <math>0\leq\theta<2\pi</math>, <math>v_i+e^{i\theta}w_j</math> will do the job(a suitable rotation).
 +
what we need is that <math>(v_i+e^{i\theta}w_j)\leftrightarrow (v_k+e^{i\theta}w_l)</math> iff either <math>v_i=v_k,|w_j-w_l|=1</math> or <math>w_j=w_l,|v_i-v_k|=1</math>. clearly if the condition holds then the adjacency is satisfied. suppose <math>i\neq k,j\neq l</math> and that the corresponding complex numbers are at a distance <math>1</math> from one another. Then this gives a quadratic in <math>e^{i\theta}</math> and hence <math>\theta</math> can take only finitely many values here.ruling this out for each such set of <math>i,j,k,l</math> hence rules out finitely many values of <math>\theta</math> and therefore a suitable choice exists.
 +
for the given problem we need a unit distance graph which is regular of degree <math>m</math> for any given <math>m</math>. since we can form the graph <math>K_2</math>, we can form <math>Q_n=Q_{n-1}\times K_2</math>(the unit cube) and that solves the problem.
 +
 
 +
This solution was posted and copyrighted by seshadri. The original thread for this problem can be found here: [https://aops.com/community/p368343]
 +
 
 +
==Solution 2==
 +
Suppose <math>S</math> has the form<cmath>S_m=\left\{\sum_{\mathbf v \in U} \mathbf v \;\middle\vert\; U \subseteq V_m\right\}=\left\{\sum_{i=1}^m b_i \mathbf v_i \;\middle\vert\; b_i \in \{0,1\}\right\}\!,</cmath>where <math>V_m=\{\mathbf v_1,\mathbf v_2,\dots,\mathbf v_m\}</math> is unknown set of distinct unit vectors in <math>\mathbb R^2</math>. We can build <math>V_m</math> inductively, starting from the empty set and adding vectors to it, one by one. We just need to make sure that two thing are respected:
 +
1. All <math>2^m</math> vectors in <math>S_m</math> are distinct;
 +
2. Two vector sums are at unit distance from one another if and only if they differ in presence of exactly one summand (i.e. one and only one coefficient <math>b_i</math> in the sum changes from <math>0</math> to <math>1</math>).
 +
If these two conditions are kept, then each of <math>2^m</math> points at <math>S_m</math> will be at unit distance from exactly <math>m</math> points corresponding to sums at which one and only one of <math>m</math> coefficients differs from coefficients of this point. However, respecting these conditions is not hard because <math>\left\|\sum_{\mathbf v \in U_1} \mathbf v - \sum_{\mathbf v \in U_2} \mathbf v\right\|=\left\|\sum_{\mathbf v \in U_1 \setminus U_2} \mathbf v \,-\! \sum_{\mathbf v \in U_2 \setminus U_1} \mathbf v\right\|</math> and for each new vector being added to <math>V_m</math> there is at most some finite set of forbidden endpoints given by sums/differences of already determined vectors but the rest of the (infinite) unit circle is permissible.
 +
 
 +
This solution was posted and copyrighted by Bandera. The original thread for this problem can be found here: [https://aops.com/community/p11000205]
 +
 
 +
== See Also == {{IMO box|year=1971|num-b=4|num-a=6}}

Latest revision as of 13:09, 29 January 2021

Problem

Prove that for every natural number $m$; there exists a finite set $S$ of points in a plane with the following property: For every point $A$ in $S$; there are exactly $m$ points in $S$ which are at unit distance from $A$.

Solution 1

I shall prove a more general statement about the unit distance graph($V=\mathbb{R}^2$, adjacency iff the Euclidean distance between the points is $1$) and this will follow as a consequence. if $G,H$ occur as unit distance graphs, then so does $G\times H$( here $G\times H$ is described as $V(G\times H)=V(G)\times V(H), (v_1,w_1)\leftrightarrow (v_2,w_2) \Leftrightarrow v_1=v_2,w_1\leftrightarrow w_2$ or $v_1\leftrightarrow v_2,w_1=w_2$). this is seen by describing the vertices by complex numbers. suppose there is an embedding of $G$ by the complex numbers $v_1,v_2\ldots,v_n$ and for $H$ by the numbers $w_1,w_2,\ldots, w_m$. we claim that for some choice of $0\leq\theta<2\pi$, $v_i+e^{i\theta}w_j$ will do the job(a suitable rotation). what we need is that $(v_i+e^{i\theta}w_j)\leftrightarrow (v_k+e^{i\theta}w_l)$ iff either $v_i=v_k,|w_j-w_l|=1$ or $w_j=w_l,|v_i-v_k|=1$. clearly if the condition holds then the adjacency is satisfied. suppose $i\neq k,j\neq l$ and that the corresponding complex numbers are at a distance $1$ from one another. Then this gives a quadratic in $e^{i\theta}$ and hence $\theta$ can take only finitely many values here.ruling this out for each such set of $i,j,k,l$ hence rules out finitely many values of $\theta$ and therefore a suitable choice exists. for the given problem we need a unit distance graph which is regular of degree $m$ for any given $m$. since we can form the graph $K_2$, we can form $Q_n=Q_{n-1}\times K_2$(the unit cube) and that solves the problem.

This solution was posted and copyrighted by seshadri. The original thread for this problem can be found here: [1]

Solution 2

Suppose $S$ has the form\[S_m=\left\{\sum_{\mathbf v \in U} \mathbf v \;\middle\vert\; U \subseteq V_m\right\}=\left\{\sum_{i=1}^m b_i \mathbf v_i \;\middle\vert\; b_i \in \{0,1\}\right\}\!,\]where $V_m=\{\mathbf v_1,\mathbf v_2,\dots,\mathbf v_m\}$ is unknown set of distinct unit vectors in $\mathbb R^2$. We can build $V_m$ inductively, starting from the empty set and adding vectors to it, one by one. We just need to make sure that two thing are respected: 1. All $2^m$ vectors in $S_m$ are distinct; 2. Two vector sums are at unit distance from one another if and only if they differ in presence of exactly one summand (i.e. one and only one coefficient $b_i$ in the sum changes from $0$ to $1$). If these two conditions are kept, then each of $2^m$ points at $S_m$ will be at unit distance from exactly $m$ points corresponding to sums at which one and only one of $m$ coefficients differs from coefficients of this point. However, respecting these conditions is not hard because $\left\|\sum_{\mathbf v \in U_1} \mathbf v - \sum_{\mathbf v \in U_2} \mathbf v\right\|=\left\|\sum_{\mathbf v \in U_1 \setminus U_2} \mathbf v \,-\! \sum_{\mathbf v \in U_2 \setminus U_1} \mathbf v\right\|$ and for each new vector being added to $V_m$ there is at most some finite set of forbidden endpoints given by sums/differences of already determined vectors but the rest of the (infinite) unit circle is permissible.

This solution was posted and copyrighted by Bandera. The original thread for this problem can be found here: [2]

See Also

1971 IMO (Problems) • Resources
Preceded by
Problem 4 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 6
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1971_IMO_Problems/Problem_5&oldid=143817"