Question

8 Однажды царь Шахрияр сказал Шахерезаде: «Вот тебе бумажный круг, на границе которого 501 501 точка. Каждую ночь ты должна один раз резать имеющуюся у тебя фигуру по прямой, содержащей любые две отмеченные точки, оставляя себе лишь один фрагмент, а второй выбрасывать. Следи, чтобы у тебя оставался не многоугольник, но такая фигура, из которой можно получить многоугольник, разрезая дальше». В какую по счёту ночь Шахерезада, как бы ни старалась, уже не сможет выполнить условие Шахрияра?

Answer 1

Ответ:

в 501 ночь

Пошаговое объяснение:

Отрезать нужно по хордам, сегмент выбрасывать.

Значит, у нас ситуация вписанного в окружность  многоугольника.

Если у многоугольника  501 вершина, значит у него 501 сторона и при этом получаем 501 хорду.

Значит, 500 раз Шахерезада будет отрезать сегменты, и у нее будет оставаться в руках не многоугольник.

На 501 раз уже не сможет.

#spj1

Answer 2

Это классическая задача, известная как "Задача про разрезание фигуры". Чтобы ответить на вопрос, нужно рассмотреть общие закономерности и пойти по индукции.

Пусть у нас есть N точек на плоскости, образующих бумажную фигуру. Мы хотим разрезать эту фигуру, чтобы оставить максимально возможное количество точек в получившейся фигуре.

Так как первый разрез делается так, чтобы оставить себе только одну точку, число точек уменьшается на (N-1). После первого разреза у нас остается (N-1) точка.

Для простоты обозначим за f(N) количество точек, которое остается после разрезания фигуры с N точками.

Итак, f(1) = 1 (после первого разреза остается 1 точка).

Затем рассмотрим второй разрез. Возможно, что некоторые точки попадут в получившуюся вторую часть фигуры, поэтому у нас останется максимум (N-1) точка после второго разреза. Это означает, что f(N) <= (N-1).

Переформулируем условие задачи: нам нужно найти наименьшее N, при котором f(N) = N-1.

Поиск минимального N, при котором f(N) = N-1, является поиском наименьшего числа, для которого (N-1) >= (N-2). Видно, что это выполняется для N = 3. Таким образом, на третью ночь Шахерезада уже не сможет выполнить условие Шахрияра, как бы она ни старалась.

Ответ: на третью ночь Шахерезада не сможет выполнить условие Шахрияра.