VII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Ряд из фишек домино и тримино
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Находясь летом на даче, наша семья очень любит играть в различные настольные игры. Они позволяют не только скоротать и весело провести время в кругу семьи, но и развивают мыслительные способности. Одной из таких игр является игра «Домино».
Стандартный набор домино включает в себя 28 костяшек, каждая из которых представляет собой прямоугольную плитку. Её лицевая сторона разделена линией на две квадратные части. Каждая часть содержит от нуля до шести точек. В процессе игры игроки выкладывают цепь костяшек, соприкасающихся половинками с одинаковым числом очков.
Этим летом нашей семье подарили разновидность этой игры под названием «Тримино». Костяшки в этой игре представлены в треугольной форме, в углах которой проставлены цифры от 0 до 5. Одна костяшка ставится к другой своей гранью так, чтобы каждая и двух цифр данной грани соответствовала такой же цифре соседней костяшки.
Играя в эту игру, меня заинтересовал вопрос, а можно ли используя все фишки тримино или домино, выложить их в один ряд? Это и стало целью моей исследовательской работы.
Цели исследования: выяснить, можно ли из всех фишек стандартного набора домино и тримино выложить одну линию.
Задачи исследования:
Изучить литературу и ресурсы Интернет по теме исследования
Попытаться составить линию из фишек игр домино и тримино
Объяснить причину невозможности составления ряда из определенных наборов фишек
Выяснить, какое минимальное количество фишек нужно убрать при невозможности составления ряда.
Гипотеза
Из всех фишек игр тримино и домино можно составить одну линию
Объект исследования: игры домино и тримино
Предмет исследования: применение теории графов для составлениялинии из фишек игр домино и тримино
Методы исследования:
Нахождение информации в Интернете и литературных источниках
Использование теории графов в решении задач исследования
Эксперимент
Теоретическая часть
Домино́ — настольная игра, в процессе которой выстраивается цепь костяшек («костей», «камней»), соприкасающихся половинками с одинаковым количеством точек, обозначающим число очков.
Тримино (треугольное домино) — настольная игра, состоящая из 56 костяшек домино треугольной формы. В углах костяшек выписаны цифры от 0 до 5, которые идут в возрастающем порядке по часовой стрелке, и все костяшки разные.
Граф – система объектов (вершин) и связок (рёбер), соединяющих некоторые пары этих объектов.
Связный граф – граф, у которого каждая вершина имеет минимум одну связь.
Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующим ребром
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу. Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более двух вершин нечётной степени. Узнав всю необходимую информацию, я перешла к практической части своего исследования.
Четная вершина графа – вершина, из которой исходит четное количество связей.
Нечетная вершина графа – вершина, из которой выходит нечетное количество связей.
Практическая часть
Ряд из фишек домино
Для начала я решила составлять линии из фишек домино, так как они имеют более простую форму связей. При этом я рассматривала наборы последовательно, начиная с 0 – 1 до 0 – 6.
Первыми я взяла фишки, содержащие числовые значения равные только 0 и 1. Без особого труда я составила ряд. Тоже самое произошло и с набором фишек от 0 до 2
Пробуя экспериментальным путем, составить линию из набора фишек от 0 до 3, я столкнулась с тем, что ряд у меня не получался. Тогда я обратилась к теории графов. Составим графы для наборов 0 – 1 и 0 – 2. В вершины этого графа мы поместим значения, которые могут располагаться на фишке домино, а линии (связи) показывают сами фишки домино. Чтобы использовать все фишки, нам нужно пройти по всем связям данного графа. Этот можно сделать, если в графе существует эйлеров путь. Для этого необходимо, чтобы все вершины графа были четными (тогда обход можно начинать с любой вершины) или количество нечетных вершин было ровно 2 (тогда обход нужно начинать из нечетной вершины). Из данных графов видно, что в первом случае количество вершин с нечетной степенью равно 2, а во втором – все вершины – четные. Т.к. расположение дублей не влияет на обход графа, то на рисунке они показаны петлей у вершины.
Теперь обратим внимание на граф, составленный для набора фишек от 0 до 3. Все вершины (их 4) имеют нечётное количество связей, а это значит, что пройти по данному графу одним путем невозможно. Поэтому и фишки домино данного набора нельзя выстроить в одну цепочку. Если мы уберем из набора одну фишку, то количество вершин с нечетной степенью станет ровно 2, поэтому обход нужно начинать с одной из них. На фотографии представлен такой ряд.
У графа из набора с числовыми значениями от 0 до 4 все вершины имеют четную степень, поэтому ряд можно построить, начиная из любой фишки.
Составим граф для ряда с числовыми значениями от 0 до 5. Данный граф имеет все вершины с нечётным количеством связей, поэтому ряд из фишек домино данного набора построить нельзя, но если мы уберем из графа две связи (эти связи не должны быть из одной вершины), то количество вершин с нечетными степенями станет ровно 2 и обход такого графа возможен. В моем примере я убрала связи 0-5 и 3-4, тогда обход нужно начинать или из 1, или из 2. Пример такого ряда на рисунке.
Граф для ряда с числовыми значениями от 0 до 6 имеет 0 вершин с нечётным количеством связей, поэтому ряд можно построить. Начинать обход такого графа возможно из любой вершины, а значит и ряд из фишек домино можно составлять из любого значения.
Вывод: используя полный набор фишек домино, можно их выстроить в один ряд.
Ряд из фишек тримино
Далее я перешла к составлению рядов из фишек игры тримино. По аналогии с фишками домино, будем составлять графы для каждого набора по отдельности. Вершинами такого графа будут не значения, а сами фишки, т.к. каждая фишка имеет один вход и два выхода.
Рассмотрим граф для фишек из набора от 0 до 1, т.е. только те фишки, у которых имеются только цифры 0 или 1. Таких фишек ровно 4. Количество вершин с нечетными степенями в таком графе ровно 2, поэтому составить ряд было довольно легко.
Граф для ряда с числовыми значениями от 0 до 2 не имеет вершин с нечётным количеством связей, поэтому ряд можно построить.
У графа из набора фишек с числовыми значениями от 0 до 3 имеется 8 вершин с нечётным количеством связей, поэтому ряд из этих фишек построить нельзя. При этом нечетные степени имеют фишки, на которых либо все три цифры одинаковые, либо все три цифры различные. При составлении такого ряда у меня получилось убрать 5 фишек, но я пока не могу утверждать, что это количество минимальное.
Граф для ряда с числовыми значениями от 0 до 4 имеет 0 вершин с нечётным количеством связей, но несмотря на это, у меня не получилось построить ряд. Чтобы ряд получился, мне пришлось убрать 9 фишек. И опять я не могу утверждать, что это количество минимальное.
Я попыталась найти ответ на вопрос, почему у меня это не получилось. Мое объяснение следующее: фишка тримино в отличие от фишки домино имеет 2 выхода, поэтому продолжать ряд можно не только вдоль одной прямой, но и повернув этот ряд. Я попробовала это сделать и у меня получилось.
Рассматривая граф для полного набора фишек тримино (от 0 до 5), можно заметить, что он повторяет ситуацию набора фишек от 0 до 3. Только 30 вершин будут иметь четную степень, остальные 26 – нечетную. По-прежнему нечетную степень будут иметь вершины, где все цифры одинаковые или все цифры разные. А это значит, что ряд составить нельзя. Для этой ситуации также я пока не знаю ответа на вопрос, какое минимальное количество фишек нужно убрать, чтобы получился ряд.
Заключение
В ходе выполнения данной работы я познакомилась новым для меня разделом математики – теорией графов. Этот раздел не изучается в школьном курсе математики. Я узнала, что с помощью построения графов можно решать достаточно большое количество задач.
Составляя графы и выстраивая ряды из фишек домино и тримино, я познакомилась с эйлеровым путем в графе и узнала, что обойти граф можно только в том случае, если все вершины у графа четные или количество нечетных вершин равно 2. В первом случае обход можно начинать с любой вершины, а во втором случае – только с вершины с нечетной степенью. Данная теория полностью нашла подтверждение в моей работе.
Гипотеза, выдвинутая в начале работы, частично подтвердилась. Из полного набора фишек домино можно составить ряд, а из полного набора фишек тримино – нет. Это объясняется тем, что при составлении графа для полного набора количество вершин с нечетными степенями больше двух.
На данный момент я продолжаю своё исследование. Я хочу понять, как можно вычислить минимальное количество фишек, которые нужно убрать при составлении ряда из некоторых наборов фишек.
Кроме этого в процессе игры в тримино я заметила, что фишки выстраиваются не только в ряд, но и из них можно получать некоторые фигуры. На рисунке представлены фигуры, которые получились у меня. В дальнейшем я хочу узнать, можно ли составить из всех фишек игры тримино одну сплошную фигуру. Если нет, то какое максимальное количество фишек я могу для этого использовать.
Список литературы и интернет источников
Гарднер М. Лучшие математические игры и головоломки, или самый настоящий математический цирк/ М. Гарднер; пер. с англ. М.И. Антипина. – М.: АСТ, Астрель, 2009. 255 с.
Мельников О.И. Теория графов в занимательных задачах. Изд.3, испр. и доп. 2009. 232 с.
Оре О. Графы и их применение: Пер. с англ. 1965. 176 с.
https://ru.wikipedia.org/wiki/Домино
http://cyclowiki.org/wiki/Треугольное_домино
https://function-x.ru/graphs1_relations.html
https://ru.wikipedia.org/wiki/Эйлеров_цикл