Теория графов или зарплата в придачу
В одном славном городе Украины, Донецкая обл. (не стану писать название) есть технарь. А в технаре том есть некий преподаватель, который уже много лет любит задавать учащимся задачу на засыпку:
Приведенную выше фигуру (круг с линиями внутри) требуется нарисовать на бумаге, отрывать карандаш от бумаги разрешается только 3 раза (после 3го отрыва фигура должна быть полностью готова). Запрещается проводить по одной линии дважды и всячески ухищраться: сгибать лист, протыкать его, накладывать другой и т.п. Знающим людям сразу ясно, что это классическая задача из теории графов ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 и www.intuit.ru/department/algorithms/graphsuse/1/ . Проблема с ней только в том, что обычно надо нарисовать фигуру без отрыва карандаша от бумаги, а тут отрывать можно 3 раза, и, возможно, это несколько усложняет исследование.
Мой интерес к этой задаче возник недавно, когда мне в очередной раз рассказали, что препод обещает отдать свою зарплату тому, кто сможет решить задачу. Узнал я о задаче еще лет 8 назад, да и забыл, а к настоящему времени это переросло уже прям в байку, что мол есть некие 3 человека, которые ее решили, но никому не рассказывают. Многие учащиеся пытались решить ее, но все тщетно. Пытался и я )).
Я изучил вопрос как нарисовать этот круг с линиями внутри)).
Должен сказать, что это невозможно сделать с тремя отрывами карандаша от бумаги и без всяких ухищрений. Таким образом мой вердикт таков: препод всех обманул (а попросту - ловко наебал, ясен хрен, что не стал бы он рисковать своими деньгами если б знал, что решение есть.) Так же я утверждаю что те, кто это нарисовал и типа никому не рассказывают - тоже обманщики.
Объясняю суть. http://chgard2.tgl.net.ru/wiki/index.php/%D0%A1%D0%B...
Тут есть немного теории по графам, почитайте ее, также найди в нете про мосты Кёнигсбергские и Эйлера и тоже почитайте. Скопирую только самое важное:
"ОПРЕДЕЛЕНИЕ: Граф, который можно нарисовать, не отрывая карандаша от бумаги и проводя каждое ребро один раз, называется эйлеровым или уникурсальным.
ВЫВОД 1: Если все вершины графа четные, то его можно начертить одним росчерком (не отрывая карандаша от бумаги), при этом движение можно начать в любой вершине и закончить его в той же вершине.
ВЫВОД 2: Если граф имеет только две нечетные вершины, то его можно начертить одним росчерком (не отрывая карандаша от бумаги), при этом движение начать нужно в одной нечетной вершине, а закончить в другой.
ВЫВОД 3: Граф с более чем двумя нечетными вершинами нельзя начертить одним росчерком.
© Шувалова Юлия Григорьевна: Семинар ДООМ "Можно ли не ломая проволоки изготовить каркас куба?" "
Обратите внимание на вывод 3, он означает, что чтобы нарисовать фигуру с хотя бы тремя нечетными вершинами надо сделать один отрыв карандаша от бумаги. Теперь посмотрите на нашу фигуру: там есть 8 вершин и все они нечетные, в каждую из них сходится по 3 линии (нечетное число). Далее я рассуждаю исходя из того, что чтобы нарисовать фигуру с 8 вершинами надо как минимум отдельно рисовать ее части, в которые входят 2 нечетные вершины.
То есть, чтобы нарисовать нашу фигуру надо сначала захватить 2 нечетные вершины, затем оторвать карандаш, затем можно захватить опять максимум 2 нечетные вершины и оторвать карандаш опять. Потом опять захватить 2 и оторвать в третий раз карандаш. Все, больше отрывать карандаш нельзя. При этом удалось захватить только 2 + 2 + 2 = 6 вершин, а в фигуре их 8 !!!
То есть без четвертого отрыва нарисовать ее невозможно.
Что и требовалось доказать.
Учащиеся технаря мне рассказывают, что всегда у всех не хватает одной линии дорисовать. Я удивлен, почему никто из всего технаря не нашел эту теорию графов и не посрамил препода.
Допускаю, что в моих рассуждениях есть ошибка, и нельзя использовать такую простую логику в доказательстве. Но в таком случае получается что все, кто пробовал решить эту задачу полные олени с низким IQ. Я не думаю что это так, а в этом случае выходит, что препод обманщик, и поступил нечистоплотно по отношению к своим учащимся. Лучшим доказательством будет пошаговая инструкция по рисованию фигуры. Если ее не будет - я претендую на его зарплату, т.к. в математике принято ставить задачи так: решить задачу или доказать что решения нет. )))
Приведенную выше фигуру (круг с линиями внутри) требуется нарисовать на бумаге, отрывать карандаш от бумаги разрешается только 3 раза (после 3го отрыва фигура должна быть полностью готова). Запрещается проводить по одной линии дважды и всячески ухищраться: сгибать лист, протыкать его, накладывать другой и т.п. Знающим людям сразу ясно, что это классическая задача из теории графов ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 и www.intuit.ru/department/algorithms/graphsuse/1/ . Проблема с ней только в том, что обычно надо нарисовать фигуру без отрыва карандаша от бумаги, а тут отрывать можно 3 раза, и, возможно, это несколько усложняет исследование.
Мой интерес к этой задаче возник недавно, когда мне в очередной раз рассказали, что препод обещает отдать свою зарплату тому, кто сможет решить задачу. Узнал я о задаче еще лет 8 назад, да и забыл, а к настоящему времени это переросло уже прям в байку, что мол есть некие 3 человека, которые ее решили, но никому не рассказывают. Многие учащиеся пытались решить ее, но все тщетно. Пытался и я )).
Я изучил вопрос как нарисовать этот круг с линиями внутри)).
Должен сказать, что это невозможно сделать с тремя отрывами карандаша от бумаги и без всяких ухищрений. Таким образом мой вердикт таков: препод всех обманул (а попросту - ловко наебал, ясен хрен, что не стал бы он рисковать своими деньгами если б знал, что решение есть.) Так же я утверждаю что те, кто это нарисовал и типа никому не рассказывают - тоже обманщики.
Объясняю суть. http://chgard2.tgl.net.ru/wiki/index.php/%D0%A1%D0%B...
Тут есть немного теории по графам, почитайте ее, также найди в нете про мосты Кёнигсбергские и Эйлера и тоже почитайте. Скопирую только самое важное:
"ОПРЕДЕЛЕНИЕ: Граф, который можно нарисовать, не отрывая карандаша от бумаги и проводя каждое ребро один раз, называется эйлеровым или уникурсальным.
ВЫВОД 1: Если все вершины графа четные, то его можно начертить одним росчерком (не отрывая карандаша от бумаги), при этом движение можно начать в любой вершине и закончить его в той же вершине.
ВЫВОД 2: Если граф имеет только две нечетные вершины, то его можно начертить одним росчерком (не отрывая карандаша от бумаги), при этом движение начать нужно в одной нечетной вершине, а закончить в другой.
ВЫВОД 3: Граф с более чем двумя нечетными вершинами нельзя начертить одним росчерком.
© Шувалова Юлия Григорьевна: Семинар ДООМ "Можно ли не ломая проволоки изготовить каркас куба?" "
Обратите внимание на вывод 3, он означает, что чтобы нарисовать фигуру с хотя бы тремя нечетными вершинами надо сделать один отрыв карандаша от бумаги. Теперь посмотрите на нашу фигуру: там есть 8 вершин и все они нечетные, в каждую из них сходится по 3 линии (нечетное число). Далее я рассуждаю исходя из того, что чтобы нарисовать фигуру с 8 вершинами надо как минимум отдельно рисовать ее части, в которые входят 2 нечетные вершины.
То есть, чтобы нарисовать нашу фигуру надо сначала захватить 2 нечетные вершины, затем оторвать карандаш, затем можно захватить опять максимум 2 нечетные вершины и оторвать карандаш опять. Потом опять захватить 2 и оторвать в третий раз карандаш. Все, больше отрывать карандаш нельзя. При этом удалось захватить только 2 + 2 + 2 = 6 вершин, а в фигуре их 8 !!!
То есть без четвертого отрыва нарисовать ее невозможно.
Что и требовалось доказать.
Учащиеся технаря мне рассказывают, что всегда у всех не хватает одной линии дорисовать. Я удивлен, почему никто из всего технаря не нашел эту теорию графов и не посрамил препода.
Допускаю, что в моих рассуждениях есть ошибка, и нельзя использовать такую простую логику в доказательстве. Но в таком случае получается что все, кто пробовал решить эту задачу полные олени с низким IQ. Я не думаю что это так, а в этом случае выходит, что препод обманщик, и поступил нечистоплотно по отношению к своим учащимся. Лучшим доказательством будет пошаговая инструкция по рисованию фигуры. Если ее не будет - я претендую на его зарплату, т.к. в математике принято ставить задачи так: решить задачу или доказать что решения нет. )))