Пусть A₁ и B₁ — проекции точки P описанной окружности треугольника ABC на прямые BC и AC. Докажите, что длина отрезка A₁B₁ равна длине проекции отрезка AB на прямую A₁B₁.

   Решение

В каждом из $16$ отделений коробки $4\times 4$ лежит по золотой монете. Коллекционер помнит, что какие-то две лежащие рядом монеты (соседние по стороне) весят по $9$ грамм, а остальные по $10$ грамм. За какое наименьшее число взвешиваний на весах, показывающих общий вес в граммах, можно определить эти две монеты?

   Решение

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

   Решение

Существует ли вписанный в окружность $19$-угольник, у которого нет одинаковых по длине сторон, а все углы выражаются целым числом градусов?

   Решение

Гриша записал на доске 100 чисел. Затем он увеличил каждое число на 1 и заметил, что произведение всех 100 чисел не изменилось. Он опять увеличил каждое число на 1, и снова произведение всех чисел не изменилось, и так далее. Всего Гриша повторил эту процедуру k раз, и все k раз произведение чисел не менялось. Найдите наибольшее возможное значение k.

   Решение

Куб со стороной 1 м распилили на кубики со стороной 1 см и положили их в ряд (по прямой). Какой длины оказался ряд?

   Решение

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

   Решение

Темы:    [ Обход графов ] [ Деревья ] [ Четность и нечетность ] [ Индукция (прочее) ]

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

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

Условие

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

Решение

  Разберём случай, когда граф не имеет нечётных вершин. Индукцией по числу рёбер графа докажем, что его можно обойти по циклу. База (граф без рёбер) очевидна.
  Шаг индукции. Рассмотрим произвольный связный граф, степени всех вершин которого чётны. Поскольку в этом графе нет висячих вершин, то он не является деревом, и, следовательно, в нём есть простой цикл. Временно удалим из графа рёбра этого цикла. При этом граф распадётся на несколько компонент связности, имеющих общие вершины с выкинутым циклом. В каждой компоненте все вершины чётны, и по предположению индукции каждую из этих компонент связности можно обойти по циклу. Теперь ясно как обойти требуемым образом исходный граф: обходим цикл и попадая в вершину, относящуюся к какой-то компоненте, обходим её, в конце возвращаясь в ту же вершину, после чего продолжаем движение по циклу.
  Доказательство для случая графа с двумя нечётными вершинами аналогично (нужно временно удалить путь, соединяющий две нечётные вершины).

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