Из известных задач я узнала, что если точек 9, то 4 звена у ломаной, если 16, то – 6, если 25, то - 8 и если 36, то – 10. Обозначим через – количество звеньев ломаной для n×n точек расположенных в форме квадрата, то есть n – количество точек на стороне квадрата, тогда:
4=2*2=2*(3-1)
6=2*3=2*(4-1)
8=2*4=2*(5-1)
10=2*5=2*(6-1)
--------------------------
, где n=3, 4, 5, 6, …
С одной стороны я увидела, что количество звеньев ломаной является четным числом, т.к. произведение содержит четный множитель, а мы знаем, что каждое следующее четноечисло, на 2 больше предыдущего, то есть выполняется равенство: для любого натурального числа n.
С другой стороны, увидев закономерность, я сформулировала гипотезу, что количество звеньев ломанной вычисляется по формуле: , где n=3, 4, 5, 6, … Проверим истинность формулы с помощью метода математической индукции.
Количество звеньев ломаной вычисляется по формуле , где n – количество точек на стороне квадрата (n=3, 4, 5, 6, …).
Доказательство:
1. – верно.
2. Пусть при n=k, где – верно.
3. Докажем при n=к+1, где – верно.
Доказательство:
= = – верно. По методу математической индукции формула верна для любого натурального n=3, 4, 5, 6, …, что и требовалось доказать.
Итак, количество звеньев ломанной вычисляется по формуле , где n=3, 4, 5, 6, …
§2. Решения головоломок на вычеркиваниеn×n точек ломаной,
Состоящей из 2(n-1) звеньев
Зная, как вычислить количество звеньев ломаной, я стала решать различные задачи, стараясь выделить общий подход при решениях.
Задача 1. Перечеркните 9 точек, расположенных на рис.1, ломаной из 4 звеньев.
Решение: смотри рис.2.[4, С. 49]
Задача 2. Перечеркните 16 точек, расположенных на рис.3, ломаной из 6 звеньев.
....
....
....
....
Рис. 4.
Решение: смотри рис.5.
Рис. 5.
Задача 3. Перечеркните 25 точек, расположенных в форме квадрата, ломаной из 6 звеньев.
Решение: смотри рис.6.
Рис. 6.
Аналогичные решения получаем для 6×6 точек и 7×7, смотри рис.7 и рис.8 и т.д.:
Я увидела, что каково бы ни было количество точек, их можно вычеркнуть последовательно горизонтальными и вертикальными отрезками, оставив 9 точек внутри, которые всегда можно вычеркнуть 4 отрезами.
§3. Разработка алгоритма вычеркивания n×n точек ломаной,
Состоящей из 2(n-1) звеньев
Полученные результаты §2, я занесла в таблицу:
Количество точек | Количество точек на стороне квадрата | Количество вертикальных звеньев | Количество горизонтальных звеньев | Количество звеньев для вычеркивания 9 точек |
… | … | … | … | … |
n×n | n | n-3 | n-3 |
Увидев закономерность, сформулировала гипотезу, что для вычеркивания n×n точек, можно n-3 вертикальными и n-3 горизонтальными отрезками вычеркнуть все точки, кроме точек в соседних трех столбцах и трех строках, то есть оставить 9 точек, которые можно вычеркнуть 4 отрезками. Всего получается (n-3)+(n-3)+4 – отрезков.
Проверка (n-3)+(n-3)+4=n-3+n-3+4=(n+n)+(4-3-3)=2n-2 – верно.
Алгоритм
· Поставить ручку в вершину квадратаn×n (например, в верхнюю правую вершину)
· Поочередно (например, по часовой стрелке) вычеркнуть n-3 вертикальными и n-3 горизонтальными звеньями ломаной все точки, кроме 9 точек. (9 точек в соседних трех столбцах и трех строках)
· Вычеркнуть 9 точек, как показано на рис. 9.
Таким образом, мне удалось выявитьединый подход при вычеркивании n×nточек ломаной из 2(n-1)звеньев, то есть составить алгоритм решения таких задач.
ЗАКЛЮЧЕНИЕ
Цели работы достигнуты:
1. Получена и доказана формуладлянахождения количества звеньев ломаной для вычёркивания точек, а именно:
Количество звеньев ломаной вычисляется по формуле , где n – количество точек на стороне квадрата (n=3, 4, 5, 6, …).
2. Разработан алгоритм вычёркивания точек звеньями ломаной:
· Поставить ручку в вершину квадрата n×n (например, в верхнюю правую вершину)
· Поочередно (например, по часовой стрелке) вычеркнуть n-3 вертикальными и n-3 горизонтальными звеньями ломаной все точки, кроме 9 точек. (9 точек в соседних трех столбцах и трех строках)
· Вычеркнуть 9 точек, как показано на рис. 9.