Докажите, что геометрическое место точек M, cтепень которых относительно окружностей S₁ и S₂ одинакова, является прямой.
Такая прямая называется радикальной осью окружностей S₁ и S₂.

   Решение

В языке Древнего Племени алфавит состоит всего из двух букв: М и О. Два слова являются синонимами, если одно из другого можно получить при помощи
  а) исключения буквосочетаний МО или ООММ,
  б) добавления в любое место буквосочетания ОМ.
Являются ли синонимами в языке Древнего Племени слова ОММ и МОО?

   Решение

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

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

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

Условие

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

Решение

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

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