May the points of a disc of radius $1$ (including its circumference) be partitioned into three subsets in such a way that no subset contains two points separated by a distance $1$?
Problem
Source: Baltic Way 1999
Tags: combinatorics proposed, combinatorics
29.12.2010 18:52
The answer is "yes". Partition into 3 sets "1","2","3" as below: -First,all points in the disc of radius 0,5 which has center I coincide to the center of the disc mentioned in the problem (not count points in its circumference) will be in set 1. -Then,choose a regular hexagon in the circumference of the disc of radius 1 and partition like my figure below,any remain point in that circumference will be in the set of a nearest number in its "left" (we choose one of two directions in the circumference as "left" and the other one will be "right").So it easy to prove that two arbitary points in that circumference which distance are 1 distributed to two different sets. -Finally,any point A lie outside or in the circumference of the small disc but lie inside the big disc will be distributed to the same sets as the intersect point of IA and the circumference of the big disc. If there are 2 points A,B which lie not inside the the big disc and are in the same set,then we denote C,D,E,F like my figure and obviously CD<AB so $CD \leq \frac{2}{\sqrt{5}} < \frac{2}{\sqrt{3}}$ (easy to prove this by using Thales and Pythagore theorem) so $EF<\frac{4}{\sqrt{3}}$ and $EF \geq EC \geq CD=1$ so point E and F are in different sets.This is the contradiction. Q.E.D
Attachments:
31.12.2010 13:47
I don't understand , A and B are green and d(A,B)=1 : Image not found Domi
02.01.2011 19:24
It's impossible , the all arc MN is red ... Image not found Domi
12.09.2015 15:13
The answer is 「NO」. proof) Let´s consider the problem on the x-y coordinate. The centre of the disc is O(0,0).The other points in the disc are A(1/2,1/2・3^1/2),B(1/2,-1/2・3^1/2),C(1,0). It's easy to verify that the distance between two different points x,y∈{A,B,C,D} is 1. By the pigeon hole principal,there exists one of the three area contains at least two points in {A,B,C,D}.Then this area have to contain the two points whose distance is 1. The proof is completed.
12.09.2015 16:50
Takeya.O wrote: The centre of the disc is O(0,0).The other points in the disc are A(1/2,1/2・3^1/2),B(1/2,-1/2・3^1/2),C(1,0). It's easy to verify that the distance between two different points x,y∈{A,B,C,D} is 1. Are you sure? The distance between $A$ and $B$, as you defined them, is $\sqrt{3} \not= 1$. In fact, there are no four points in the plane such that the distance between any two of them is 1.
12.09.2015 18:56
Sorry,I missed. What is the answer(YES or NO) for this problem?
31.12.2019 06:42
It is extremely obvious the answer is No. Consider an inscribed hexagon. Clearly no 2 adjacent vertices of the hexagon can be part of the same subset since they are 1 unit apart. Since we are allowed to have only 3 subsets, it readily follows that at least 2 vertices out of the 6 must belong to the same subset resulting in a contradiction.
31.12.2019 13:39
KRIS17 wrote: It is extremely obvious the answer is No. Consider an inscribed hexagon. Clearly no 2 adjacent vertices of the hexagon can be part of the same subset since they are 1 unit apart. Since we are allowed to have only 3 subsets, it readily follows that at least 2 vertices out of the 6 must belong to the same subset resulting in a contradiction. In fact, the vertices of the inscribed hexagon can be colored in only two colors, i.e. alternatively $1,2,1,2,1,2$. So, no contradiction that way. But, nevertheless, the answer is "NO". Suppose on the contrary, such coloring (partitioning) is possible. Consider any two equilateral triangles with side length $1$ unit, $\triangle ABC, \triangle A'BC$ which have a common side $BC$ and lie inside the unit disk. Clearly $|AA'|=\sqrt{3}$. Now, the key idea is that $A$ and $A'$ are colored in the same color. Indeed, the points $A,B,C$ are colored in distinct colors and so are $A',B,C$. It follows that any two points $A,A'$ apart $\sqrt{3}$ units and inside the unit disk, such that the corresponding points $B,C$ are also inside the unit disk, must be colored in the same color. Fixing $A$ and rotating slightly $A'$ (with $A',B,C$ remaining inside the unit disk) we conclude all "small" arcs that lie close to the circumference of the disk, and are part of circles with radii $\sqrt{3}$, are colored with one and the same color. It easily follows, a thin annular strip with outer border the unit circle is colored in the same color (it can be calculated exactly how thin is that annular strip, but it doesn't matter). Obviously, it's a contradiction.