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

   Решение

Темы:    [ Степень вершины ] [ Индукция (прочее) ]

Сложность: 4 Классы: 9,10,11

Прислать комментарий

Условие

На плоскости нарисовано несколько точек, некоторые пары точек соединены отрезками. Известно, что из каждой точки выходит не более k отрезков. Докажите, что точки можно покрасить в  k + 1  цвет таким образом, чтобы каждые две точки, соединенные отрезком, были покрашены в разные цвета.

Подсказка

Используйте индукцию по числу точек.

Решение

  Индукция по числу точек. База: для одной точки утверждение очевидно.
  Шаг индукции. Пусть на плоскости нарисовано  n + 1  точек, некоторые пары из которых соединены отрезками. Рассмотрим одну из точек - A. На время забудем про неё и про выходящие из неё отрезки. По предположению индукции оставшиеся n точек можно покрасить в  k + 1  цвет таким образом, чтобы каждые две точки, соединённые отрезком, были покрашены в разные цвета. Покрасим эти n точек нужным образом. Вспомним про точку A. Она соединена отрезками не более, чем с k точками. Поскольку цветов  k + 1,  покрасим точку A в цвет, отличный от цветов точек, с которыми она соединена. Тем самым, получена требуемая раскраска точек.

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