РЕШЕНИЕ-ИССЛЕДОВАНИЕ ЗАДАЧИ «КРАСИМ КВАДРАТ»

XXVII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

Личный портфель

РЕШЕНИЕ-ИССЛЕДОВАНИЕ ЗАДАЧИ «КРАСИМ КВАДРАТ»

Трубач П.А. 1
1Вилейская гимназия № 2
Вольская Т.Л. 1
1Вилейская гимназия № 2
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

ВВЕДЕНИЕ

Около 70% площади здания Вилейской гимназии № 2 входит в зону покрытия WI-FI. Это неплохой показатель, но не во всех помещениях нашего учреждения образования четкий сигнал сети. Мы задались вопросом: «Что можно сделать, чтоб улучшить сигнал WI-FI во всем здании гимназии?» Выяснили, что очень важно правильное размещение роутера. Поиск места для роутера – это математическая задача. С нее и начнем.

Нам показалось, что задачи на раскраски помогут разобраться с правильным местом размещения роутера. Например, мы нашли такую задачу: 1. Дан клетчатый квадрат 10×10. Какое наименьшее количество клеток нужно закрасить так, чтобы любой прямоугольник 2×5 со сторонами, параллельными сторонам квадрата, составленный из клеток, содержал бы хоть одну закрашенную клетку?

2. А в квадрате 11×11?

3. Попробуйте решить эту задачу для квадратов 12×12, 13×13 и 14×14.

4. А если взять квадрат квадрата n×n (для n > 4)?

5. Дан клетчатый квадрат 2n×2n. Какое наименьшее количество клеток нужно закрасить так, чтобы любой прямоугольник 2×2 со сторонами, параллельными сторонам квадрата, составленный из клеток, содержал бы хоть одну закрашенную клетку?

6. Дан клетчатый квадрат 15×15. Какое наименьшее количество клеток нужно закрасить так, чтобы любой прямоугольник 3×5 со сторонами, параллельными сторонам квадрата, составленный из клеток, содержал бы хоть одну закрашенную клетку?

7. А в квадрате (15+х)×(15+х), где х – натуральное число от 1 до 14 включительно?

8. Какое наименьшее количество клеток в квадрате k×k можно закрасить, чтобы выполнялось условие: в прямоугольниках указанных размеров n×m должна быть хоть одна закрашенная клетка?

В данной задаче необходимо опираться на методику решения задач
«на раскраски». Было много попыток решения задачи в классе и дома. Задачи «на раскраски» не изучаются в школьной программе, но могут использоваться в решении олимпиадных задач. Это значит, что 6-классник теоретически не может состояться как исследователь «Красим квадрат». Но ничто не мешает самостоятельно изучению данную тему.

Объектом исследования стало наименьшее количество закрашенных клеток в квадрате nxn так, чтобы выполнялось условие: в прямоугольниках указанных размеров должна быть одна закрашенная клетка.
В персективе объектом исследования может стать поиск наиболее выгодных мест для размещения роутеров в Вилейской гимназии № 2.

При исследовании условия и решения «Красим квадрат»основной целью былоквадраты разместить так, чтобы они соответствовали условию задачи
и в дальнейшем исследовании помогли нам найти наиболее выгодные места для размещения роутеров в Вилейской гимназии № 2.

Цель исследования определила следующие задачи:

  1. изучить теоретический материал о решении задач «на раскраски»;

  2. исследовать задачу «Красим квадрат» для определения наименьшего количества закрашенных клеток, которые можно разместить в квадратах;

  3. обсудить с инженером-программистом гимназии Мяделко Е.С. систему поиска наиболее выгодных мест для размещения роутеров в Вилейской гимназии № 2.

Методы исследования: сравнение, метод индукции, анализ.

Новизна работы связана с собственным творческим исследованием задачи «Красим квадрат» и апробацией ее решения для практического применения в Вилейской гимназии № 2 для улучшения сигнала WI-FI.

ГЛАВА 1. ЧТО ТАКОЕ МЕТОД РАСКРАСКИ?

ГДЕ ОН ПРИГОДИТСЯ?

Исследуя литературу по теме, мы выяснили, что идея метода раскраски состоит в том, что математические объекты делятся на группы, наделенные некоторыми свойствами. Каждой группе ставиться в соответствие свой цвет, а затем составляется цветовая модель, которая нередко помогает найти правильное решение [1].

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

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

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

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

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

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

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

4. Даже при составлении таблиц для известной игры судоку можно использовать метод раскрасок [1, 2, 3].

5. При решении задачи мы использовали следующий теоретический материал: «Целой частью числа х (обозначение [x]) называется наибольшее целое число, не превосходящее х. Так, [5,6] = 5, [– 3,2] = – 4. Функцию [х] называют также «антье от x» (от французского слова entier – целый). Дробной частью числа х [обозначение {х}] называется разность {х} = х – [х]» [4].

ТАКИМ ОБРАЗОМ, область применения метода раскрасок очень обширна. Например, в 2023 году учащиеся нашей гимназии Субоч Д. и Субоч И. доказали, что «Вкусная задача» на раскраски помогает с поиском оптимальных мест в магазине при раскладке товаров на полках.
А мы предполагаем, что наша задача «Красим квадрат» в перспективе будет применима для поиска наиболее выгодных мест размещения роутеров в Вилейской гимназии № 2.

ГЛАВА 2. РЕШЕНИЕ-ИССЛЕДОВАНИЕ ЗАДАЧИ

«КРАСИМ КВАДРАТ»

2.1. Решение п. 1-4 задачи

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

Мы использовали различные методы закраски. Сначала выставляли закрашенные квадратики хаотично. Потом применяли шаг шахматного коня и многие другие постановки закрашивания. Таким образом, у нас получилось, что наименьшее количество закрашенных клеток мы получили, закрасив квадратики так, как на Рис. 1, 2, 3, 4.

                   
                   
                   
                   
                   
                   
                   
                   
                   
                   

Рис. 1. Квадрат 10х10

                     
                     
                     
                     
                     
                     
                     
                     
                     
                     
                     

Рис. 2. Квадрат 11х11

                     
                     
                     
                     
                     
                     
                     
                     
                     
                     
                     

Рис. 3. Квадрат 12х12

                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           

Рис. 4. Квадрат 14х14

Далее мы вывели формулу для расстановки закрашенных квадратиков в любом квадрате n×n (для n > 4).

Предположим, n:2=k. Если k – четное, то четные строки и нечетные строки тоже .

Предположим, n:4=а, (n+2):4=b. Пусть а и b – полное и неполное частное, таким образом

Предположим, n:2=k. Если k – нечетное, то четные строки и нечетные строки , таким образом

 

2.2. Решение п. 5 задачи

Разберемся с клетчатым квадратом 2n×2n. Иллюстрируем решение для квадрата, в котором n=4 (т.е. квадрата со сторонами 2*4×2*4) (Рис. 5):

               
               
               
               
               
               
               
               

Рис. 5. Квадрат 2*4×2*4

Продолжим разбираться с клетчатым квадратом 2n×2n.

Иллюстрируем решение для квадрата, в котором n=5 (т.е. квадрата со сторонами 2*5×2*5) (Рис. 6, 7):

                   
                   
                   
                   
                   
                   
                   
                   
                   
                   

Рис. 6. Квадрат 2*5×2*5 (правильный)

                   
                   
                   
                   
                   
                   
                   
                   
                   
                   

Рис. 7. Квадрат 2*5×2*5 (неправильный)

Иллюстрируем решение для квадрата, в котором n=7 (т.е. квадрата со сторонами 2*7×2*7) (Рис. 8):

                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           
                           

Рис. 8. Квадрат 2*7×2*7

Иллюстрируем решение для квадрата, в котором n=8 (т.е. квадрата со сторонами 2*8×2*8) (Рис. 9):

                               
                               
                               
                               
                               
                               
                               
                               
                               
                               
                               
                               
                               
                               
                               
                               

Рис. 9. Квадрат 2*8×2*8

2.3. Решение п. 6 задачи

Продолжим решение задачи, работая с клетчатым квадратом 15×15,
в котором будем рассматривать прямоугольник 3×5. Сделаем иллюстрацию (Рис. 10).

                             
                             
                             
                             
                             
                             
                             
                             
                             
                             
                             
                             
                             
                             
                             

Рис. 10. Квадрат 15×15

Проверим получившийся результат, работая с клетчатым квадратом 17×17. Сделаем иллюстрацию (Рис. 11).

                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 

Рис. 11. Квадрат 17×17

 

2.4. Решение п. 7 задачи

Продолжим решение задачи, работая с клетчатым квадратом 16×16, в котором будем рассматривать прямоугольник 3×5. Сделаем иллюстрацию (Рис. 12).

                               
                               
                               
                               
                               
                               
                               
                               
                               
                               
                               
                               
                               
                               
                               
                               

Рис. 12. Квадрат 16×16 (прямоугольники 3×5)

Проверим получившийся результат, работая с клетчатым квадратом 17×17. Сделаем иллюстрацию (Рис. 13).

                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 
                                 

Рис. 13. Квадрат 17×17(прямоугольники 3×5)

2.5. Решение п. 8 задачи

Продолжим решение задачи, работая с клетчатым квадратом k×k, в котором будем рассматривать прямоугольник n×m. Сделаем иллюстрации
(Рис. 14, 15, 16).

                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       

Рис. 14. Квадрат 20×20 (прямоугольники 4×7)

Проверим получившийся результат, работая с клетчатым квадратом 26×26 (прямоугольники 4×6) (Рис. 15).

                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   
                                                   

Рис. 15. Квадрат 26×26 (прямоугольники 4×6)

Для ввода общей формулы нам понадобилось теоретическое понятие: «Целой частью числа х (обозначение [x]) называется наибольшее целое число, не превосходящее х [4]. Так, [5,6] = 5, [–3,2] = –4.

Таким образом, (2k-n):m=[a], (2k- m):n =[b].

Получили общую формулу:

ЗАКЛЮЧЕНИЕ

В процессе исследования мы узнали о раскраске как методе решения задач.

В ходе исследования задачи «Красим квадрат» вывели формулы для определения наименьшего количества закрашенных клеток, которые можно разместить в квадратах, соответствующих условиям задачи. С инженером-программистом Вилейской гимназии № 2 Мяделко Е.С. мы начали поиск наиболее выгодных мест для размещения роутеров в учреждении образования. Значит, цель исследования достигнута.

«Рано или поздно всякая правильная математическая идея находит применение в том или ином деле», – говорил механик и математик А.Н.Крылов. Если следовать логике этого высказывания, проверенного временем, то правильное решение-исследование задачи «Красим квадрат» также найдет практическое применение.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

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

2. Колычева, А.А. Недетские раскраски: возможности применения раскрасок для решения задач [Электронный ресурс]. – Режим доступа: https://school-herald.ru/ru/article/view?id=502. – Дата доступа: 18.02.2025.

3. Кузнецов, Д.Ю. О методе раскраски одной задачей. [Электронный ресурс]. – Режим доступа: https://nnov.hse.ru/data/2015/08/05/1085108094/%D1%82%D0%B5%D1%. – Дата доступа: 18.01.2025.

4. Целая часть числа. [Электронный ресурс]. – Режим доступа: https://www.booksite.ru › fulltext – Дата доступа: 25.03.2025.

Просмотров работы: 4