Задача
Из клетчатого бумажного квадрата 100×100 вырезали по границам клеток 1950 доминошек (двуклеточных прямоугольников). Докажите, что из оставшейся части можно вырезать по границам клеток четырёхклеточную фигурку вида Т – возможно, повёрнутую. (Если такая фигурка уже есть среди оставшихся частей, считается, что её получилось вырезать.)
Решение
Решение 1: Представим себе, что доминошки (прямоугольники 1×2) ещё не вырезаны, и будем вырезать их по одной. В каждый момент процесса назовём ценой ещё не вырезанной клетки число её невырезанных соседей по стороне, уменьшенное на 2 (например, цена неугловой клетки, лежащей на границе квадрата, изначально равна 1). Тогда исходная цена каждой клетки есть 2 – t, где t – количество отрезков периметра квадрата, находящихся на границе этой клетки. Значит, исходная суммарная цена всех клеток равна 2·1002 – 400 = 19600.
Проследим, как изменяется суммарная цена S всех невырезанных клеток после вырезания доминошки. При этом выкидываются две клетки (сумма цен которых не превосходит 2 + 2 = 4), а также уменьшаются на 1 цены клеток, граничащих с доминошкой (а их не больше шести). Поэтому после вырезания доминошки S уменьшается не более, чем на 10.
Итак, после вырезания 1950 доминошек S будет не меньше, чем 19600 – 1950·10 = 100. Поэтому найдётся невырезанная клетка k, цена которой положительна. Это значит, что у k не менее трёх невырезанных соседей. Тогда k вместе с этими тремя соседями образует требуемую фигурку.
Решение 2: Назовём требуемую фигурку T-тетрамино. Разобьём наш квадрат на фигурки (см. рис.). Нетрудно подсчитать, что вне "полных" крестов окажется ровно 4·100 = 400 клеток, из которых 320 будут находиться в T-тетрамино разбиения. Итого, в разбиении есть (100² – 400) : 5 = 1920 полных крестов и ещё 80 T-тетрамино.

Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь