1999-угольник

[pakandrew]

Существует ли такой выпуклый 1999-угольник,на сторонах которого (в порядке обхода) лежат соответственно 1,2,...,1999 точек с целыми координатами?

[Коровьев]

Существует.
Задача А. С. Голованова из 1999 года.
Построение
http://www.sibpatent.ru/default.asp?khi ... l=1&sort=3

[Gordmit]

Коровьев писал(а):

Построение
http://www.sibpatent.ru/default.asp?khi ... l=1&sort=3

Что-то весьма странное там написано:

Цитата:

Предложен простой способ точного построения правильного многоугольника с количеством сторон в виде предельно большого простого числа (например, 1999).
Для построения правильного 1999-угольника предложенным способом не требуется сложных инструментов: используются всего лишь циркуль и линейка без делений.

Но ведь известно, что правильный $p$-угольник можно построить циркулем и линейкой тогда и только тогда, когда $p=2^{2^n}+1$ - простое число Ферма.

P.S. Не говоря уже о том, что к задаче топикстартера это не имеет отношения...
Или я чего-то не понимаю?

[pakandrew]

Уважаемый Коровьев,не могли бы вы объяснить как использовать этот факт в решении первоначальной задачи?

[Руст]

По ссылке Коровьева написана абсолютная чушь. Со времён Гаусса известно, что циркулем и линейкой можно построить только иррациональности выражаемые квадратичными корнями от рациональных чисел типа $a+\sqrt{b+\sqrt{c+\sqrt{d}}+\sqrt{e}}$ (нет радикалов более высокого порядка).
К тому же это не имеет никакого отношения к исходной задаче. Очевидно, что нульзя построить правильный 1999 угольник, удовлетворяющий условиям задачи. Иначе из рациональности наклона направления одной стороны вытекает нерациональность других наклонов.
В исходной задаче не говорится о правильности многоугольника. Соответственно она решается тривиально и ответ да.

[Коровьев]

Дык, я и привёл ссылку мелким шрифтом.
Задача со Второго математическкого турнира старшеклассников "Кубок памяти А.Н. Колмогорова".
Очевидно, надо было просто проверить число на критерий Гаусса. С другой стороны это довольно тривиально для такого турнира...

[pakandrew]

Прошу людей ,которые знают решение первоначальной задачи,показать свои решения Дело в том что ,я учусь в 9-ом классе,и для меня эта задача не тривиальна.К тому же я не знаю довольно сложных вещей,как к примеру критерий Гаусса
Всем заранее спасибо!

[Коровьев]

Gordmit писал(а):

Но ведь известно, что правильный $p$-угольник можно построить циркулем и линейкой тогда и только тогда, когда $p=2^{2^n}+1$ - простое число Ферма.

$p=2^{2^n}+1$ - простое число.
Это и есть критерий Гаусса.

[Профессор Снэйп]

pakandrew писал(а):

Прошу людей ,которые знают решение первоначальной задачи,показать свои решения

Это не принципиально, но всё же.

pakandrew писал(а):

Существует ли такой выпуклый 1999-угольник,на сторонах которого (в порядке обхода) лежат соответственно 1,2,...,1999 точек с целыми координатами?

1) Верно ли я понял, что на одной из сторон должна находиться ровно одна точка с целыми координатами, на следующей (в порядке обхода) --- ровно две, на следующей --- три и так далее?

2) Могут ли точки, о которых идёт речь, совпадать с вершинами многоугольника, или они обязаны лежать "внутри" сторон?

[pakandrew]

Профессор Снэйп писал(а):

Цитата:

1) Верно ли я понял, что на одной из сторон должна находиться ровно одна точка с целыми координатами, на следующей (в порядке обхода) --- ровно две, на следующей --- три и так далее?

Да,вы правильно поняли.

Цитата:

2) Могут ли точки, о которых идёт речь, совпадать с вершинами многоугольника, или они обязаны лежать "внутри" сторон?

В условии об этом ничего не сказано,значит могут.
Задача с одного Питерского матбоя,в котором я не был.

[bobo]

Считаем, что вершина (целочисленная) учитывается дважды. Тогда построение такое: строим сторону, на которой 1999 целочисленных точек, причем с началом в целочисленной точке. Затем с другого конца достраиваем сторону, на которой 1998 целочисленных точек и т.д. (соблюдая выпуклость). Остановимся, когда останется провести два последние отрезка, на которых находится 2 и 1 целочисленная точка, при этом отрезок с 3-мя целочисленными точками должен заканчиваться в целочисленной точке. Но это можно сделать всегда. Чтобы соблюсти выпуклость нужно соединить начало и конец ломаной отрезком и по ту сторону, где не лежит ломаная, провести отрезочек, который проходит еще через одну целую точку и заканчивается в такой точке, что если мы соединим самое начало ломаной с этой точкой, то получится прямая с иррациональным тангенсом наклона ( тогда она не пройдет еще через одну целую точку).