Нестандартные задачи по математике

2)Пусть существует такой незамкнутый путь; например, пусть он начинается в вершине А, а заканчивается в С.

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

Ответ: нельзя.

Хотя рассуждение проведенное при решении задачи 3.13, вы

полнено для частного случая, оно носит общий характер:

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

2)если существует аналогичный незамкнутый путь, то степени начала и конца пути нечетные, а остальных вершин – четные.

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

1) когда степень каждой вершины четная (в этом случае путь замкнут),

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

3.18.Можно ли обвести карандашом, не отрывая его от бумаги и не проводя по одной линии дважды:

а) квадрат с диагоналями,

б)правильный пятиугольник с диагоналями?

3.19. Можно ли из проволоки длиной 12 дм изготовить каркас куба с ребром длины 1 дм, не ломая проволоку на части?

3.20. Можно ли граф, изображенный на рисунке 22, обвести карандашом, не отрывая его от бумаги и не проходя ни одной линии дважды? Если можно, то как?

3.21. В точке А расположен гараж для снегоочистительной машины (рис. 23). Водителю машины было поручено убрать снег с улиц части города изображенной на рисунке. Может ли он закончить свою работу на том перекрестке, где находится гараж, если по каждой улице своего участка города водитель будет проезжать только один раз?

3.22. В марсианском метро 100 станций. От любой станции до любой Другой можно проехать. Забастовочный комитет хочет закрыть проезд через одну из станций так, чтобы между всеми остальными стан­циями был возможен проезд. Докажите, что такая станция найдется.

3.23. В тридевятом царстве каждые два города соединены дорогой с односторонним движением. Докажите, что существует город, из которого в любой другой можно проехать не более чем по двум дорогам.

3.24. В городе на каждом перекрестке сходится четное число улиц. Известно, что с любой улицы города можно проехать на любую другую. Докажите, что все улицы города можно объехать, побывав на каждой по одному разу.

Разные задачи на графы.

3.25. В углах шахматной доски 3х3 стоят 4 коня: 2 белых (в соседних углах) и два черных. Можно ли за несколько ходов (по шахматным правилам) поставить коней так, чтобы во всех соседних углах стояли кони разного цвета?

Решение.

Отметим центры клеток доски и соединим отрезками пары отмеченных точек, если из одной в другую можно пройти ходом коня. Мы получим граф, содержащий «цикл» из восьми точек и одну изолированную точку (рис. 24). Перемещение коней по доске соответствует движению по ребрам этого цикла. Ясно, что при движении по циклу нельзя изменить порядок следования коней.

3.26. Выпишите в ряд цифры от 1 до 9 так, чтобы число, составленное из двух соседних цифр, делилось либо на 7, либо на 13.

Решение.

Напишем цифры на листе. Соединим стрелками те цифры, которые могут следовать друг за другом (рис. 25). Теперь ясно, что первой идет 7, затем 8 и 4. Поскольку 8 уже использована, то стрелки, идущие в нее, надо убрать. После 4 идет 9, поскольку к девятке другого пути нет. Дальше идет 1 и так далее.

Ответ: 784913526.

3.27. В школьном турнире в один круг играют шесть шахматистов: Алеша, Боря, Витя, Гриша, Дима и Костя. Ежедневно игрались три партии, и весь турнир окончился в пять дней. В первый день Боря играл с Алешей, а во второй – с Костей. Витя в четвертый день играл с Костей, а в пятый с Димой. Кто с кем играл в каждый день турнира?

Решение.

Обозначим шахматистов соответственно точками А, Б, В, Г, Д и К, а сыгранные ими партии – отрезками, соединяющими эти точки.

Точки лучше располагать так, чтобы при последовательном их соединении они стали вершинами правильного шестиугольника.

1) Первый день турнира. По условию в этот день Боря играл с Алешей. С кем играл Витя? Только с Гришей, так как с Димой и Костей он играл в другие дни. Следовательно, третью партию в первый день играли Дима с Костей. Построим соответствующий граф (рис. 26).

2) Второй день турнира. В этот день Боря играл с Костей, поэтому Витя, учитывая первый и пятый дни, мог играть лишь с Алешей (рис. 27).

3) Третий день турнира. Витя, с учетом всех предыдущих и последующих турнира, мог играть только с Борей. Так как Дима уже играл с Костей и Гришей, то в этот день он играл с Алешей (рис. 28). Значит Гриша играл с Костей.

4) Четвертый день турнира. Здесь нетрудно определить, кто с кем играл: Витя – с Костей, Алеша – с Гришей, Боря с Димой (рис.29) .

5) Пятый день турнира (рис. 30).

3.28. В одном купе поезда ехали четыре пассажира. Среди них не было трех человек, которые прежде были знакомы друг с другом, но один был знаком с тремя остальными. Докажите, что эти три последних пассажира прежде не были знакомы друг с другом.

3.29. Каждые две из шести ЭВМ соединены проводом. Можно ли все эти провода раскрасить в один из пяти цветов так, чтобы из каждой ЭВМ выходили пять проводов разного цвета?

Решение.Для решения начертим выпуклый шестиугольник

и проведем в нем все диагонали (рис. 31). Пусть каждая вершина шестиугольника означает однуB из ЭВМ, а каждый отрезок провод, соединяющий две ЭВМ. Занумеруем различные цвета натуральными числами от 1 до 5 для того, чтобы отличать их друг от друга. Начнем например с вершины Апроведем из нее отрезки всех пяти цветов. Перейдем к вершине В и из нее проведем четыре отрезка всех цветов с №2 по №5, учитывая, что отрезок ВА, выходящий из этой вершины, уже окрашен в цвет №1. Затем займемся вершиной С. И т. д. В итоге получаем положительный ответ на вопрос задачи.

Ответ: можно.

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

3.30. На туристском слете выяснилось, что каждый юноша знаком с 8 девушками, каждая девушка знакома с 6 юношами. Кого на слете больше: юношей или девушек?

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

Решение.

Изобразим школьника точкой, а решенную им задачу – линией исходящей из этой точки. Пусть один из школьников обозначен точкой А Проведем из нее линию. Так как каждую задачу решили два школьника , то проведенная линия соединяет точку А с другой точкой В, которая обозначает второго школьника, решившего ту же задачу. Так как каждый школьник решил две задачи, то из точки В должна выходить еще одна линия, которая соединяет точку В с еще одной точкой С и т. д.

 Скачать реферат