?

Log in

No account? Create an account
четыре точки (математическое) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

четыре точки (математическое) [сент. 11, 2015|03:52 pm]
Anatoly Vorobey
[Tags|]

Можно ли поставить три точки на плоскости так, чтобы все расстояния между ними были нечетными целыми числами?

Да. Это тривиально, можно просто поставить их в вершины равностороннего треугольника с длиной стороны 1.

А как насчет четыре точки на плоскости, и все расстояния между ними нечетные числа?

А вот тут оказывается, что это невозможно. Есть красивое простое доказательство того, что это невозможно, причем оно пользуется довольно неожиданно аппаратом линейной алгебры. Я помещу его ниже под катом для всех, кому интересно.





Если вам понравилось это доказательство, возможно, стоит посмотреть на статью, где это впервые было доказано:

Are There n+2 Points in E^n with Odd Integral Distances? (Graham, Rothschild, Straus, 1974)

Там с помощью чуть более тщательного анализа доказывается следующий удивительный факт: не только 4 точки на плоскости, но и 5 точек в пространстве невозможно расположить с попарными нечетными расстояниями, и вообще в n-мерном эвклидовом пространстве можно расположить так n+2 точки тогда и только тогда, когда n при делении на 16 дает остаток 14. То есть наименьший пример такого - это 16 точек в 14-мерном пространстве, и в статье дается конкретное построение этих 16 точек!
СсылкаОтветить

Comments:
[User Picture]From: ivan_semushin
2015-09-11 12:58 pm
Похоже, это тот самый Graham, которого многие знают благодаря рекордному числу его имени.
(Ответить) (Thread)
[User Picture]From: avva
2015-09-11 12:59 pm
Да, это он :)
(Ответить) (Parent) (Thread)
[User Picture]From: xaxam
2015-09-11 01:13 pm
Очень симпатично.

А также поучительно, чем занимались сотрудники Белл Лабс в далёком 74-м, когда ещё не было ни Майкрософт Ресёрч, ни АйБиЭм ресёрч ;-)
(Ответить) (Thread)
[User Picture]From: criblycrablybum
2015-09-11 05:50 pm

Наверное кодами (исправлениями ошибок) занимались.

(Ответить) (Parent) (Thread)
[User Picture]From: mi_b
2015-09-12 12:27 am
Да, нечетные расстояния как раз там интересны
(Ответить) (Parent) (Thread)
[User Picture]From: shultz_flory
2015-09-11 02:16 pm
>> 16 точек в 14-мерном пространстве, и в статье дается конкретное построение этих 16 точек!

На плоском листе бумаги? Вы все врёти!
(Ответить) (Thread)
From: edo_rus
2015-09-12 01:16 am
да ничего странного, если внимательно присмотреться, то он не идеально плоский.
(Ответить) (Parent) (Thread)
[User Picture]From: brandt1
2015-09-11 06:09 pm
Мне кажется, сказать, что решено "аппаратом линейной алгебры" - это несколько преувеличено. Используется векторная алгебра в 3-мерном пр-ве и чуть-чуть матричной алгебры.
(Ответить) (Thread)
[User Picture]From: buddha239
2015-09-11 09:42 pm
Так это и есть линейная алгебра.:)
(Ответить) (Parent) (Thread)
[User Picture]From: akor168
2015-09-17 05:53 am
Линейная алгебра это по видимому, когда у нас есть m-мерное пространство! Или нет, m это слишком мало, нужно n-мерное!
(Ответить) (Parent) (Thread)
[User Picture]From: primaler
2015-09-11 08:04 pm
Что из статьи остаётся совершенно неясным, так это как они до этого додумались %)
(Ответить) (Thread)
[User Picture]From: buddha239
2015-09-11 09:44 pm
Ну, логично же рассматривать остатки по модулю степеней двойки. А определитель, возможно, кто-то раньше составил.
(Ответить) (Parent) (Thread)
[User Picture]From: micliva
2015-09-11 09:53 pm
Насчет определителя, это много где используемая идея, что через длины ребер можно посчитать объем k-мерного симплекса. А значит получить условие, когда k+2 точки с данными попарными расстояниями лежат в k-мерном пространстве.
(Ответить) (Parent) (Thread)
[User Picture]From: buddha239
2015-09-11 10:00 pm
Я тоже подумал об объемах симплексов - но рассмотреть остатки по модулю 8 не догадался (а если бы догадался, то все равно поленился бы:)).
(Ответить) (Parent) (Thread)