Имеется куб размером 10×10×10, состоящий из маленьких единичных кубиков. В центре O одного из угловых кубиков сидит кузнечик. Он может прыгать в центр кубика, имеющего общую грань с тем, в котором кузнечик находится в данный момент; причём так, чтобы расстояние до точки O увеличивалось. Сколькими способами кузнечик может допрыгать до кубика, противоположного исходному?

   Решение

Ладья стоит на поле a1. За ход разрешается сдвинуть ее на любое число клеток вправо или на любое число клеток вверх. Выигрывает тот, кто поставит ладью на поле h8.

   Решение

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

   Решение

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

   Решение

Докажите, что существует граф с 2n вершинами, степени которых равны 1, 1, 2, 2, ..., n, n.

   Решение

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

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

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

Условие

Докажите, что существует граф с 2n вершинами, степени которых равны 1, 1, 2, 2, ..., n, n.

Подсказка

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

Решение

  Будем строить граф по индукции. База. Для  n = 1  такой граф существует: две вершины, соединённые ребром.
  Шаг индукции. Пусть граф с 2n вершинами и указанными степенями уже построен. Добавим к нему две вершины A и B. Вершину A соединим с n старыми вершинами со степенями 1, ..., n, а также с вершиной B. В результате у половины старых вершин степени не изменятся, у оставшихся – увеличатся на 1, степень A будет равна  n + 1,  а степень B будет равна 1. Это и есть искомый граф с  2n + 2  вершинами.

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