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

Старт в науке

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

• Авторы
• Руководители
• Файлы работы

Субоч И.С. 1Субоч Д.С. 1

---

1Вилейская гимназия № 2

Вольская Т.Л. 1Родионов К.А. 1

---

1Вилейская гимназия № 2

Работа в формате PDF

246.2 KB

ВВЕДЕНИЕ

Однажды на уроке математики предложили решить задачу «№ 4. Вкусная задача» одного из Областных турниров юных математиков:

В прямоугольнике m×n лежат конфеты. В каждой ячейке лежит шоколадная конфета одного из k цветов. Саша может съесть две конфеты, если они одного цвета и лежат в соседних ячейках.

1. Докажите, что можно разложить конфеты так, что Саша ни одной не сможет съесть, если

а) k = 2 и «соседними» называют ячейки, имеющие общую сторону;

б) k ≥ 4 и «соседними» называют ячейки, имеющие общую вершину.

2. Какое наибольшее число конфет может съесть Саша (в зависимости от n и m), если k = 3 и «соседними» называют ячейки, имеющие общую вершину?

3. Какое наибольшее число конфет может съесть Саша, если k = 2, «соседними» называют ячейки, имеющие общую вершину и n = m ≤ 7?

4. Какое наибольшее число конфет может съесть Саша, если k = 2, «соседними» называют ячейки, имеющие общую вершину и

а) m = 2?,

б) m = 3?

5. Какое наибольшее число конфет может съесть Саша, если k = 2, «соседними» называют ячейки, имеющие общую вершину и:

а) n = m = 8?,

б) n = m = 9?

Было много попыток решения задачи в классе и дома: учащиеся размещали конфеты по-разному, различными способами делались расчеты. Ничего не получалось.

Через некоторое время пришло понимание, что не хватает знаний для решения «Вкусной задачи» задачи. И тогда последовало обращение за помощью к учителю математики. Учитель подсказал, что в данной задаче необходимо опираться на методику решения задач «на раскраски».

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

Нужно отметить, что мы всегда за ЗОЖ. Поэтому нас изначально насторожило в условии задачи слово «наибольшее» в словосочетании «наибольшее число конфет может съесть». На определенном этапе решения задачи мы поняли, что конфеты можно разложить так, что их можно съесть все. Нас это не устроило, т.к. мы за ЗОЖ, а много сладкого есть вредно. Поэтому мы решили размещать конфеты так, чтобы их съесть как можно меньше. В своем решении задачи мы заменяем слово «наибольшее» на слово «наименьшее». И в целом выходим за рамки решения «Вкусной задачи», делаем его более обобщенным и опускаем при решении п. 4 и 5 задачи, т.к. они нам показались очень частными. Соответственно, объектом исследования стало наименьшее количество конфет, которые можно съесть.

При исследовании условия и решения «Вкусной задачи»основной целью былоконфеты разместить так, чтобы они соответствовали условию задачи и нашим правилам ЗОЖ.

В ходе исследования были выдвинуты гипотезы:

можно разложить конфеты так, что Саша ни одной не сможет съесть, если

а) k = 2 и «соседними» называют ячейки, имеющие общую сторону;

б) k ≥ 4 и «соседними» называют ячейки, имеющие общую вершину.

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

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

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

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

Новизна работы связана с собственным творческим исследованием «Вкусной задачи», редактированием её условия.

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

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

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

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

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

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

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

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

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

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

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

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

ГЛАВА 2. РЕШЕНИЕ-ИССЛЕДОВАНИЕ «ВКУСНОЙ ЗАДАЧИ»

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

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

Допустим, мы имеем конфеты в обертках синего и красного цвета. Решение было следующим (Рис. 1):

Рис. 1

k (цвет конфет) = 2 и «соседними» называют ячейки, имеющие общую сторону.

Таким образом, мы видим, что Саша не сможет съесть ни одной конфеты, если их разложить в шахматном порядке. Такая раскладка конфет соответствует нашим правилам ЗОЖ.

Аналогичным методом мы доказали, что при k ≥ 4 (обертки конфет синего, красного, зеленого, розового… цветов) и «соседних» ячейках имеющих общую вершину Саша также не съест ни одной конфеты (Рис. 2):

Рис. 2

Значит, Саша не может съесть ни одной конфеты, если в первой строке чередовать 2 цвета, а в следующей строке чередовать следующие 2 цвета и т.д. Если мы смогли конфеты 4 цветов разместить так, чтобы Саша не смог съесть ни одной, то тем более у него не получится съесть конфеты, если цветов будет больше.

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

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

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

Рис. 3

мы пришли к выводу, что при любом количестве цветов, при любой таблице m×n можно расположить конфеты так, что Саша съест все конфеты. Что нас не устраивает, т.к. мы за ЗОЖ. Поэтому тут мы решили изменить первоначальное условие задачи Областного турнира юных математиков: «наибольшее» число конфет мы поменяли на «наименьшее». И представили, что в прямоугольнике m×n, m – это ширина, а n – высота прямоугольника.

Далее решение было следующим.

Если мы имеем конфеты трех цветов, то расположив их таким образом (Рис. 4), мы не сможем съесть половину конфет при m и n четном.

Рис. 4

Если m – четное, а n – нечетное, то тоже съедаем половину конфет (Рис. 5), значит, остается конфет.

Рис. 5

Если m – нечетное и n – нечетное, то остается конфет (Рис. 6).

Рис. 6

Можно конфеты расставить и по-другому: m – нечетное, а n – любое число. В такой расстановке у нас будет оставаться конфет. А если m – четное, а n – любое число, то оставаться будет половина конфет (Рис. 7).

Рис.7

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

Если у нас конфеты двух цветов, то при m и n нечетных и расстановке конфет (Рис. 8) у нас остается конфет.

Рис. 8

Если m и n нечетное, то остается конфет (Рис. 9).

Рис. 9

Если m – четное, а n – нечетное, то остается конфет
(Рис. 10).

Рис. 10

Если m – нечетное, а n – четное, то остается конфет (Рис. 11).

Рис. 11

ЗАКЛЮЧЕНИЕ

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

В ходе исследования задачи «Вкусной задачи» вывели формулы подсчёта наименьшего количества конфет, которые можно съесть. Значит, цель исследования достигнута. Гипотезы подтвердились.

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

Следует заметить, что при решении мы детально проработали п. 1-3 «Вкусной задачи», а на п. 4-5 лишь обратили внимание только для проверки решения.

В ПРИЛОЖЕНИЯХ 1, 2 к исследовательской работе мы представили результаты создания и апробации машинных программ по подсчету количества конфет. В создании этих программ нам помогал учитель информатики Родионов К.А.

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

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

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

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

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

ПРИЛОЖЕНИЯ

Приложение 1. Результаты работы программы
на 3 цвета

program z1;

uses crt;

var

sm,sum,m,n,z,i,j,k,s,q:integer;

a,b: array [1..100,1..100,1..2] of byte;

c: array [1..10000] of byte;

begin

readln (m,n);

z:=m*n;sm:=0;

while s<2*m*n do

begin

for i:= z downto 1 do

if c[i]=2 then c[i]:=0 else begin c[i]:=c[i]+1;break; end;

s:=0;

for i:=1 to z do

s:=s+c[i];

q:=1;

for i:=1 to m do

for j:=1 to n do

begin

a[i,j,1]:=c[q];

q:=q+1;

end;

sum:=0;

for i:=1 to m do

for j:=1 to n do

a[i,j,2]:=0;

for i:=1 to m do

for j:=1 to n do

begin

if i>1 then

if a[i,j,1]=a[i-1,j+1,1] then begin a[i,j,2]:=1; a[i-1,j+1,2]:=1; end;

if i<m then

if a[i,j,1]=a[i+1,j+1,1] then begin a[i,j,2]:=1; a[i+1,j+1,2]:=1; end;

if i<m then

if a[i,j,1]=a[i+1,j,1] then begin a[i,j,2]:=1; a[i+1,j,2]:=1; end;

if j<n then

if a[i,j,1]=a[i,j+1,1] then begin a[i,j,2]:=1; a[i,j+1,2]:=1; end;

end;

for i:=1 to m do

for j:=1 to n do

if a[i,j,2]=0 then sum:=sum+1;

if sum>sm then begin sm:=sum; b:=a; end;

end;

for i:=1 to m do

begin

writeln;

for j:=1 to n do

write (b[i,j,1],' ');

end;

writeln;

writeln;

writeln (sm);

end.

Приложение 2. Результаты работы программы
на 2 цвета

program z1;

uses crt;

var

sm,sum,m,n,z,i,j,k,s,q:integer;

a,b: array [1..100,1..100,1..2] of byte;

c: array [1..10000] of byte;

begin

readln (m,n);

z:=m*n;sm:=0;

while s<m*n do

begin

for i:= z downto 1 do

if c[i]=1 then c[i]:=0 else begin c[i]:=1;break; end;

s:=0;

for i:=1 to z do

s:=s+c[i];

q:=1;

for i:=1 to m do

for j:=1 to n do

begin

a[i,j,1]:=c[q];

q:=q+1;

end;

sum:=0;

for i:=1 to m do

for j:=1 to n do

a[i,j,2]:=0;

for i:=1 to m do

for j:=1 to n do

begin

if i>1 then

if a[i,j,1]=a[i-1,j+1,1] then begin a[i,j,2]:=1; a[i-1,j+1,2]:=1; end;

if i<m then

if a[i,j,1]=a[i+1,j+1,1] then begin a[i,j,2]:=1; a[i+1,j+1,2]:=1; end;

if i<m then

if a[i,j,1]=a[i+1,j,1] then begin a[i,j,2]:=1; a[i+1,j,2]:=1; end;

if j<n then

if a[i,j,1]=a[i,j+1,1] then begin a[i,j,2]:=1; a[i,j+1,2]:=1; end;

end;

for i:=1 to m do

for j:=1 to n do

if a[i,j,2]=0 then sum:=sum+1;

if sum>sm then begin sm:=sum; b:=a; end;

end;

for i:=1 to m do

begin

writeln;

for j:=1 to n do

write (b[i,j,1],' ');

end;

writeln;

writeln;

writeln (sm);

end.