Решение.
Напишем цифры на листе. Соединим стрелками те цифры, которые могут следовать друг за другом (рис. 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. На кружке, в котором участвуют шесть школьников, было дано шесть задач. Каждый школьник решил две задачи, и каждую задачу решили два школьника. Докажите, что разбор задач можно организовать так, чтобы каждый школьник изложил решение одной из решенных им задач и все задачи были разобраны.
Решение.
Изобразим школьника точкой, а решенную им задачу – линией исходящей из этой точки. Пусть один из школьников обозначен точкой А.. Проведем из нее линию. Так как каждую задачу решили два школьника , то проведенная линия соединяет точку А с другой точкой В, которая обозначает второго школьника, решившего ту же задачу. Так как каждый школьник решил две задачи, то из точки В должна выходить еще одна линия, которая соединяет точку В с еще одной точкой С и т. д.
Возможны следующие случаи.
1) Может получиться шестиугольник. Тогда утверждение задачи выполняется.
2) Может получиться четырехугольник и «двуугольник» ; последнее возможно тогда, когда два школьника решили одни и те же задачи.
3) Могут получиться два треугольника.
4) Могут получиться три «двуугольника».
Этим исчерпываются все возможности. В каждом из рассмотренных случаев утверждение задачи выполняется.
3.31. На столе в приемной парикмахерской лежат журналы. Каждый клиент парикмахерской просмотрел два журнала; каждый журнал просмотрели три человека; для каждой пары журналов имеется только один клиент, который их просмотрел. Сколько журналов и сколько клиентов в приемной парикмахерской?
Решение.
Обозначим журнал точкой, а клиента, просмотревшего этот журнал – отрезком, выходящим из этой точки.
Возьмем одну такую точку А. Так как каждый журнал просмотрели три человека, то из точки А должны выходить три отрезка. Так как каждый клиент просмотрел два журнала, то каждый
Отрезок соединят две точки. (рис. 32).
Поскольку каждую пару журналов просмотрел один человек, то нужно каждую пару точек соединить отрезком. Получаем четырехугольник с диагоналями (рис. 33). Проверьте еще сами, что здесь все три условия задачи выполняются.
Может возникнуть вопрос: а не существует ли еще хотя одна , пятая точка Е, такая, что все условия задачи выполняются? Тогда из каждой из пяти точек будет выходить не по три, а по четыре отрезка, а это противоречит условиям задачи.
Ответ: 4 журнала, 6 клиентов.
3.32. В одном учреждении каждый сотрудник выписывает две газеты, каждую газету выписывает пять человек и каждую пару газет выписывает только один человек. Сколько человек в учреждении и сколько они выписывают газет.
3.33. Шесть точек, из которых никакие три не лежат на одной прямой соединены всевозможными отрезками и каждый отрезок окрашен в черный или красный цвет. Докажите, что найдется треугольник с вершинами в данных точках, у которого все стороны черные, или треугольник, у которого все стороны красные.
Решение.
Возьмем одну из шести точек А1более четырех отрезков ( по обобщенному принципу Дирихле ). Пусть отрезки А1А2, А1А3 и А1А4 – красные. Рассмотрим два случая.
1) Допустим, что среди отрезков А2А3, А2А4 и А3А4 имеется красный, например отрезок А2А3. Тогда у треугольника А1А2А3 все стороны красные. Именно этот вариант изображен на рисунке 34.
2) Если допустим, что среди отрезков А2А3, А2А4 и А3А4 нет красного, тогда все эти отрезки – черные, а следовательно у треугольника А2А3А4 все стороны черные.
3.34. Докажите, что если в задаче 3.33 вместо шести точек взять пять, треугольник с одноцветными сторонами может и не найтись.
3.35. В международном туристическом лагере шесть туристов познакомились между собой. Выяснилось, что среди любых трех из них имеются двое, которые могут разговаривать друг с другом на каком-нибудь языке. Верно ли, что среди них найдутся трое, каждый из которых может разговаривать с каждым из двух других на каком- нибудь языке?
3.36. 17 ученых из разных стран переписываются между собой на одном из трех языков: английском, французском или русском. Докажите, что среди них найдутся трое, которые переписываются между собой на одном и том же языке.
Решение.
Обозначим каждого из ученых точкой и соединим эти точки всевозможными отрезками. Точки расположим так, чтобы никакие три из них не лежали на одной прямой. Так как каждый ученый переписывается с 16 остальными, то из каждой точки выходит 16 отрезков. Каждый из отрезков, означающий переписку ученых на английском языке, окрасим в черный цвет, на французском – в красный, на русском – в белый.
Рассмотрим два случая.
1) Пусть среди отрезков, соединяющих точки А2, А3, А4, А5, А6 и А7 попарно между собой, имеется черный, скажем А2А3. Тогда у треугольника А1А2А3 все стороны черные, т. е. соответствующая тройка ученых переписываются между собой на английском языке.
2) Пусть среди этих отрезков нет черного. В этом случае отрезки между шестью точками А2, А3, А4, А5, А6 и А7 окрашены не более, чем в два цвета – красный и белый. Тогда на основании утверждения задачи 3.33 среди отрезков, соединяющих эти точки, имеются три, составляющие треугольник со сторонами одного цвета.
3.37. На плоскости даны п точек, из которых никакие три не лежат на одной прямой. Они соединены всевозможными отрезками, и каждый отрезок окрашен в один из четырех различных цветов. При каком наименьшем п обязательно найдется треугольник с одноцветными сторонами с вершинами в трех из данных точек?
3.38. Последовательность из 36 нулей и единиц начинается с пяти нулей. Среди пятерок подряд стоящих цифр встречаются все 32 возможные комбинации. Найдите пять последних цифр последовательности.
3.39. Докажите, что можно расположить по кругу символы 0 и 1 так, чтобы любой возможный набор из n символов, идущих подряд, встретился.
Указание.
Рассмотреть граф, вершины которого суть слова длины n-1. Две вершины u и v соединяются стрелкой, если существует слово длины n, у которого u является началом, а v - концом.
4. Раскраски
Говорят, что фигура покрашена в несколько цветов, если каждой точке фигуры приписан определенный цвет. Бывают задачи, где раскраска уже дана, например для шахматной доски, бывают задачи, где раскраску с данными свойствами нужно придумать, и бывают задачи, где раскраска используется как идея решения.
Задачи
4.1. Из шахматной доски вырезали две противоположные угловые клетки. Докажите, что оставшуюся фигуру нельзя разрезать на «домино» из двух клеток
Решение.
Каждая фигура «домино» содержит 1 белую и 1 черную клетку. Но в нашей фигуре 32 черных и 30 белых клеток (или наоборот).
4.2. Можно ли все клетки доски 9х9 обойти конем по одному разу и вернуться в исходную клетку?
Решение.
Каждым ходом конь меняет цвет клетки, поэтому, если существует обход, то число черных клеток равно числу белых, что неверно.