IV Международный конкурс
научно-исследовательских и творческих работ учащихся
«СТАРТ В НАУКЕ»
 
     

НЕДЕТСКИЕ РАСКРАСКИ: ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ РАСКРАСОК ДЛЯ РЕШЕНИЯ ЗАДАЧ
Колычева А.А.
Текст научной работы размещён без изображений и формул.
Полная версия научной работы доступна в формате PDF


Введение

Говорят, что в каждом из нас живет художник. Правда не все могут нарисовать настоящий шедевр самостоятельно, однако раскрасить уже готовые очертания не так уж и сложно. Раскрашивать рисунки любят не только дети, но и взрослые. Так, среди моих сверстников сейчас очень популярны раскраски-антистресс, раскраски-граффити и картины по номерам. И, казалось бы, какое отношение имеет это незатейливое увлечение к науке?

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

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

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

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

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

Объект исследования: раскраски.

Предмет исследования: условия и возможности применения раскрасок для решения задач.

Цель исследования: проанализировать возможности применения раскрасок для решения математических задач.

Задачи исследования:

  1. Изучить литературу, в которой отражаются возможности применения раскрасок к решению различных теоретических и практических задач.

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

  3. Отобрать материал, посвященный раскраскам в математике, для оформления школьной математической газеты.

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

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

Методы исследования: изучение специальной литературы; обобщение, анализ и систематизация материала, практическое применение раскрасок для решения математических задач.

Глава I. Раскраски в науке и жизни

Раскраски широко применяются в различных областях науки и в повседневной жизни. Изучив литературу, мы нашли следующие примеры.

Изобразите на бумаге карту: области, граничащие друг с другом. Раскрасьте ее таким образом, чтобы никакие две граничащие области не оказались раскрашенными в один цвет. Каким минимальным количеством цветов можно обойтись при этом? Несложно заметить, что всего четыре цвета позволят сделать такую раскраску. А вот доказать тот факт, что для раскраски любой карты достаточно всего четыре цвета, не так-то просто. Эта задача в математике известна как «проблема четырех красок» и является одной из самых известных раскрасок в географии и математике.

Считается, что впервые проблему четырех красок сформулировал в 1852 году шотландский студент Фрэнсис Гутри. С 1878 года, когда английский математик Артур Кэли сообщил, что размышлял над этой задачей, но так и не смог найти решения, проблема четырех красок стала очень популярна среди ученых всех стран. [2]

Многие математики тщетно пытались найти решение этой проблемы. Так, к примеру, основоположник кибернетики и теории искусственного интеллекта Норберт Виннер писал, что пытался найти решение задачи о четырех красках, но оно «каждый раз, как заколдованное золото в волшебной сказке, обращалось в груду глиняных черепков». [2]

Англичане Кеннет Аппель и Вольфганг Хакен доказали теорему о четырех красках в 1976 году с помощью созданной компьютерной программы (для карт с количеством стран не более 38). Позднее были представлены более простые доказательства с использованием специализированного программного обеспечения.

Раскраски применяют в организации сотовой связи. Общая зона покрытий делится на ячейки, напоминающие соты. Для того чтобы не возникали помехи, необходимо строго разделять диапазоны частот между соседствующими базовыми станциями. Максимальное количество обслуживаемых базовой станцией абонентов в определенный момент времени тем больше, чем шире её канал. Получается, что с уменьшением количества различных частот диапазонов, увеличивается ширина канала связи. Пусть каждому диапазону частот соответствует свой цвет. На языке математики мы получаем задачу о раскраске плоскости, замощенной шестиугольниками, минимальным количеством цветов. [8]

Немало применений нашли раскраски в теории графов и прикладных сферах. Так, раскраски помогают автоматически составлять расписание занятий. При этом рассматривается граф, вершины которого учебные занятия. В том случае, если занятия невозможно провести одновременно (задействованы один и тот же класс, аудитория или преподаватель), вершины соединяют ребрами. Далее раскрашивают этот граф таким образом, что каждая пара соседних вершин окрашена в разные цвета, общее количество вершин одного цвета не превышает количества аудиторий, при этом количество использованных цветов должно быть минимальным. Благодаря современным компьютерным технологиям такой перебор не представляется сложным и на выходе мы получаем готовое расписание. [4].

Даже при составлении таблиц для известной игры судоку можно использовать метод раскрасок. Для этого надо принять клетки таблицы за вершины графа, а ребрами соединить те вершины, которые расположены в одной горизонтали, вертикали и угловом боксе. Вершины графа красят таким образом, чтобы каждая пара соседних вершин оказалась окрашена в различные цвета. Таблицу судоку размером 4 на 4 клетки раскрашивают в 4 цвета, таблицу 9 на 9 клеток раскрашивают в 9 цветов. А затем расставляют необходимое для решения задачи количество цифр (в зависимости от уровня сложности игры).

В Приложении 1 мы на примерах показали описанные выше возможности практического применения раскрасок.

Глава II. Решение задач методом математических раскрасок
  1. Многообразие решаемых задач

Википедия определяет раскраску, как изображение контуров, напечатанное или нарисованное на однотонном фоне. Математики говорят, что фигура раскрашена в несколько цветов, если каждой точке фигуры приписан определенный цвет.[5, с.53]

Идея метода раскраски состоит в том, что мы делим математические объекты на группы, наделяя их некоторыми свойствами. Каждой группе ставим в соответствие свой цвет, а затем составляем цветовую модель, которая нередко помогает найти правильное решение. Многие задачи повышенного уровня сложности и олимпиадные тем или иным способом связаны с раскрасками. Мы классифицировали их по признаку «наличие раскраски»:

Задачи с раскрасками

Раскраска дана в условии

Раскраску требуется получить в соответствии с заданием

Раскраски нет в условии и задании, но ее можно применить в решении задачи

Задачи на шахматной доске

Задачи с раскрашенными объектами (плоскость, фигура)

Задачи на раскрашивание фигуры, плоскости

Задачи на разрезание и замощение фигуры

Задачи на заполнение таблицы с заданными условиями

Другие задачи

Таблица 1. Классификация задач с раскрасками

В работе над решением задач мы следовали следующим рекомендациям:

  1. определить, какие идеи привели к решению;

  2. постараться выяснить какие исходные данные были использованы в решении, что произойдет, если некоторые условия изменить сделать выводы вывести некоторые следствия. [5]

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

  1. Задачи с раскраской в условии

Задачи на шахматной доске можно решать, используя свойства этой доски и особенности «ходов» шахматных фигур. К свойствам шахматной доски относят общее количество клеток, количество черных и белых клеток в отдельности.

Задача 1. Можно ли шахматным конем обойти все клетки шахматной доски 5×5, побывав в каждой клетке по одному разу, и вернуться в исходную клетку? [6, с.27]

Идеи решения: 1) каждый ход коня изменяет цвет клетки, на которой он стоит; 2) должно быть равное количество клеток каждого цвета.

Решение: На поле 13 черных клеток и 12 белых. 25-м ходом он попадет на последнюю черную клетку. К этому моменту конь посетил все клетки. Чтобы вернуться в исходное положение, нужно сначала попасть на белую клетку. Противоречие. Обход совершить нельзя.

Наблюдения и выводы: 1) в условии задачи можно изменить размеры поля. Тогда, если поле представляет собой квадрат со стороной из нечетного количества клеток, обход совершить нельзя. Если сторона квадрата состоит из четного количества клеток, то противоречия с количеством черных и белых клеток на поле не возникает. Однако, для ответа на поставленный вопрос нужно привести хотя бы один возможный вариант обхода. 2) Можно изменить в условии задачи фигуру, совершающую обход. Так, в задачах мы встречали фигуру «верблюд», которая, как и конь, перемещается буквой Г, но по большей стороне сдвигается на 4 клетки. Она вообще не сможет совершить такой обход, потому что с каждым ходом сохраняет цвет начальной клетки.

Задача 2. В левом нижнем углу доски 9×9 стоят 9 шашек, образуя квадрат 3×3. За один ход можно переставить шашку симметрично другой, не выходя за пределы доски. Можно ли за несколько ходов переместить эти шашки так, чтобы они образовали квадрат а) в левом верхнем углу, б) в правом верхнем углу, в) в центральном квадрате? [6, с.27]

Идея решения: раскрасить клетки доски таким образом, чтобы в один цвет были окрашены клетки, на которые можно переместить шашки и сравнить раскраску исходного квадрата 3×3 и того, куда мы должны переместить шашки. Если раскраска различная, то сделать это невозможно.

В данном случае раскраска является инвариантом. Инвариант – величина, которая не изменяется в результате некоторых операций. Если инвариант различает несколько положений, то от одного нельзя перейти к другому. [5, с.29]

Решение: В красный цвет раскрасим те клетки, на которые может перейти левая нижняя шашка. Видим, что на эти же клетки могут перейти и все оставшиеся угловые шашки. Далее, раскрасим в синий цвет те клетки, на которые может переместиться нижняя средняя шашка. Видим, что на эти же клетки перемещается верхняя средняя шашка. Аналогично закрасим в желтый цвет клетки, на которые может переместиться центральная шашка. Оставшиеся поля закрасим зеленым цветом – на эти клетки могут переместиться две оставшиеся шашки.

                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     
                                     

Рис.1 Переместить в углы можно

 

Рис.2 Переместить в центр нельзя

Теперь сравним раскраски полей в квадратах 3×3. Все угловые квадраты раскрашены одинаково, значит, можно переместить шашки в левый и правый верхние углы. Экспериментальным путем мы сделали это. А вот в центральный квадрат переместить шашки не сможем, так как раскраска отличается от раскраски угловых квадратов.

Наблюдения и выводы: 4-хцветная раскраска помогает решить подобные задачи, независимо от того, квадраты мы рассматриваем или прямоугольники, а также не имеет значения их размер и четность количества клеток на стороне квадрата или прямоугольника.

Задача 3. Прямая раскрашена в два цвета. Докажите, что найдутся три точки одного цвета A, B, C такие, что AB=BC. [5, с.54]

Идея решения: применим метод от противного.

Решение: Пусть нет на прямой такого отрезка, у которого середина и концы одного цвета. Возьмем отрезок AC с концами первого цвета. Вправо и влево от точек A и С отложим отрезки AM=АС и CK=AC. Концы M и K этих отрезков окрашены во второй цвет (в соответствии с нашим предположением). Но тогда точка B - середина отрезка MK, которая является и серединой отрезка AC, окрашена в первый цвет. Мы пришли к тому, что все три точки A, B и C окрашены в один цвет. Противоречие. Следовательно, наше предположение было неверно и такие точки найдутся.

  1. Задачи, в которых требуется найти раскраску

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

Задача 4. Раскрасьте некоторые клетки доски 8×8 так, чтобы у каждой клетки было ровно две соседние по стороне закрашенные клетки. Можно ли таким же образом закрасить некоторые клетки доски размером 6×20? [1, с.26]

Идея решения: 1) заметим, что каждый из уголков исходного квадрата имеет ровно по две соседние клетки, а значит, они обязательно будут покрашены; 2) в первую очередь покрасим клетки, соседние с диагональными.

Решение: Будем строить раскраску методом постепенного конструирования. Закрасим красным цветом те клетки, которые точно закрашены, а серым – те, которые точно не закрашены (на рисунке номера клеток указывают порядок работы с ними).

1

 

5

7

7

5

 

1

                                   
 

2

 

6

6

 

2

                                     

5

 

3

8

8

3

 

5

                                   

7

6

 

4

4

 

6

7

                                   

7

6

8

4

4

8

6

7

                                   

5

 

3

   

3

 

5

                                   
 

2

 

6

6

 

2

                                     

1

 

5

7

7

5

 

1

                                   

Рис.3 Постепенное конструирование

 

Рис.4 Раскраска – первое решение задачи

 

Рис.5 Раскраска – второе решение задачи

Рассуждая аналогичным образом, раскрасим прямоугольник 6×20.

                                       
                                       
                                       
                                       
                                       
                                       

Рис.6 Раскраска прямоугольника

Наблюдения и выводы: 1) Мы заметили, что любой квадрат с четным количеством клеток по стороне может быть раскрашен таким образом, чтобы каждая клетка имела по два закрашенных соседа. Действительно, на рисунке показан и способ такой раскраски. Видим, что квадрат 8×8 содержит в себе уже закрашенные квадраты 6×6, 4×4 и 2×2.Правда у квадратов 6×6 и 2×2 раскраску нужно будет инвертировать. Алгоритм построения раскраски для четного количества клеток на стороне такой: красим внешний ряд клеток по всему периметру, затем поочередно по направлению к центру - ряд клеток пропускаем, ряд красим.

2) Квадрат с нечетным количеством клеток на стороне раскрасить так, как требуется в задаче нельзя. Докажем. Начнем закрашивать с левого нижнего угла соседние с диагональными клетки - в красный цвет те, которые точно закрашены и серый цвет те, которые точно не закрашены. Пар закрашенных и не закрашенных клеток четное количество (на одну меньше, чем всего клеток на диагонали). А это значит, что обе соседние с правой верхней угловой клеткой будут не закрашены. Пришли к противоречию.

         
         
         
         
         

Рис. 7

3) Мы переформулировали исходную задачу таким образом, чтобы в ней фигурировало число текущего года – 2017. И такую задачу уже можно считать нестандартной, творческой.

Задача для математической газеты. Можно ли раскрасить некоторые клетки доски 2017×2017 так, чтобы у каждой клетки было ровно две соседние по стороне закрашенные клетки.

Рассматривая различные прямоугольники размером 6×m, мы пришли к выводу, что всегда можно раскрасить прямоугольник со сторонами 6×7n-1. Для этого нужно раскрасить левый квадрат 6×6, затем пропустить вертикальную полоску клеток, снова закрасить квадрат 6×6 и т.д. Этот результат можно обобщить и сформулировать верное утверждение: Прямоугольник 2n×(2n+1)*k-1 можно раскрасить так, чтобы у каждой клетки было ровно две соседние по стороне закрашенные клетки.

  1. Задачи, в которых раскраска помогает найти решение

Различные виды раскрасок и возможности их применения к решению задач разобраны в статье Кузнецова Дмитрия «О методе раскраски на примере одной задачи» в журнале «Квант». [6, с.25-27] Мы же рассмотрим следующие задачи, которые, как нам кажется, позволяют продемонстрировать красоту и возможности применения метода раскрасок к решению нестандартных задач.

Задача 5. Заполните таблицу 6×6 числами так, чтобы сумма чисел во всей таблице была четной, а в каждом прямоугольнике 1×4 – нечетной. [1, с.33]

Идея решения: в каждый прямоугольник поместим одно нечетное и три четных числа; поставим в соответствие нечетным числам закрашенную клетку; раскрасим таблицу таким образом, чтобы в каждый прямоугольник 1×4 попала только одна закрашенная клетка.

Решение: Нечетное число пишем в закрашенные клетки, четные числа расставляем в белые клетки.

                   

4

6

2

1

0

6

                   

2

2

3

6

4

4

                   

8

5

0

2

8

1

                   

7

6

2

4

3

8

                   

6

8

2

5

4

2

                   

0

8

7

6

2

4

Рис.8 Раскраска с заданным условием

       

Рис.9 Таблица с решением

Наблюдения и выводы: 1) Данную таблицу можно построить и для квадрата с нечетным количеством клеток на стороне. 2) Можно раскрасить квадрат так, чтобы в каждый прямоугольник 1×4 попали 3 или 1 клетка. Тогда тоже будет выполнено условие нечетной суммы в прямоугольниках.

Задача 6. Можно ли квадрат клетчатой бумаги 4×4 разрезать на один пьедестал, один квадрат (2×2), один столбик (1×4) и один зигзаг? [3, с.28]

Идея решения: раскрасим фигуры и квадрат 4×4 шахматной раскраской. Если квадрат на эти фигуры разрезать можно, то количество черных клеток и белых клеток должно быть одинаковым.

                                 
                                 
                                 
                                 

Рис.10 Шахматная раскраска фигур

Решение: Количество черных и белых клеток в квадрате 4×4 одинаковое – по 8 клеток. У фигурок черных клеток 9 или 7 в зависимости от того, как закрашена фигура пьедестал. В любом случае это не 8, поэтому квадрат 4×4 разрезать на эти фигуры нельзя.

Наблюдения и выводы: Чтобы доказать, что решение задачи на разрезание какой-нибудь фигуры на части, возможно, достаточно представить один из способов разрезания. Гораздо труднее доказать, что разрезать фигуру невозможно. И здесь часто помогает раскраска фигуры. Поэтому сначала нужно проверить – а возможно ли разрезание? И если ответ утвердительный, тогда надо искать способ разрезания.

1

4

5

8

9

2

3

6

7

10

Рис.11 Игра «Классики»

1

4

5

8

9

2

3

6

7

10

Рис.12

Задача 7. Для игры в классики на земле нарисован ряд клеток, в которые вписаны по порядку числа от 1 до 10. Маша прыгнула в клетку 1, затем попрыгала по остальным клеткам (каждый раз в соседнюю по стороне клетку) и выпрыгнула наружу из клетки 10. Известно, что на клетке 1 Маша была 1 раз, на клетке 2 – 2 раза и т.д. Сколько раз Маша была на клетке 10? [1, с.19]

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

Решение: Пусть на клетке с номером 10 было сделано x прыжков. Тогда, 1+3+5+7+9=2+4+6+8+x; 25=20+x; x=5. Ответ: 5 прыжков.

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

Заключение

В исследовательской работе мы сформулировали проблему – выяснить, каким образом можно использовать раскраски в решении задач. В процессе исследования, мы решили следующие задачи:

  1. рассмотрели, где в науке и в жизни применяются раскраски;

  2. выделили виды задач, которые можно решить с помощью раскрасок;

  3. составили их классификацию по признаку «наличие раскраски»;

  4. применили раскраски к решению задач каждого вида нашей классификации, оформили идеи, выводы и наблюдения;

  5. сформулировали задачу на раскраску с числом текущего года – 2017.

Также к практическим результатам нашего исследования можно отнести тематический выпуск школьной математической газеты, посвящённый «недетским» раскраскам (Приложение 2).

Надеемся, что данное исследование будет полезным для школьников, принимающим участие в олимпиадах по математике, а также тем учащимся, кому интересна наука математика. Материалы исследования можно использовать на дополнительных занятиях и кружках по математике.

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

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

Список источников и литературы
  1. Баранов В.Н., Баранова О.В. Экстремальные задачи в дискретной математике. Метод раскраски: учебное пособие. – Ижевск: изд-во «Удмуртский университет». – 2015

  2. Гарднер М. Математические головоломки и развлечения. Пер. с англ. Ю. А. Данилова. Под ред. Я. А. Смородинского. М., "Мир", 1971, 511с.

  3. Екимова М.А., Кукин Г.П. Задачи на разрезание. – М.: МЦНМО, 2002

  4. Зимин С.Н. Составление учебного расписания, используя теорию графов // Современные наукоемкие технологии. – 2007. – № 11. – С. 89-90. [Электронный ресурс URL: https://www.top-technologies.ru/ru/article/view?id=25634 (дата обращения: 18.10.2017)].

  5. Канель-Белов А.Я., Ковальджи А.К. Как решают нестандартные задачи / Под ред. В.О.Бугаенко, М.: МЦНМО, 2008

  6. Кузнецов Д. О методе раскраски на примере одной задачи /Квант №15 – 2003 с.25-27

  7. Математический кружок 6 класс / Универсальная методическая разработка для элективного курса по решению нестандартных задач в средних общеобразовательных учреждениях г.Москвы // сост. Д.А.Коробицын, Г.К.Жуков. – М.: МГУ, 2017

  8. Мурзаков Д.Э., Зенков М.А., Жуков А.Д. [и др.] Применение алгоритма последовательной раскраски графа в сотовой сети // Естественные и математические науки в современном мире: сб. ст. по матер. XXXI междунар. науч.-практ. конф. № 6(30). – Новосибирск: СибАК, 2015.

  9. Раскраска // Википедия. Свободная энциклопедия [Электронный ресурс URL: https://ru.wikipedia.org/wiki/Раскраска (дата обращения: 20.10.2017)].

Приложения

ПРИЛОЖЕНИЕ 1. Примеры практического применения раскрасок

ПРИЛОЖЕНИЕ 2. Выпуск газеты, посвященный раскраскам