| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
(a) The points of a unit square (interior and edge) have one of two colors.
Prove that two similarly-colored points are at distance >= sqrt(5/4) apart.
(b) If the points of a unit square are colored with one of n colors,
two similarly-colored points must be at least L(n) apart. Prove that:
L(2) = sqrt(5/4) (as in part (a))
L(3) = sqrt(65/64)
L(4) = sqrt(1/2)
L(5) = sqrt(1/2) (surprise!)
(c) It's easy to show that L(6) <= sqrt(13/36), and L(n�) <= sqrt(2/n�).
Are these equalities?
(d) What are L(6), L(7), L(8), and L(9)?
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1639.1 | Is there some missing information? | UNTADC::TOWERS | Tue Jul 14 1992 04:57 | 13 | |
This doesn't make sense to me.
>The points of a unit square (interior and edge) have one of two colors.
>Prove that two similarly-colored points are at distance >= sqrt(5/4) apart.
I take the first sentence to mean that for each of the points (x,y)
where 0 <= x,y <= 1, I can choose one of two colours.
Well, OK. I choose (�,�) and (�,�) to be red and all other points to be
blue. Then the two red points are a distance of � apart and the
distance between any two blue points varies between 0 and sqrt(2).
Brian
| |||||
| 1639.2 | BEING::EDP | Always mount a scratch monkey. | Tue Jul 14 1992 09:48 | 8 | |
Re .1:
Prove that no matter how somebody else colors the points of a square,
you can find two similarly-colored points that are a distance greater
than or equal to sqrt(5/4) apart.
-- edp
| |||||
| 1639.3 | GUESS::DERAMO | Dan D'Eramo, zfc::deramo | Tue Jul 14 1992 10:17 | 23 | |
part (a)
Consider the corners and the midpoints of the edges.
The distance between a corner and the midpoint of a
nonadjacent edge is sqrt(5/4).
D Y C
Z X
A W B
Let the two colors be red and blue.
Arbitraily let A be red. Then X and Y are sqrt(5/4) from
A, so they must be blue, otherwise {A,X} or {A,Y} is a
"monochromatic distant pair" :-). Now B is sqrt(5/4)
from Y so it must be red, and D is sqrt(5/4) from X so it
must be red; otherwise either {B,Y} or {D,X} is a
monochromatic distant pair. But now B and D are sqrt(2)
> sqrt(5/4) apart and are both red. QED.
Dan
| |||||