Задача по геометрии на плоскости.
Вот задача, которую я сегодня услышал. Задача вполне олимпиадного типа, но решения ни кто вроде бы не знает. Задачу предлагает Bruce Kleiner, но я не уверен, что он ее автор. Итак, рассмотрим произвольный граф G, у которого вершины - все узлы квадратной решетки. Считаем длину каждого ребра равной единице. Расстояние между вершинами графа - длина кратчайшего пути, соединяющего эти вершины. Спрашивается, существует ли такой граф G, чтобы для любых двух вершин A, B выполнялось
|A-B|-const не превосходит dist_G(A,B) не превосходит |A-B| + const ?
Здесь |.| - обычное (Евклидово) расстояние на плоскости; const - константа, не зависящая от A, B.
Скажем, если G - обычная квадратная решетка, то
|A-B| не превосходит dist_G(A,B) не превосходит sqrt(2) |A-B|
и константу sqrt(2) уменьшить до 1 нельзя (для этого G). Tо есть квадратная решетка не подходит.
|A-B|-const не превосходит dist_G(A,B) не превосходит |A-B| + const ?
Здесь |.| - обычное (Евклидово) расстояние на плоскости; const - константа, не зависящая от A, B.
Скажем, если G - обычная квадратная решетка, то
|A-B| не превосходит dist_G(A,B) не превосходит sqrt(2) |A-B|
и константу sqrt(2) уменьшить до 1 нельзя (для этого G). Tо есть квадратная решетка не подходит.