О методе раскраски одной задачей. (Д. Ю. Кузнецов)



Скачать 361,66 Kb.
страница1/3
Дата15.10.2017
Размер361,66 Kb.
  1   2   3
О методе раскраски одной задачей. (Д.Ю.Кузнецов)

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

Д













































































































































































































































































































рис.1
оказать, что клетчатую доску 1010 нельзя разрезать по линиям сетки на прямоугольники 14.


Решение 1. Разделим доску на квадраты 22 и раскрасим их в шахматном порядке (рис.1). Заметим, что любой прямоугольник 14 содержит поровну (по 2) чёрных и белых клеток, но при данной раскраске на доске 52 чёрных клетки и 48 белых, т.е. не поровну. Значит, разрезать доску 1010 на тетрамино 14 не удастся.

П

1

2

3

4

1

2

3

4

1

2

2

3

4

1

2

3

4

1

2

3

3

4

1

2

3

4

1

2

3

4

4

1

2

3

4

1

2

3

4

1

1

2

3

4

1

2

3

4

1

2

2

3

4

1

2

3

4

1

2

3

3

4

1

2

3

4

1

2

3

4

4

1

2

3

4

1

2

3

4

1

1

2

3

4

1

2

3

4

1

2

2

3

4

1

2

3

4

1

2

3

рис.2
римечание.
Идея применения подобной «шахматной раскраски квадратами 22» возникает естественным образом из обычной шахматной раскраски, которая очень часто применяется для доминошек 12. А здесь мы имеем дело с фигурой в два раза крупнее, потому и раскраска стала в два раза крупнее, причём в обоих направлениях.

Решение 2. Раскрасим доску диагональной раскраской в 4 цвета (рис.2). Заметим, что любой прямоугольник содержит по одной клетке каждого из четырёх цветов, но при данной раскраске на доске по 25 клеток 1-го и 3-го цветов, 26 клеток – 2-го и 24 клетки – 4-го, т.е. не поровну. Значит, разрезать доску 1010 на тетрамино 14 не удастся.

Р













































































































































































































































































































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

П













































































































































































































































































































рис.4
римечание.
Легко заметить, что данная раскраска является разновидностью диагональной раскраски на рис.2, когда в качестве чёрного цвета выделен цвет номер 4, которого меньше 25 клеток. С таким же успехом можно было бы использовать в качестве чёрного цвета и цвет номер 2, то тогда бы мы получили сразу 26 прямоугольников, что невозможно. Кроме того, можно было бы объединить в чёрный цвет и любые два соседних цвета с раскраски на рис.2. Например, если бы мы в качестве чёрного цвета использовали цвета номер 1 и 2, то у нас бы возникло следующее решение.

Решение 4. Посмотрим на раскраску на рис.4. Заметим, что любой прямоугольник 14 содержит поровну (по 2) чёрных и белых клеток, но при данной раскраске на доске 51 чёрная клетка и 49 белых, т.е. не поровну. Значит, разрезать доску 1010 на тетрамино 14 не удастся.

Р

1

2

1

2

1

2

1

2

1

2

3

4

3

43

3

4

3

43

3

4

1

2

1

2

1

2

1

2

1

2

3

4

3

4

3

4

3

4

3

4

1

2

1

2

1

2

1

2

1

2

3

433

3

4

3

4

3

4

3

4

1

2

1

2

1

2

1

2

1

2

3

4

3

4

3

4

3

4

3

4

1

2

1

2

1

2

1

2

1

2

3

4

3

4

3

4

3

4

3

43

рис.5
ешение

Каталог: data -> 2011
2011 -> Программа дисциплины Компьютерная лингвистика для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров
2011 -> «Выполняя врачебные обязанности, я постиг дух народный»: самосознание врача как просветителя российского государства первая половина
2011 -> А. И. Зыкин 1 курс Кубик Рубика. Требуется описать группу вращений и допустимые положения кубика. Задача
2011 -> Дэвид Ванн, Томас X. Нэйлор, Джон Де Грааф Потреблятство. Болезнь, угрожающая миру
2011 -> Мирча Элиаде йога: бессмертие и свобода
2011 -> Что изучает этнология?
2011 -> П зз избранные философские произведения
2011 -> Психология. Журнал Высшей школы экономики. 2006. Т. 3, № С. 102-110


Поделитесь с Вашими друзьями:
  1   2   3


База данных защищена авторским правом ©stomatologo.ru 2017
обратиться к администрации

    Главная страница