Версия для печати
Убрать все задачи

---

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

   Решение

---

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

   Решение

---

Пусть p – простое число и  p > 3.
  а) Докажите, что если разрешимо сравнение  x² + x + 1 ≡ 0 (mod p),  то  p ≡ 1 (mod 6).
  б) Выведите отсюда бесконечность множества простых чисел вида  6k + 1.

   Решение

---

Пусть p – простое число и  p > 5.  Докажите, что если разрешимо сравнение  x⁴ + x³ + x² + x + 1 ≡ 0 (mod p),  то   p ≡ 1 (mod 5).
Выведите отсюда бесконечность множества простых чисел вида  5n + 1.

   Решение

---

Имеется 20 человек – 10 юношей и 10 девушек. Сколько существует способов составить компанию, в которой было бы одинаковое число юношей и девушек?

   Решение

---

Во время шахматного турнира, несколько игроков сыграли нечётное количество партий. Докажите, что число таких игроков чётно.

   Решение

---

Пусть a и k > 0 произвольные числа. Определим последовательность {a_n} равенствами

Докажите, что при любом неотрицательном n выполняется равенство

   Решение

---

В углах шахматной доски 3×3 стоят четыре коня: два белых (в соседних углах) и два чёрных.
Можно ли за несколько ходов поставить коней так, чтобы во всех соседних углах стояли кони различного цвета?

   Решение

---

На плоскости нарисовано несколько точек, некоторые пары точек соединены отрезками. Известно, что из каждой точки выходит не более k отрезков. Докажите, что точки можно покрасить в  k + 1  цвет таким образом, чтобы каждые две точки, соединенные отрезком, были покрашены в разные цвета.

   Решение

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

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

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

Условие

На плоскости нарисовано несколько точек, некоторые пары точек соединены отрезками. Известно, что из каждой точки выходит не более k отрезков. Докажите, что точки можно покрасить в  k + 1  цвет таким образом, чтобы каждые две точки, соединенные отрезком, были покрашены в разные цвета.

Подсказка

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

Решение

  Индукция по числу точек. База: для одной точки утверждение очевидно.
  Шаг индукции. Пусть на плоскости нарисовано  n + 1  точек, некоторые пары из которых соединены отрезками. Рассмотрим одну из точек - A. На время забудем про неё и про выходящие из неё отрезки. По предположению индукции оставшиеся n точек можно покрасить в  k + 1  цвет таким образом, чтобы каждые две точки, соединённые отрезком, были покрашены в разные цвета. Покрасим эти n точек нужным образом. Вспомним про точку A. Она соединена отрезками не более, чем с k точками. Поскольку цветов  k + 1,  покрасим точку A в цвет, отличный от цветов точек, с которыми она соединена. Тем самым, получена требуемая раскраска точек.

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