Олимпиадные задачи по теме «Топология» для 10 класса - сложность 3 с решениями

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

Даны многоугольник, прямая <i>l</i> и точка <i>P</i> на прямой <i>l</i> в общем положении (то есть все прямые, содержащие стороны многоугольника, пересекают <i>l</i> в различных точках, отличных от <i>P</i>). Отметим те вершины многоугольника, для каждой из которых прямые, на которых лежат выходящие из неё стороны многоугольника, пересекают <i>l</i> по разные стороны от точки <i>P</i>. Докажите, что точка <i>P</i> лежит внутри многоугольника тогда и только тогда, когда по каждую сторону от <i>l</i> отмечено нечётное число вершин.

а) Электрическая схема имеет вид решётки 3×3: всего в схеме 16 узлов (вершины квадратиков решётки), которые соединены проводами (стороны квадратиков решётки). Возможно, часть проводов перегорела. За одно измерение можно выбрать любую пару узлов схемы и проверить, проходит ли между ними ток (то есть, проверить, существует ли цепочка неперегоревших проводов, соединяющая эти узлы). В действительности схема такова, что ток проходит от любого узла к любому. За какое наименьшее число измерений всегда можно в этом удостовериться? б) Тот же вопрос для решётки 7×7 (всего 64 узла).

а) Электрическая схема имеет вид решетки 3×3: всего в схеме 16 узлов (вершины квадратиков решётки), которые соединены проводами (стороны квадратиков решётки). Возможно, часть проводов перегорела. За одно измерение можно выбрать любую пару узлов схемы и проверить, проходит ли между ними ток (то есть, проверить, существует ли цепочка неперегоревших проводов, соединяющая эти узлы). В действительности схема такова, что ток проходит от каждого узла к любому другому. За какое наименьшее число измерений всегда можно в этом удостовериться? б) Тот же вопрос для решётки 5×5 (всего 36 узлов).

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

В игре Тантрикс-солитер возможны фишки 14 типов:<img src="/storage/problem-media/66767/problem_66767_img_2.png"> Каждую из них можно поворачивать, но нельзя переворачивать: именно поэтому первые 2 фишки разные – их нельзя получить друг из друга поворотом. Их разрешается прикладывать друг к другу так, чтобы линии одного цвета были продолжениями друг друга. У Саши было по одной фишке каждого типа, и он мог выложить их так, чтобы все синие линии образовывали «петлю», и при этом чтобы в картинке не было «дырок»: <img src="/storage/problem-media/66767/problem_66767_img_3.png"> Саша потерял фишку <img src="/storage/problem-media/66767/problem_66767_img_4.png">. Докажите, что теперь он не сможет выложить оставшиеся 13 фишек так, чтобы в картинке не...

В левой нижней клетке доски 100×100 стоит фишка. Чередуя горизонтальные и вертикальные ходы в соседнюю по стороне клетку (первый ход горизонтальный), она дошла сначала до левой верхней клетки, а потом до правой верхней. Докажите, что найдутся две такие клетки $A$ и $B$, что фишка не менее двух раз делала ход из $A$

в $B$.

Сколько (максимум) кругов можно расположить на плоскости так, чтобы каждые два из них пересекались, а никакие три – нет?