close

Вход

Забыли?

вход по аккаунту

?

Клетчатые доски

код для вставки
КЛЕТЧАТЫЕ ДОСКИ В ОЛИМПИАДНЫХ ЗАДАЧАХ.
Задачи, в которых рассматриваются фигурки, составленные из клеток, разнообразны по
содержанию и методам решения. Иногда в них может идти речь о разрезаниях клетчатой фигуры
на более мелкие части определенного вида. При разрезании или замощении ставится вопрос о его
возможности, его свойствах, о количестве фигурок каждого вида, их ориентации и т.п. В
некоторых случаях предлагается какая-нибудь операция, производимая с частью клеток с целью
получить новую их расстановку. При решении таких задач обычно используются различные
раскраски, которые помогают либо построить требуемый пример, либо доказать невозможность
это сделать. Кроме раскрасок бывают нужны дополнительные соображения, использующие
инвариант, принцип Дирихле, подсчеты разными способами и т.д. Здесь мы рассмотрим лишь
некоторые задачи такого типа, но даже в этом небольшом наборе можно увидеть разнообразие и
привлекательность этой темы.
Пример 1. Из шахматной доски вырезали две угловые клетки. Можно ли покрыть
оставшиеся клетки доски доминошками («доминошка» – прямоугольник, покрывающий две
соседние по стороне клетки), если это
а) угловые клетки, примыкающие к одной стороне доски;
б) угловые клетки на диагонали доски?
Решение. а) Легко привести пример покрытия доски с вырезанными угловыми клетками на
одной ее стороне (рис. а)).
б) В этом случае покрытие невозможно. Доказать это можем, используя шахматную раскраску
доски (рис. б)). При таком вырезании на доске останется 30 черных клеток и 32 белых. Каждая
доминошка обязательно накрывает одну черную клетку и одну белую. Поскольку черных и белых
клеток не поровну, покрыть такую доску не получится.
Пример 2. Можно ли прямоугольник а) 5 6 ; б) 311
разрезать на трехклеточные
уголки?
Решение. а) Разрезать можно, один из примеров показан на рисунке.
б) Закрасим клетки верхней и нижней строки через одну, как показано на рисунке
(разреженная шахматная раскраска). Если вырезать любой трехклеточный уголок, он не может
одновременно содержать сразу две окрашенные клетки. Это означает, что если разрезание
возможно, трехклеточных уголков получится не менее 12 (по количеству окрашенных клеток). Во
всем прямоугольнике 33 клетки. Его можно разрезать только на 11 трехклеточных фигур. Значит,
требуемое разрезание невозможно.
Пример 3. Можно ли доску 66 разрезать на прямоугольники 14?
Решение. В квадрате 66 всего 36 клеток. Из 36 клеток могло бы
получиться 9 прямоугольников 14. Если применить диагональную
раскраску, как показано на рисунке, понятно, что прямоугольник 14 при
любом вырезании содержит ровно одну окрашенную клетку. Всего таких
клеток 10. Чтобы они все оказались вырезаны, потребуется 10
прямоугольников, а их только 9. Такое разрезание невозможно.
Пример 4. Фигуру на рисунке разрезали на трёхклеточные и четырёхклеточные уголки,
нарисованные справа от неё. Сколько трёхклеточных уголков могло получиться?
Решение. Фигура состоит из 22 клеток. Если при разрезании получилось x трёхклеточных
уголков и
y четырёхклеточных, то 3x  4 y  22 .
Очевидно, что число x чётно и x  8 , так что x может
быть равно 0, 2, 4 или 6. Ни 0, ни 4 не подходят: y
должно быть целым. При x  2 получаем y  4 , а при
x  6 получаем y  1 . Оба случая возможны, как
показано на рисунках.
Ответ: 2 или 6.
Пример 5. Прямоугольник 3 7 разрезали на трехклеточные и четырехклеточные уголки.
Сколько четырехклеточных уголков могло получиться?
Решение. Прямоугольник содержит 21 клетку, поэтому количество трехклеточных уголков
х и количество четырехклеточных уголков у удовлетворяют равенству 3x  4 y  21 . Решая
это уравнение в натуральных числах получаем две возможности: x  7; y  0 или x  3; y  3 .
Следовательно, количество четырехклеточных уголков должно быть либо 0, либо 3. Проверим
каждый из этих случаев.
Применим разреженную шахматную раскраску (рис. а)). Каждый трехклеточный уголок
накрывает не более одной окрашенной клетки. Если бы прямоугольник можно было
разрезать только на такие уголки, их было бы не менее 8, что невозможно. Случай, когда
каждого вида уголков по 3, показан на рисунке б). Таким образом, четырехклеточных
уголков было 3.
Ответ: 3.
Пример 6. Прямоугольник 7 11 разрезали на квадраты 2  2 и трехклеточные уголки.
Сколько всего фигур могло получиться?
Решение. Применим разреженную шахматную раскраску (см. рис. а)). Всего получилось 24
окрашенных клетки. Квадрат 2  2 или трехклеточный уголок содержит не более одной
окрашенной клетки. Значит, при разрезании получилось не менее 24 частей.
а)
Пусть уголков было х, а квадратов – у. Тогда 3x  4 y  77 . Решая это уравнение в
натуральных числах, будем учитывать, что x  y  24 . Подходят только два решения:
x  23; y  2 и x  19; y  5 . Оба эти варианта возможны (см. рис. б) и в)).
Ответ: 24 или 25.
Пример 7. Из квадрата 5  5 удалили одну клетку так, что оставшуюся часть можно
разрезать на полоски размером 1 3 . Какую клетку удалили (указать все возможные
расположения)?
Решение. После удаления одной клетки останется еще 24, то есть после разрезания
получится восемь полосок 1 3 . Раскрасим клетки так, как на рисунке а). Каждая полоска
1 3 накрывает ровно одну закрашенную клетку. Но закрашенных клеток девять,
следовательно, одна из них останется непокрытой, то есть вырезанная клетка находится на
месте одной из закрашенных.
Раскрасим клетки квадрата 5  5 снова так, как на рисунке б). Рассуждая точно так же,
получаем, что вырезанная клетка находится на месте одной из закрашенных на рисунке б).
Одновременно закрашенной на обоих рисунках является только центральная клетка,
следовательно, если такое разрезание возможно, удаленной должна быть только она. Пример
разрезания показан на рисунке в).
Пример 8. Какое наибольшее количество фигурок в виде пятиклеточного креста можно
вырезать по линиям сетки из квадрата 7  7 ?
Решение. Идея решения – «анализ края». Рассмотрим заштрихованные на рисунке а)
клетки. Среди этих семи клеток не более двух могут оказаться в вырезанных крестах.
Действительно, заштрихованные клетки примыкают к краю квадрата, поэтому, те из них,
которые принадлежат вырезанным крестам, находятся друг от друга на расстоянии по
крайней мере двух клеток, причем угловые клетки не входят в кресты. Во всей выделенной
кайме тогда не более восьми клеток, принадлежащих крестам, следовательно в этой кайме не
менее 16 не вырезанных клеток. Следовательно, из 49 клеток квадрата на кресты приходятся
не более 33. Значит, больше шести таких фигурок вырезать не удастся. Пример на рисунке
б) показывает, как можно вырезать шесть таких фигурок.
Пример 9. Клетчатый прямоугольник разрезали по линиям сетки на
шестиклеточные фигурки, показанные на рисунке и нечетное число
отдельных клеточек. Какое наименьшее число отдельных клеточек могло
при этом оказаться?
Решение. Поскольку фигурки шестиклеточные, а количество отдельных клеточек нечетно,
площадь прямоугольника должна быть нечетной, то есть обе его стороны – нечетные.
Фигурка может примыкать к стороне прямоугольника либо двумя клетками, либо четырьмя
(см. рисунок а)), поэтому стороны прямоугольника не короче трех и к каждой из них
примыкает отдельная клетка. Одна клетка может примыкать одновременно только к двум
сторонам, поэтому отдельных клеток не менее трех.
Пример с тремя отдельными клетками показан на рисунке б).
Пример 10. Любые два столбца или любые две строки шахматной доски размерами 88
разрешается поменять местами. Можно ли после нескольких таких операций получить доску,
вся левая половина которой состоит из белых клеток, а правая – из черных?
Решение. Указанная операция сохраняет количество белых и черных клеток в каждом
столбце и каждой строке. Поэтому, нельзя получить доску, в которой какой-нибудь столбец
состоит, например, только из белых клеток, значит, нельзя получить доску, требуемую в
условии.
Пример 11. Можно ли покрасить некоторые клетки квадрата 5  5 так, чтобы в любом
квадрате 2  2 было ровно 2 закрашенные клетки, а в каждом прямоугольнике 1 3 - ровно 1
закрашенная клетка?
Решение. Предположим, что такая раскраска возможна. Тогда в квадрате 5  5 может быть
либо 8, либо 9 окрашенных клеток.
Действительно, на первом рисунке видно,
что в восьми прямоугольниках 1 3
содержится 8 окрашенных клеток. Если
центральная клетка квадрата 5  5 при
этом тоже окрашена, то всего окрашенных
клеток девять, если нет – то восемь. С
другой стороны, окрашенных клеток в
квадрате 5  5 должно быть не меньше
десяти. На втором рисунке видно, что в
квадратах 2  2 содержится восемь окрашенных клеток и в двух прямоугольниках 1 3 - еще
два. Полученное противоречие доказывает, что такая раскраска невозможна.
Ответ: нельзя.
Пример 12. Можно ли в квадрате 5  5 закрасить 16 клеток так, чтобы в любом квадрате
2  2 было закрашено не более двух клеток?
Решение. 1-й способ. Предположим, что можно. Тогда в выделенном на рисунке
квадрате 4  4 закрашено не более 8 клеток (он разбивается на 4
квадрата 2  2 , в каждом из которых не более двух закрашенных клеток).
Значит, в отдельном уголке, состоящем из нижней строки и правого
столбца, должно быть не менее 8 закрашенных клеток. Но в этом уголке
всего 9 клеток, и все они не могут быть окрашены (тогда в квадрате
2  2 , находящемся в правом нижнем углу, будут окрашены не менее трех
клеток). Значит, в этом уголке 8 закрашенных клеток – либо все, кроме
правого нижнего угла, либо кроме одной из примыкающих к нему
клеток. Это означает, что каждая из клеток, отмеченных звездочкой, входит в квадрат 2  2 ,
уже имеющий две закрашенные клетки. Значит, все эти клетки не закрашены. Следовательно,
в левом верхнем квадрате 3  3 окрашены ровно 8 клеток. Но в нем всего 9 клеток. Это
означает, что в нем найдутся квадраты 2  2 с тремя закрашенными клетками, что
противоречит условию.
2-й способ. Можно закончить решение и по-другому. Точно так же, как получено, что в
правом нижнем девятиклеточном уголке не более
одной незакрашенной клетки, можно доказать, что и в
левом верхнем девятиклеточном уголке не более
одной незакрашенной клетки (см. следующий рисунок).
Тогда в рамке из 16 клеток (на следующем рисунке)
не более двух чистых клеток. Всего в этой рамке
четыре неперекрывающихся трехклеточных уголка,
значит, хотя бы один из них окрашен полностью.
Следовательно, в квадрате, содержащем этот уголок, закрашено более двух клеток.
3-й способ. Разрежем квадрат 5  5 на части так, как показано на рисунке.
Тогда в каждом из четырех квадратов не более двух окрашенных клеток,
а в двух оставшихся фигурах не менее 8 окрашенных клеток (такое же
рассуждение было в первом решении). Поскольку две эти фигуры вместе
состоят из 9 клеток, то на них приходится не более одной чистой
клетки. Это означает, что хотя бы в одной из двух фигур закрашены все
клетки, то есть имеется окрашенный трехклеточный уголок.
Ответ: нельзя.
Упражнения для тренировки.
1. Можно ли доску а) 88 ; б) 1010
показанные на рисунке?
разрезать на четырехклеточные фигурки,
2. Можно ли доску а) 68 ; б) 66 разрезать на четырехклеточные фигурки, показанные
на рисунке?
3. Можно ли прямоугольник 59 разрезать на трехклеточные уголки?
4. Фигуру, изображенную
на
рисунке (квадрат 55 с
удаленными четырьмя клетками в серединах сторон),
разрезали на части в виде доминошек и трехклеточных
уголков. Сколько всего получилось таких частей?
5. Квадрат 77 разрезали на трехклеточные уголки и пятиклеточные кресты. Сколько всего
частей могло получиться?
6. В прямоугольнике 67 закрашены какие-то 25 клеток. Доказать, что можно найти квадрат
22, в котором закрашено не менее трех клеток.
7. Клетки квадрата 100 100 раскрашены в шахматном порядке. Квадрат разрезали на
квадраты с нечетными длинами сторон, и в каждом квадрате отметили центральную клетку.
Доказать, что белых и черных клеток отмечено поровну.
8. Можно ли покрасить некоторые клетки квадрата 5  5 так, чтобы в любом квадрате 2  2
было ровно 2 закрашенные клетки, а в каждом прямоугольнике 1 3 - ровно 1 закрашенная
клетка?
9. От квадратной доски 10011001 отрезали четыре угловых квадрата 2  2 . Можно ли
оставшуюся часть разбить на фигурки, показанные на рисунке?
10. В клетчатом прямоугольнике размером 5  7 произвольно окрасили 22 клетки. Доказать,
что при этом будет окрашен трехклеточный уголок.
11. В клетчатом квадрате размером 7  7 произвольно окрасили 29 клеток. Всегда ли при
этом будет окрашен трехклеточный уголок?
12. На
клетки
любого
черный
клетчатой доске 88 окрашены в черный цвет произвольные 7 клеток, остальные
белые. За одну операцию можно перекрасить в противоположный цвет клетки
квадрата 2  2 . Можно ли за несколько таких операций покрасить всю доску в
цвет?
Решение упражнений для тренировки.
1. а) Доску 88 можно разрезать на квадраты 44, а каждый из них разбить так, как показано на
рисунке.
б) Доску 1010 на такие фигурки разрезать нельзя. Докажем это от противного.
Если бы разрезание было возможно, таких фигурок получилось бы 25. Применим
шахматную раскраску данной доски и получим 50 белых клеток и 50 черных
(четное количество и тех, и других). Как бы ни вырезали фигурку, в ней будет
три клетки одного цвета и одна другого (нечетное количество и тех, и других).
Например, проследим за количеством белых клеток во всех полученных фигурках. Поскольку
фигурок 25, а в каждой из них нечетное количество белых клеток, всего белых клеток будет
нечетное количество. Но на самом деле их 50. Полученное противоречие показывает, что такое
разрезание невозможно.
2. а) Доску 612 можно разрезать на прямоугольники 42, а каждый из них разбить так, как
показано на рисунке.
б) Доску 66 на такие фигурки разрезать нельзя. Докажем это от противного. Если бы
разрезание было возможно, таких фигурок получилось бы 9. Применим
полосатую раскраску данной доски и получим 18 белых клеток и 18
черных (четное количество и тех, и других). Как бы ни вырезали
фигурку, в ней будет три клетки одного цвета и одна другого (нечетное
количество и тех, и других). Например, проследим за количеством белых клеток во
всех полученных фигурках. Поскольку фигурок 9, а в каждой из них нечетное
количество белых клеток, всего белых клеток будет нечетное количество. Но на
самом деле их 18. Полученное противоречие показывает, что такое разрезание
невозможно.
3. Применим разреженную шахматную раскраску, как в примерах 2, 5 и 6. Всего клеток 45, из них
закрашенных – 15. Если разрезание возможно, фигурок тоже
будет 15. Значит, в каждый уголок обязательно входит
закрашенная клетка. Попытаемся построить пример. Это не так
легко, как в примере 2. Там весь прямоугольник разбивался на
блоки 23, каждый из которых разрезается на два уголка. При
построении примера следим за попаданием в каждый уголок
закрашенной клетки. Убеждаемся, что такое разрезание
возможно.
4. Фигура содержит 21 клетку, поэтому, если уголков было х, а доминошек – у, то 3x  2 y  21 .
Решая это уравнение в натуральных числах, получаем: x  7; y  0 , x  5; y  3 ; x  3; y  6 или
x  1; y  9 . Рассмотрим все эти варианты.
Если раскрасить фигуру в шахматном порядке, как на рисунке а), то белых клеток будет
12, а черных – 9. Если бы можно было разрезать фигуру на 9 доминошек и трехклеточный
уголок, получилось бы, что все клетки уголка должны быть белыми, что невозможно.
Разрезать фигуру только на уголки тоже нельзя. Каждую из четырех угловых клеток
накрывает уголок только в таком расположении, как показано на рисунке б). Тогда
центральный квадрат 33
необходимо разрезать на три трехклеточных уголка. Но это
невозможно, поскольку каждую из окрашенных клеток содержит не более одного уголка, а
таких клеток четыре.
Случаи, когда x  5; y  3 ; x  3; y  6 возможны (см. рис. в) и г)). Общее количество частей
при этом либо 8, либо 9.
Ответ: 8 или 9.
5. Пусть уголков было х, а пятиклеточных фигур – у. Тогда получаем, что 3x  5 y  49 . Решая
это уравнение в натуральных числах, получаем следующие варианты: x  3; y  8 , x  8; y  5 ,
x  13; y  2 . Первый из них невозможен, поскольку никакой крест не может содержать
угловую клетку квадрата. Угловых клеток всего четыре, а трехклеточных уголков всего три,
при этом ни один из них не может содержать две угловые клетки квадрата. Два остальных
случая возможны (см. рис.)
Ответ: 13 или 15.
6. Предположим, что в любом квадрате 22 закрашено менее трех клеток, то есть не более
двух. Выделим в прямоугольнике 67 девять квадратов 22, как показано на рисунке. По
предположению, они содержат не более 18 окрашенных клеток.
Следовательно, оставшаяся полоска 61 должна содержать не менее 7  25  18  7 
окрашенных клеток. Но в полоске всего 6 клеток. Полученное противоречие доказывает
утверждение.
7. В квадрате с черным центром черных клеток на одну больше, чем белых, а в квадрате с
белым центром белых клеток на одну больше, чем черных. Если рассматривать квадраты без
центральных клеток, общее количество белых клеток равно общему количеству черных.
Исходная доска тоже имела поровну клеток каждого цвета. Значит, среди центров
полученных квадратов черных и белых клеток также поровну.
8. Предположим, что такая раскраска возможна. Тогда в квадрате 5  5 может быть либо 8,
либо 9 окрашенных клеток. Действительно, на первом рисунке видно, что в восьми
прямоугольниках 1 3 содержится 8 окрашенных клеток. Если центральная клетка квадрата
5  5 при этом тоже окрашена, то всего окрашенных клеток девять, если нет – то восемь. С
другой стороны, окрашенных клеток в квадрате 5  5 должно быть не меньше десяти. На
втором рисунке видно, что в квадратах 2  2 содержится восемь окрашенных клеток и в
двух прямоугольниках 1 3 - еще два. Полученное противоречие доказывает, что такая
раскраска невозможна.
Ответ: нельзя.
9. Предположим, что доску разбить можно. Раскрасим ее в три цвета в полоску: первую,
четвертую, седьмую и т.д. строки – в первый цвет; вторую, пятую, восьмую и т.д. – во второй
цвет; третью, шестую, девятую и т.д. – в третий цвет. При этом в каждой фигурке разбиения
будут присутствовать все три цвета, причем клеток каждого цвета – нечетное количество
(либо одна, либо три). Клеток первого цвета 997  2  1001 332 - четное количество, значит,
фигурок разбиения должно быть тоже четное количество. Клеток третьего цвета 1001 333 нечетное число, то есть и фигурок разбиения должно быть нечетное число. Противоречие
показывает, что такое разбиение невозможно.
Ответ: нет.
10. Предположим, что ни одного окрашенного уголка не образовалось. Разобьем
прямоугольник на части так, как показано на рисунке. Если в каждом
квадрате 2  2 окрашено не более двух клеток, во всех шести таких
квадратах их окрашено не более 12. Значит, в остальных трех фигурах
окрашенных клеток не менее 10  22  12  10  . Вместе эти фигуры состоят
из 11 клеток, следовательно, чистых (неокрашенных) клеток в этой части не
более одной. Значит, по крайней мере в двух из этих трех фигур все клетки окрашены. То
есть, хотя бы один из трехклеточных уголков, заштрихованных на рисунке, должен быть
полностью окрашен.
11. Если применить полосатую раскраску, как в задании 2, то при 28 окрашенных клетках не
образуется ни одного трехклеточного уголка. Предположим, что ни один
такой уголок не получится и при 29 окрашенных клетках. Сделаем
7  7 на фигуры, как показано на рисунке. По
разбиение квадрата
предположению все девять квадратов содержат не более 18 закрашенных
клеток. Значит, остальные три фигуры имеют все вместе не менее 11 таких
клеток. Поскольку в них всего 13 клеток, то чистых клеток там не более
двух. Но фигур – три. Значит, хотя бы одна из них полностью окрашена,
поскольку в каждой содержится трехклеточный уголок.
Ответ: всегда.
12. Если в квадрате
2  2 содержится
а окрашенных клеток
 a  0,1, 2,3, 4 ,
то после
перекрашивания в нем будет 4  a окрашенных клеток. Значит, количество окрашенных
клеток изменится на величину a   4  a   2a  4 . Эта величина всегда четная. Значит,
четность количества клеток на доске на каждом шаге не меняется. Сначала окрашенных
клеток было 7 – нечетное количество. Значит, после любого шага оно останется нечетным.
Следовательно, стать равным 64 (когда всю доску покрасили в черный цвет) это количество
не может.
Контрольное задание.
1. Прямоугольник 64 покрыт плитками размеров 22 и 41. Доказать, что если одну из
плиток 22 заменить на плитку 41, то теперь прямоугольник покрыть не удастся.
2. Из противоположных углов доски 1010 выпилили два квадрата размерами 33. Можно
ли оставшуюся часть доски покрыть прямоугольными плитками размерами 21?
3. В клетчатом прямоугольнике размером 3  4 произвольно окрасили 9 клеток. Доказать, что
обязательно найдется трехклеточный уголок, все клетки которого окрашены.
4. Можно ли шахматную доску
четырехклеточный уголок?
88
разрезать на 15 прямоугольников 1 4
и один
5. Из 16 плиток 1 3 и одной плитки 11 сложили квадрат со стороной 7. Доказать, что
плитка 11 лежит в центре квадрата или примыкает к его границе.
6. Прямоугольник 5  7 разрезали на прямоугольники 1 3 и 1 4 . Сколько всего частей
могло получиться?
7. Прямоугольник 4 10 разрезали на прямоугольники 1 3 и фигурки из четырех
клеток, как на рисунке. Сколько всего частей могло получиться?
8. Квадрат 7  7 разрезали на трехклеточные уголки и пятиклеточные кресты. Сколько всего
частей могло получиться?
9. Можно ли доску 7575 разрезать на фигурки, каждая из которых либо прямоугольник 12, либо
пятиклеточный крест?
10. Можно ли квадрат 77 с удаленной угловой клеткой разрезать на прямоугольники 21, чтобы
ровно половина из них располагалась горизонтально?
11. Игорь хочет вырезать из клетчатого квадрата размером 1111 17 клетчатых прямоугольников
размером 16. Можно ли отметить в квадрате одну клеточку так, чтобы она наверняка осталась не
вырезанной, как бы Игорь ни старался?
12. Клетчатый прямоугольник со сторонами 629 и 630 разрезан на несколько квадратов (все
разрезы идут по линиям сетки). Какое наименьшее число квадратов с нечетной стороной может
оказаться в таком разбиении?
Документ
Категория
Образование
Просмотров
1 144
Размер файла
329 Кб
Теги
клетчатые
1/--страниц
Пожаловаться на содержимое документа