Несколько топологических и комбинаторных задач
Сборник задач (1–8) для семинара / кружка.
К некоторым задачам приложены сканы из книг и журнала Квант.
1. Две доски у входа в библиотеку
У входа в библиотеку висят две доски. Каждый человек,
входя в библиотеку, считает количество уже находящихся там людей
и записывает результат на первую доску;
выходя из библиотеки, каждый записывает на вторую доску
количество тех, кто ещё остался в библиотеке.
Докажите, что мульти множества чисел, появившихся на двух досках в течение дня, совпадают.
2. Покрашенные отрезки на ([0,1])
На отрезке длины (1) выбрано и покрашено несколько маленьких отрезочков.
Известно, что сумма длин покрашенных отрезков превосходит (1/2).
Докажите, что найдутся две покрашенные точки на расстоянии ровно (1/2).
3. Стрелки на доске (8\times 8)
В каждой клетке доски (8\times 8) стоит стрелочка одного из восьми направлений: на север, северо-восток, восток, юго-восток, юг, юго-запад, запад или северо-запад.
Известно, что в соседних по стороне клетках стрелочки отличаются не более чем на (45^\circ) (то есть направления либо совпадают, либо отличаются на одну «шаговую» восьмую окружности).
В некоторую клетку поставили человека; каждую секунду он идёт в ту клетку, на которую указывает стрелка в его текущей клетке.
Докажите, что рано или поздно он окажется на краю доски.
4. Буквы П, А, С в таблице (11\times 11)
Можно ли в клетках таблицы (11\times 11) так расставить буквы П, А, С, чтобы
- в верхней строчке таблицы было написано:
ПАПАСПАСПСА; - ни одна из остальных клеток, прилегающих к границе таблицы, не содержала бы букву С;
-
ни в одной фигурке вида
[ \lower1ex\hbox{\vbox{\lines2 _ || ||| }} \quad\text{или}\quad \lower1ex\hbox{\vbox{\lines2 _ _ ||| |_| }} ] не было трёх различных букв?
(В задаче упоминается также статья
https://arxiv.org/pdf/1712.03024.)
Сканы условия и решений:
5. Ориентация рёбер многогранника
На каждом ребре выпуклого многогранника поставлена стрелка так, что в каждую вершину многогранника входит и из каждой вершины выходит хотя бы одна стрелка.
Докажите, что существуют по крайней мере две грани многогранника, каждую из которых можно обойти по периметру, двигаясь в соответствии с направлениями стрелок на её сторонах.
6. Муравьи на гранях многогранника
По контуру каждой грани выпуклого многогранника ползает муравей (таким образом, муравьёв столько же, сколько граней), и все они движутся, обходя каждую свою грань по часовой стрелке. Известно, что их скорости в любой момент времени не меньше (1) мм/ч.
Докажите, что рано или поздно какие-то два муравья столкнутся.
Задача M1397. Условие и одно из решений — в Кванте 1994, №2:
7. Красные и синие векторы
Из одной точки на плоскости выходят (n) красных и (n) синих векторов. Красные векторы занумерованы первыми (n) натуральными числами.
В порядке нумерации каждый красный вектор поворачивается по часовой стрелке и занимает положение ближайшего свободного синего вектора так, что в конце концов красные векторы займут положения всех синих векторов (каждый красный переходит в положение своего «синего»).
Докажите, что сумма углов поворотов всех красных векторов не зависит от порядка нумерации красных векторов.
8. Сапоги в ряд
В ряд стоят (20) сапог: (10) правых и (10) левых.
Докажите, что найдутся (10) сапог, стоящих подряд, среди которых поровну правых и левых.