Всем Успехов на ЕГЭ!

[wpoms.]

На экране компьютера показана шахматная доска размером $98 \times 98,$ окрашенная обычным образом. С помощью мышки можно выделить любой прямоугольник, стороны которого идут по линиям сетки, и кликнуть по нему. После этого цвета внутри прямоугольника меняются: черное становится белым, белое --- черным. Найдите наименьшее количество кликов мышкой, необходимое для того, чтобы вся доска стала одноцветной.

@темы: Дискретная математика

---

Бинарные последовательности

[wpoms.]

В $n$-элементной последовательности $(x_1, x_2, \ldots, x_n)$ каждый элемент равен 0 или 1. Назовем такую последовательность бинарной последовательностью длины $n$. Пусть $a_n$ равно равно количеству бинарных последовательностей длины $n,$ не содержащих трёх последовательных членов равных 0, 1, 0 (в этом порядке). Пусть $b_n$ равно количеству бинарных последовательностей длины $n,$ не содержащих четырёх последовательных членов равных 0, 0, 1, 1 или 1, 1, 0, 0 (в этом порядке). Докажите, что $b_{n+1} = 2a_n$ для всех положительных целых чисел $n.$

@темы: Дискретная математика, Теория чисел

---

Про друзей

[wpoms.]

Предположим, что о каждой паре людей из некоторого сообщества можно сказать, что она состоит из друзей или врагов. Каждый член дружественной пары дружит с другим членом этой пары, а каждый член враждебной пары враждует с другим членом этой пары. Рассмотрим сообщество из $n$ людей, в котором $q$ пар друзей и в котором в любой группе, состоящей из трех членов сообщества, есть по крайней мере одна пара врагов. Докажите, что есть по крайней мере один член сообщества такой, что среди его врагов есть $\, q(1 - 4q/n^2)$ или меньше пар друзей.

@темы: Дискретная математика

---

Связь между параметрами множества

[wpoms.]

Пусть $|U|, \sigma(U)$ и $\pi(U)$ обозначают соответственно количество, сумму и произведение элементов конечного множества положительных целых чисел $U.$ (Если $U$ является пустым множеством, то считаем что $|U| = 0, \sigma(U) = 0, \pi(U) = 1.$) Пусть $S$ --- конечное множество положительных целых чисел. Как обычно, пусть $C_n^k$ обозначает $\frac{n!}{k! \, (n-k)!}.$ Докажите, что $\sum_{U \subseteq S} (-1)^{|U|} C_{m - \sigma(U)}^{|S|} = \pi(S)$ для всех целых чисел $m \geq \sigma(S).$

@темы: Дискретная математика, Теория чисел

---

Раскраска

[wpoms.]

Стороны $99$-угольника сначала покрасили так, что последовательные стороны окрашены в красный, синий, красный, ..., красный, синий, желтый цвет. Выполняется последовательность изменения цвета сторон, по одной стороне за раз. Стороны окрашиваются в красный, синий или желтый цвет при условии, что никакие две смежные стороны не будут иметь одинаковый цвет. Может ли после выполнения подобных перекрашиваний получиться так, что последовательные стороны будут окрашены в красный, синий, красный, ..., красный, желтый, синий цвет?

@темы: Дискретная математика

---

Точки пересечения

[wpoms.]

На окружности отметили 2021 точку и провели 2021 отрезок с концами в отмеченных точках. После этого вычислили количество различных точек, в которых пересекаются проведённые отрезки (концы отрезков не считаются точками пересечения). Найдите наибольшее количество точек пересечения, которое могло получиться.

@темы: Дискретная математика

---

Про Z-тетрамино

[wpoms.]

Клетчатую доску размера $2022 \times 2022$ разрезали на фигуры двух видов: L-тетрамино и Z-тетрамино. Каждое тетрамино состоит из четырёх единичных квадратов, тетрамино можно поворачивать и переворачивать. Определите, какое наименьшее количество Z-тетрамино могло получиться.

@темы: Дискретная математика

---

Игра

[wpoms.]

Дана клетчатая доска размера $3 \times 2021,$ все клетки которой покрашены в белый цвет. Два игрока по очереди перекрашивают в чёрный цвет две не обязательно соседние белые клетки, расположенные либо в одной строке, либо в одном столбце. Игрок, который не может сделать ход, проигрывает. Кто из игроков может обеспечить себе выигрыш вне зависимости от игры соперника?

@темы: Дискретная математика

---

Ожерелья

[wpoms.]

Пусть ожерелье $A$ состоит из 14 бусин, а ожерелье $B$ из 19. Докажите, что для любого нечетного числа $n \geq 1$ можно пронумеровать каждую из 33 бусин так, чтобы по одному разу были использованы все числа $\{ n, n+1, n+2, \ldots, n+32 \}$ и соседние бусины были пронумерованы взаимно простыми числами. (Здесь ожерелье рассматривается как окружность, на которой каждая бусина имеет двух соседей.)

@темы: Дискретная математика

---

Найдутся

[wpoms.]

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

@темы: Дискретная математика

---

Не геометрия

[wpoms.]

Треугольник разделили на девять маленьких треугольников и написали в каждой из десяти вершин число 0. За один ход можно выбрать один из девяти треугольников и либо увеличить все числа в его вершинах на 1, либо уменьшить их на 1. На рисунке показана ситуация после возможного первого хода. Число $n$ назовем доминантным, если возможно из начального положения, выполняя описанные ранее шаги, получить конфигурацию, в которой в вершинах написаны последовательные числа и большее из них равно $n.$ Найдите все доминантные числа.

@темы: Дискретная математика

---

Раскраска

[wpoms.]

Сколькими способами можно покрасить клетки шахматной доски размером `m xx n,` так, что каждая клетка покрашена в один из четырёх цветов и в каждом квадрате `2xx2` есть клетки четырёх разных цветов?

@темы: Дискретная математика, Комбинаторика

---

Стражи

[wpoms.]

Директор музея распорядился выставить около наиболее ценного экспоната постоянную охрану. Известно, что каждый стражник охраняет экспонат в течении 7 часов, после этого уходит и возвращается на службу в то же время, что и накануне, и снова 7 часов дежурит около экспоната и так далее. Стражник называется незаменимым, если какое-то время он охраняет экспонат один. Найдите все возможные значения количества стражников, если все они являются незаменимыми.

@темы: Дискретная математика