珍珠湾ART

标题: Erdos 平面染色问题 [打印本页]

作者: fzy 时间: 2005-9-13 20:30
标题: Erdos 平面染色问题

Erdos 问过下列问题：设2维平面可以染成N种颜色，使得距离为1的任意两点颜色都不同。问N最小是多少？

原题太难，Erdos也不会。只知道4<=N<=7。但是这两个上下界不太难。

难度：++

1。证明如果平面上所有的点都染成三种颜色之一，必有同颜色的两点距离为1。

2。证明平面可以染成7种颜色，使得距离为1的任意两点颜色都不同。

作者: yma16 时间: 2005-9-13 20:46
标题: 回复：Erdos 平面染色问题

I attended one of Erdos lectures. I remembered in the lecture, he offered money for some problems. Most people there did not understand him. After a few years, he passed away.

作者: 乱弹 时间: 2005-9-13 20:56
标题: You were so lucky to meet him.

You were so lucky to meet him.

作者: fzy 时间: 2005-9-13 21:02
标题: I also attended one of his lectures

Forgot the topic. But he did use many of his terminologies, such as Poison, Noise, and he joked about himself being old.

作者: sean9991 时间: 2005-9-13 21:58
标题: answer

Q1.

Consider an equilateral triangle ABC of unit length. Let C1, C2, C3 be the color of its three vertices, respectively. The mirror image of vertex A (colored C1) w.r.t line BC, call it D, should also be colored C1.

Consider another equilateral triangle AEF of unit length. The mirror image of vertex A w.r.t. line EF, call it G, should also be colored C1. We can rotate AEF such that the distance between D and G is 1.

Q2.

Color the plane like a bee's nest.

欢迎光临珍珠湾ART (http://zzwav.com/)