Задача 98271

Темы:    [ Теория алгоритмов (прочее) ] [ Плоскость, разрезанная прямыми ] [ Прямоугольники и квадраты. Признаки и свойства ] [ Оценка + пример ]

Сложность: 3+ Классы: 6,7,8

Условие

Автор: Канель-Белов А.Я.

На плоскости расположен квадрат и невидимыми чернилами нанесена точка P. Человек в специальных очках видит точку. Если провести прямую, то он отвечает на вопрос, по какую сторону от неё лежит P (если P лежит на прямой, то он говорит, что P лежит на прямой).
Какое наименьшее число таких вопросов необходимо задать, чтобы узнать, лежит ли точка P внутри квадрата?

Решение

  Пусть наш квадрат – ABCD. Сначала проведём диагональ AC. Если окажется, что P лежит от нее по ту же сторону, что и вершина B, достаточно будет узнать по какую сторону от прямых AB и BC лежит точка P.
  Случай, когда на первый вопрос человек укажет на полуплоскость, содержащую точку D, аналогичен.
  Если задано всего один или два вопроса, то проведено меньше трёх прямых. Каковы бы ни были ответы (за исключением случая, когда точка принадлежит пересечению двух проведённых прямых), мы можем узнать только, принадлежит ли точка тем частям, на которые плоскость разбита проведёнными прямыми. Но эти части не ограничены, и принадлежность им не может быть доказательством того, что точка принадлежит квадрату.

Ответ

Три вопроса.

Замечания

1. 3 балла.

2. Для аналогичной задачи про выпуклый 2^k-угольник (а тем самым, и про n-угольник, где  n ≤ 2k)  достаточно  k + 1  вопроса. Здесь работает идея "дихотомии" – деления пополам: первым вопросом мы выясняем, по какую сторону от прямой, соединяющей 1-ю вершину с "противоположной" (2^k–1+1)-й, лежит точка P, и (по индукции) сводим задачу к аналогичной для 2^k–1-угольника.

3. Аналогичные задачи в пространстве сложнее, но и там полезна идея "дихотомии" (именно она оказалась ключевой в работах А. Хочияна и др., где вопреки ожиданиям было обнаружено, что некоторые задачи линейного программирования имеют полиномиальную сложность, то есть решаются значительно быстрее, чем полным перебором).

Источники и прецеденты использования

олимпиада
Название	Турнир им.Ломоносова
номер/год
Название	конкурс по математике
Дата	1995
Задача
Номер	1
олимпиада
Название	Турнир городов
Турнир
Дата	1995/1996
Номер	17
вариант
Вариант	осенний тур, тренировочный вариант, 10-11 класс
Задача
Номер	1
журнал
Название	"Квант"
год
Год	1996
выпуск
Номер	1
Задача
Номер	М1531
олимпиада
Название	Турнир городов
Турнир
Дата	1995/1996
Номер	17
вариант
Вариант	осенний тур, тренировочный вариант, 8-9 класс
Задача
Номер	1