Мне в частной переписке досталась крупинка золота - очень интересная задачка. Я ее не решила. Предлагаю ее решить вам, и объяснить свое решение. Без объяснения ответ не принимается. Если объяснение совпадет с тем, которое я знаю, то "браво" будет сразу. Если при правильном ответе объяснение будет отличным от того, которое я знаю, и мне оно не покажется логически неправильным, то я буду спрашивать совета у того, очень умного, человека, который мне задал эту задачку. Одним из условий размещения этой задачки на Эрудите было обязательное упоминание того, что эта задачка размещена на Диофант-ру, что я и делаю.
Итак:
На плоской квадратной сетке рассматриваются выпуклые многоугольники, все вершины которых находятся в узлах сетки, а внутри сторон и внутри многоугольника нет ни одного узла. Найдите, чему равно наибольшее возможное количество сторон такого многоугольника.
Здравствуйте. Я новичок на этом форуме :). Мне ответ видится абсолютно тупым: Если вершины многоугольников находятся только в узлах сетки (то есть в вершинах плоских квадратов), то и внутри каждого квадрата будет находится также выпуклый квадрат, то есть число сторон многоугольника - 4. Если же присутствие вершины многоульника в каждом узлу сетки необязательно, а также нет ограничения по размерам квадратной сетки, то совершенно очевидно, что число сторон многоугольника может быть любым и максимальное число не может быть найдено. Либо я не правильно понял условие задачи?
Владимир, Здравствуйте. Я сейчас очень уставшая, и плохо соображаю, поэтому подумаю над вашим ответом завтра. И в моих задачках можно отвечать без спойлера.
Вы выложили только ответ, без объяснений и доказательств.
Поскольку к этой задачке нет интереса со стороны участников, то я выкладываю решение:
Цитата
1) Пример такого многоугольника – квадрат со стороной, равной шагу сетки.
2) Для дальнейшего нам необходимо некоторое, нередко применяемое, достаточно простое утверждение. Пусть А(х1; у1) и В(х2; у2) – две точки на плоскости с целочисленными координатами (в прямоугольной декартовой системе координат).
Лемма: Середина отрезка АВ имеет целочисленные координаты тогда и только тогда, когда числа х1 и х2 одинаковой четности, равно как и числа у1 и у2 одинаковой четности.
Доказательство. Пусть С(х0; у0) – середина отрезка. Тогда (по формуле аналитической геометрии) х0=(х1+х2)/2, у0=(у1+у2)/2. В числителях – четные числа, откуда всё следует.
3) Пример: А(1; -1), В(-5;1). Координаты середины отрезка АВ: -3 и 0.
4) Закончим решение задачи. Допустим, что существует такой многоугольник с количеством сторон 5 или больше. Введём какую-либо систему координат, оси которой совпадают с двумя прямыми сетки. Выберем какие-либо 5 вершин многоугольника. Среди 5-ти абсцисс этих точек обязательно найдутся 3 одинаковой четности. Зафиксируем соответствующие 3 вершины многоугольника. Среди 3-х ординат этих точек обязательно найдутся две одинаковой четности.
Итак, мы выделили две вершины многоугольника, назовём их Р и Q, абсциссы (ординаты) которых одинаковой чётности. Следовательно, по лемме, середина О отрезка РQ имеет целочисленные координаты, то есть является узлом сетки. А так как многоугольник выпуклый, то точка О лежит либо внутри его, либо на границе, что запрещено условием задачи. Следовательно, ответ: 4.
Сообщение отредактировал Гретхен - Вт, 14.05.13, 12:30
Мда, честно скажу, с трудом представлял себе доказательство... Достаточно представить себе чертеж по условиям задачи - и сразу всё становится ясно... Ну это типа того, что параллельные линии не пересекаются или что через две точки плоскости можно провести только одну прямую - доказательства этих фактов есть, но сами по себе факты настолько очевидны, что доказательств не нужно. Так что за отсутствие доказательство - пардон
