Клетчатые задачи

Пример. Для прямоугольника получаем

Оценка. Пусть в кроссворде клеток. Выберем некоторое его покрытие наименьшим количеством слов. Слова из этого покрытия назовём правильными, а остальные неправильными.

Каждая клетка содержится не более чем в одном горизонтальном и одном вертикальном слове. Хотя бы одно из этих слов правильное, так как правильные слова покрывают весь кроссворд. Значит, каждая клетка принадлежит не более чем одному неправильному слову. Поэтому сумма количеств клеток в неправильных словах не больше

Если клетка является словом, то к ней не примыкает другая клетка кроссворда ни по горизонтали, ни по вертикали. Следовательно, клетка входит в любое покрытие кроссворда словами и, значит, является правильным словом. Поэтому все неправильные слова содержат не меньше чем по две клетки и количество неправильных слов не больше

Так как правильные слова покрывают весь кроссворд, сумма количеств клеток в них не меньше Каждое слово содержит не больше клеток, поэтому количество правильных слов не меньше Отсюда

Рассмотрим центры клеток доски. Они образуют сетку со стороной Тогда ломанная из условия является целым многоугольником, у которого на границе узлов, а внутри узлов нет. По формуле Пика искомая площадь равна

Рассмотрим треугольник с вершинами в точках Заметим, что его площадь равна Легко проверить, что на его границе нет целых точек, кроме вершин. Тогда по формуле Пика получаем, что количество внутренних точек равно

Раскрасим доску в диагональную раскраску в три цвета. Заметим, что из цвета мы в любом случае идем в цвет с цвета — в цвет с цвета — на цвет Поскольку клеток цвета больше всех ( а не ), мы должны начать и закончить на цвете

Пример. На картинке показано, в каком порядке красить клетки: сначала красим все серые клетки, дальше в порядке возрастания номеров. Несложно видеть, что у каждой клетки с номером, начиная с не более одного соседа с бoльшим номером.

Оценка. Предположим, что клеток с числами, большими не более Тогда в них написаны числа, не превосходящие Заметим, что в последней закрашенной клетке написано число В остальных клетках написано число, не превосходящее Таким образом, сумма всех чисел не больше С другой стороны, сумма всех чисел равна количеству пар соседних чисел в таблице, то есть

Допустим, можно. Каждым ходом освобождается от шашек не более одной клетки. Так как вначале все клетки заняты, а в конце ровно 9999 клеток должны быть свободны, то никакая свободная клетка не должна быть повторно занята. На клетке , где собраны все шашки, пересекаются вертикаль и горизонталь. Ходы на делались только с этой вертикали и этой горизонтали, причем из каждой клетки не более одного раза. Число шашек, пришедших из клетки в , равно расстоянию между и . Сумма расстояний от всех клеток вертикали и горизонтали максимальна для угловой клетки X, она равна . Значит, включая шашку, стоявшую изначально на Ф, на этой клетке могло собраться не более 9901 шашки. Противоречие.

(a) Раскрасим клетки в шахматную раскраску. Заметим, что после команды все жуки из белых клеток переползут в чёрные, а из чёрных — в белые. На доске чёрных и белых клеток. Значит, какие-то два жука переползут из чёрных клеток в одну белую.

(b) Пометим клетки как показано на рисунке:

Из верхнего левого угла жук переползёт во вторую слева клетку четвёртой строки, а из верхнего правого угла — во вторую справа клетку четвёртой строки. Также понятно, что из средней клетки верхней строки жук переползёт либо во вторую слева, либо во вторую справа клетку в четвёртой строке, то есть в одной из этих клеток будет два жука.

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

Раскрасим доску в шахматную раскраску. Заметим, что фигура типа Т либо содержит одну белую и три чёрные клетки, либо наоборот. Предположим, что разрезать можно. Пусть всего фигур первого типа, тогда фигур второго — Количество белых клеток равно то есть оно нечётно. С другой стороны их а это чётное число, противоречие.

Раскрасим клетки второй, четвёртой и шестой строки в чёрный цвет. Заметим, что в одну букву Г входит либо одна, либо три чёрные клетки, то есть нечётное количество. Предположим, что разрезать можно. Всего будет фигур, то есть всего на доске нечётное количество (сумма нечётного количества нечётных чисел нечётна) чёрных клеток. Однако всего чёрных клеток, противоречие.

Пусть вырезан левый нижний уголок (не умаляя общности). Раскрасим клетки в чёрный цвет как показано на рисунке:

Нетрудно понять, что один прямоугольник не может содержать более одной чёрной клетки. Значит, потребуется хотя бы прямоугольника. Они займут хотя бы клеток, а это больше, чем то есть разрезать нельзя.

Замечание. Текст решения ниже написан с ориентиром на белую тему. В тёмной теме цвета надо поменять местами.

_________________________________________________________________________________________________________________________________________________________________________________

Раскрасим чёрным цветом клетки как показано на картинке:

Заметим, что каждый прямоугольник обязан содержать ровно одну чёрную клетку. Всего чёрных клеток. Значит ненакрытой останется какая-то чёрная клетка, а все белые точно будут накрыты.

А теперь покрасим в чёрный клетки по-другому:

Для этой раскраски справедливы вышеописанные рассуждения, то есть ненакрытая клетка является чёрной и на этом рисунке. Множества чёрных клеток с первой и второй картинки пересекаются по центральной клетке. Следовательно, ненакрытой может быть только она.

Осталось привести пример:

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

Следовательно, при каждом инвертировании цветов в квадрате на цвета в центральном квадрате на будут инвертироваться. Изначально в нём были белые клетки, значит они в нём будут при каждом очередном инвертировании, то есть чёрной доски мы не получим.

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

Приведём пример на нанесём удар по отмеченным клеткам:

Пронумеруем строки и столбцы от до и отметим на доске клетки, обе координаты которых делятся на Всего мы отметим клеток так как первая и вторая координата могут быть равны или Заметим, что король не может бить две отмеченных клетки. Значит нужно поставить хотя бы королей.

Осталось привести пример, поставив королей на отмеченные клетки:

Разобьём доску на фигурки следующим образом:

В трёхклеточных уголках и квадратах может быть не более двух закрашенных клеток.

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

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

С одной стороны, сумма всех чисел в таблице равна сумме чисел во всех строках, то есть она положительна. С другой стороны, эта сумма равна сумме чисел во всех столбцах, то есть она отрицательна, противоречие.

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

Разделим доску на четыре квадрата Обозначим через число ладей, которые стоят в левом верхнем квадрате. Левый и правый верхние квадраты образуют вместе верхних строк, следовательно, в них расположено ладей. Поэтому в правом верхнем квадрате расположено ладей. Аналогично вычисляется число ладей в левом нижнем квадрате — их тоже

Если число делится на то сумма его цифр делится на Пусть, для определённости, не делящееся на число стоит в верхней строке. Тогда сумма всех цифр в каждом столбце делится на Значит, сумма всех цифр в таблице делится на Вычтем из этой суммы сумму цифр четырёх чисел, стоящих в строках Результат делится на поскольку все вычитаемые делятся на Но, с другой стороны, это и есть сумма цифр, стоящих в верхней строке. Противоречие.