МАЛЫЙ МЕХМАТ МГУ

Кружок 8 класса

Занятие 13 (18 февраля 2017 года). Клеточки

1.

Можно ли расставить на бесконечном листе клетчатой бумаги крестики и нолики так, чтобы ни на одной горизонтали, вертикали или диагонали нельзя было встретить три одинаковых знака подряд?

2.

а)

В какое наибольшее количество цветов можно раскрасить клетки таблички 3×3 так, чтобы для любых двух цветов нашлись клетки этих цветов, имеющие общую сторону.

б)

В какое наименьшее количество цветов можно раскрасить клетки таблички 5× 5, если клетки, расположенные рядом, нельзя красить в один цвет.

3.

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

4.

Все клетки клетчатой плоскости окрашены в 5 цветов так, что в любой фигуре вида все цвета различны. Докажите, что и в любой фигуре вида все цвета различны.

5.

а)

Узлами клетчатой бумаги называются точки пересечения вертикальных и горизонтальных линий. Раскрасьте узлы бесконечной клетчатой бумаги в 4 цвета так, что на любом отрезке, соединяющем два одноцветных узла, лежит ещё хотя бы один узел.

б)

На клетчатой бумаге нарисован выпуклый n-угольник так, что его вершины лежат в узлах, а других узлов ни внутри него, ни на его сторонах нет. Чему может быть равно n? (Укажите все варианты.)

6.

Двое играют на треугольной доске (см. рисунок), закрашивая по очереди на ней треугольные клеточки. Одна клетка (начальная) уже закрашена перед началом игры. Первым ходом закрашивается клетка, граничащая (по стороне) с начальной, а каждым следующим ходом — клетка, граничащая с только что закрашенной. Повторно клетки красить нельзя.

а)

Кто из игроков может обеспечить себе победу, если начальная клетка — угловая?

б)

А если начальная клетка — та, что отмечена звёздочкой?

в)

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

г)

Может показаться, что в этой игре исход партии не зависит от поведения игроков. Покажите что это не так: приведите пример двух партий с одной и той же начальной клеткой, в одной из которых выигрывает первый игрок, а во второй — его партнёр.

Дополнительные задачи

7.

Коля и Витя играют в следующую игру на бесконечной клетчатой бумаге. Начиная с Коли, они по очереди отмечают узлы клетчатой бумаги, при этом каждый из них своим ходом должен отметить такой узел, что после этого все отмеченные узлы лежали в вершинах выпуклого многоугольника (начиная со второго хода Коли). Тот из играющих, кто не сможет сделать очередного хода, считается проигравшим. Кто из игроков может обеспечить себе победу?

8.

Бесконечную клетчатую доску раскрасили шахматным образом, и в каждую белую клетку вписали по отличному от нуля целому числу. После этого для каждой чёрной клетки посчитали разность: произведение того, что написано в соседних по горизонтали клетках, минус произведение того, что написано в соседних по вертикали. Могут ли все такие разности равняться 1?

9.

На бесконечном листе клетчатой бумаги (размер клетки 1×1) укладываются доминошки размером 1×2 так, что они накрывают все клетки. Можно ли при этом добиться того, чтобы любая прямая, идущая по линиям сетки, разрезала лишь конечное число костей?