Загадка 25 точек соединить

Обновлено: 22.11.2024

С давних пор известны и пользуются популярностью головоломки, которые можно объединить под общим названием «одним росчерком». В таких задачах предлагается начертить какую-либо фигуру одним росчерком (одной линией), не отрывая карандаша от бумаги, и не проводя дважды по одной линии. Классическими примерами являются задачи, в которых одним росчерком нужно нарисовать разные варианты конверта или квадрат с диагоналями и четырьмя дугами:

Нарисуйте фигуры одним росчерком, не отрывая карандаша от бумаги, и не проводя по одной линии дважды Нарисуйте фигуры одним росчерком, не отрывая карандаша от бумаги, и не проводя по одной линии дважды

Вариантом задачи является поиск пути по дорогам или мостам, который будет проходить по всем дорогам (мостам) ровно по одному разу. Классическим примером является задача о семи кёнигсбергских мостах, которая опубликована на этой неделе под номером 5.

Также известна старая задача о доме из пяти комнат, каждая из которых соединена с другой и с улицей дверьми. Необходимо найти такой путь по комнатам, который проходил бы по всем 16 дверям ровно по одному разу (начинать и заканчивать можно в любой комнате или вне дома):

Соедините все 16 дверей одной линией, не пересекая ни одну из дверей дважды Соедините все 16 дверей одной линией, не пересекая ни одну из дверей дважды

Независимо от условий задачи (начертить фигуру одной линией или найти непрерывный путь), ее решением является граф – математический объект, объединяющий в себе множество вершин и ребер. Причем как само понятие графа, так и раздел математики, изучающий данные объекты (он назван теорией графов), родились как раз из решения такой задачи. А именно – из решения задачи о семи кёнигсбергских мостах, которой в 1736 году занялся великий математик Леонард Эйлер. Правда, само понятие «граф» было предложено в 1878 году английским математиком Джеймсом Джозефом Сильвестром. Однако «отцом» теории графов по праву считается Эйлер, и здесь мы проследим за некоторыми его рассуждениями.

Правила Эйлера

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

Карте Кёнигсберга преобразуется в граф с четырьмя вершинами Карте Кёнигсберга преобразуется в граф с четырьмя вершинами

Вот так Эйлер получил граф – абстрактный математический объект, состоящий из вершин, попарно соединенных ребрами. Вершины обозначены здесь красными точками, а ребра – черными линиями. А что за цифры стоят у вершин? О, это – как раз то, что и помогает решать любые (повторяю – любые) задачи о рисовании фигур одним росчерком! Это – обозначение четности/нечетности вершины, которое указывает на число ребер, которое выходит из данной вершины. Если из вершины выходит четное число ребер – значит она четная, а если нечетное – она нечетная. Все очень просто.

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

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

Итак, вновь посмотрим на граф задачи мостов Кёнигсберга: здесь четыре вершины, и все они нечетные. Значит, задача не имеет решения – пройти по всем семи мостам, посетив каждый из них ровно по одному разу, невозможно. Задача становится разрешимой только при добавлении одного моста (что в 1905 году и было сделано в реальности). Это можно сделать подобным образом (дополнительный мост указан пунктирной линией):

При добавлении одного моста задача о мостах Кёнигсберга имеет решение При добавлении одного моста задача о мостах Кёнигсберга имеет решение

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

Следующая загадка

соединить клетки (все, кроме синей) одной непрерывающейся линией

Голосование за лучший ответ

Невозможно! И сейчас я поясню почему. Очевидно, что для того чтобы была возможность решить задачу нужно начинать (заканчивать) на левом верхнем квадрате. Обозначим все квадраты знаками + и - в шахматном порядке (cтартовая клетка имеет знак +). Cмотрите рисунок 1. Чтобы решить задачу, нужно пройти 5*5-1=24 клетки. Тк одна клетка в таблице 5x5 недоступна. Очевидно, что переходя с клетки на клетку характер знаков будет чередоваться : +-+-+-+-и тд .Понятно, что на тк 24 число четное, то на финальной 24-й клетке у нас будет знак - .То есть в пройденном нами пути в общей сложности 12 знаков + и 12 знаков - .Но в таблице 5*5 у нас 25 чисел (число 25 нечетное), поэтому знаков + будет 13, а знаков - будет 12. Запрещенная клетка закрывает знак - ,а значит в пройденном нами пути должно быть 11 знаков - и 13 знаков + .Таким образом мы пришли к противоречию. Решить задачу ,, честно '' невозможно. Но можно сделать это немного схитрив, а именно выйти за зону игрового поля . (Смотрите рисунок 2)

Андрей ПоповУченик (112) 11 месяцев назад

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

Анализ и решение задач

Теперь проанализируем фигуры, приведенные в начале статьи – конверты и квадрат с дугами:

Следующая загадка

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

Что нужно делать?

Задача простая надо соединить 9 точек 4 линиями, не отрывая руки от экрана. Сами точки вы можете найти на изображении ниже

Следующая загадка

Мария Гуровская ответила Сообществу

Читайте также: