Задача по геометрии на плоскости.

[markvs]

Вот задача, которую я сегодня услышал. Задача вполне олимпиадного типа, но решения ни кто вроде бы не знает. Задачу предлагает Bruce Kleiner, но я не уверен, что он ее автор. Итак, рассмотрим произвольный граф G, у которого вершины - все узлы квадратной решетки. Считаем длину каждого ребра равной единице. Расстояние между вершинами графа - длина

Comments

[french_man]

Гм. A вот более простой вопрос. Существует ли граф, для которого

limsup dG(A,B)/|A-B| · limsup |A-B|/dG(A,B) < √2

[french_man]

Здесь limsup - верхний предел при |A-B|→∞

[flaass]

Из шестиугольной решетки легко строится. Вроде, там будет 2/√3

[french_man]

Да, но у нас квадратная.

[flaass]

Наложить на квадратную шестиугольную той же плотности, а потом устроить биекцию с расстоянием О(1). Ведь есть же такая?

[flaass]

Хм. Сорри. Длина ребра... Хм.
Надо еще подумать.
Навскидку кажется, что на твой вопрос 1+о(1), а на вопрос в посте - нельзя.

[french_man]

Мне тоже казалось, что в моем вопросе можно доехать до единички, но сейчас уже не кажется.

[french_man]

A, ну да, 1 достигается. Надо накидать дигоналек случайным образом с вероятностью 1/√2. Но вот исходную задачу это все равно не решает.

[flaass]

Ух ты!
Подумаю.

[french_man]

Ну, я не просчитывал, может, и соврал. Но надо явно чего-то случайно докидывать.

[french_man]

A как их сделать той же плотности?