Доказать, что существует бесконечно много натуральных чисел, не представимых в виде  p + n^2k  ни при каких простых p и целых n и k.

   Решение

AB и AC — две хорды, образующие угол BAC, равный 70^o. Через точки B и C проведены касательные до пересечения в точке M. Найдите BMC.

   Решение

Постройте хорду данной окружности, равную и параллельную заданному отрезку.

   Решение

Петя и Вася играют в игру на клетчатой доске n×n (где  n > 1).  Изначально вся доска белая, за исключением угловой клетки – она чёрная, и в ней стоит ладья. Игроки ходят по очереди. Каждым ходом игрок передвигает ладью по горизонтали или вертикали, при этом все клетки, через которые ладья перемещается (включая ту, в которую она попадает), перекрашиваются в чёрный цвет. Ладья не должна передвигаться через чёрные клетки или останавливаться на них. Проигрывает тот, кто не может сделать ход; первым ходит Петя. Кто выиграет при правильной игре?

   Решение

Что останется от прямоугольника? Золотой прямоугольник — это такой прямоугольник, стороны a и b которого находятся в пропорции золотого сечения, то есть удовлетворяют равенству a : b = b : (a - b). Представим, что такой прямоугольник вырезан из бумаги и лежит на столе, обращенный к нам своей более длинной стороной. Отсечем по левую сторону прямоугольника наибольший квадрат, который можно из него вырезать; остаток будет снова золотым прямоугольником. Далее становимся по левую сторону стола так, чтобы снова иметь перед собой более длинную сторону и поступаем с новым прямоугольником так же, как и с предыдущим. Таким образом обходим стол вокруг по направлению хода часовой стрелки и по очереди отсекаем квадраты. Каждая точка прямоугольника за исключением одной, будет раньше или позже отсечена. Определите положение этой исключительной точки.

   Решение

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

   Решение

Для каждого натурального n обозначим через  s(n)  сумму цифр его десятичной записи. Назовём натуральное число m особым, если его нельзя представить в виде  m = n + s(n).  (Например, число 117 не особое, поскольку  117 = 108 + s(108),  а число 121, как нетрудно убедиться, – особое.) Верно ли, что особых чисел существует лишь конечное число?

   Решение

В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать во всех городах, совершив не более  а) 198 перёлетов;  б) 196 перелётов.

   Решение

Темы:    [ Деревья ] [ Принцип крайнего (прочее) ] [ Индукция (прочее) ]

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

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

Условие

В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать во всех городах, совершив не более  а) 198 перёлетов;  б) 196 перелётов.

Решение

  б) Рассмотрим соответствующий граф и выделим из него максимальное дерево (см. задачу 30789 а).
  Докажем по индукции, что в дереве с n вершинами  (n > 2)  существует обходящий все вершины маршрут длины не более  2n – 4.  База  (n = 3)  очевидна.
  Шаг индукции. Рассмотрим висячую вершину А (см. задачу 30786) и удалим её и выходящее из неё ребро АВ. По предположению индукции в оставшемся дереве есть обходящий его маршрут длины  2n – 6.  Вставив в него кусок ВАВ получим маршрут длины  2n – 4,  обходящий исходное дерево.

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