Erdos 平面染色问题

fzy · 发表于 2005-9-13 20:30:46

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

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

难度：++

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

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

yma16 · 发表于 2005-9-13 20:46:17

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:08

You were so lucky to meet him.

fzy · 发表于 2005-9-13 21:02:07

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:06

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.

		自动登录	找回密码
密码			立即注册

动态微博

Erdos 平面染色问题

回复：Erdos 平面染色问题

You were so lucky to meet him.

I also attended one of his lectures

answer