Хулиганы Джей и Боб на уроке черчения нарисовали головастиков (четыре окружности на рисунке - одного радиуса, треугольник - равносторонний, горизонтальная сторона этого треугольника - диаметр окружности). Какой из головастиков имеет бо'льшую площадь?

   Решение

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

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

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

Условие

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

Решение

  Индукция по числу городов. База очевидна.
  Шаг индукции. Удалим один из городов. В силу предположения индукции есть город А с требуемым свойством. Вспомним теперь про удалённый город. Если в него ведёт хотя бы одна дорога, то город А – искомый. В противном случае сам удалённый город удовлетворяет требуемому свойству.

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