Нестандартные задачи по математике
Решение.
Изобразим два множества множество корзин и множество их номеров. В каждом из этих множеств по пять элементов обозначим их точками
Установим соответствие между этими двумя множествами так, чтобы условия задачи выполнялись. Будем соответствующие элементы двух множеств соединять сплошными линиями, а не соответствующие – пунктирными или совсем не соединять. Так как яблоки первого сорта лежат только в корзине Д, то именно этой корзине и нужно дать номер 1; проведем сплошную линию между точками Д и 1. Далее номер 2 можно присвоить только корзине В, а после этого номер 5 – лишь корзине Г. Наконец, номера 3 и 4 дадим корзинам А и Б ( в любом порядке ).
Ответ: корзины расположились, начиная с №1, в последовательном порядке Д, В, А, Б, Г или в порядке Д, В, Б, А, Г.
3.2. Петр, Геннадий, Алексей и Владимир занимаются в одной детской спортивной школе в разных секциях: гимнастики, легкой атлетики, волейбола и баскетбола. Петр, Алексей и волейболист учатся в одном классе. Петр и Геннадий на тренировки ходят пешком вместе, а гимнаст ездит на автобусе. Легкоатлет не знаком ни с волейболистом, ни с баскетболистом. Кто в какой секции занимается?
3.3.Футбольные команды пяти школ города учавствуют в розыгрыше кубка. В финал кубка выходят две команды. До соревнований пять болельщиков высказали прогнозы, что в финал выйдут команды:
1) Б и Г, 2) В и Д , 3) Б и В, 4) А и Г, 5) Г и Д.
Один прогноз оказался полностью неверным, в остальных была правильно названа только одна из команд-финалисток. Какие команды вышли в финал?
3.4. Три товарища – Владимир, Игорь и Сергей – окончили один и тот же педагогический институт и преподают математику, физику и литературу в школах Тулы, Рязани и Ярославля. Владимир работает не в Рязани, Игорь – не в Туле. Рязанец преподает не физику, Игорь – не математику, туляк преподает литературу. Какой предмет и в каком городе преподает каждый из них?
3.5. Среди офицеров А, Б, В и Г – майор, капитан и два лейтенанта. А и один из лейтенантов – танкисты, Б и капитан – артиллеристы, А младше по званию, чем В. Определите род войск и воинское звание каждого из них.
3.6. В стране Радонежии некоторые города связаны между собой авиалиниями. Из столицы выходит 1985 авиалиний, из города Дальнего одна, а из остальных городов - по 20 линий. Докажите, что из столицы можно добраться до Дальнего.
Решение.
Рассмотрим множество городов, до которых можно добраться из столицы. Это граф: его вершины - города, ребра - авиалинии, их соединяющие. Из каждой вершины графа выходит столько ребер, сколько всего авиалиний выходит из соответствующего города. Граф содержит нечетную вершину - столицу. Поскольку число нечетных вершин в графе четно, в нем есть еще одна нечетная вершина. Этой вершиной может быть только город Дальний.
Задачи, при решении которых используются вершины, стороны и диагонали многоугольника
3.7. Можно ли организовать футбольный турнир девяти команд так, чтобы каждая команда провела по четыре встречи?
Решение
Изобразим каждую команду точкой, а проведенную ею встречу – отрезком, исходящим из этой точки. Девять точек лучше расположить так, чтобы при последовательном соединении их отрезками образовался выпуклый девятиугольник.
Задача сводиться к следующей: можно ли девять точек соединить отрезками так, чтобы из каждой точки выходили четыре отрезка? Другими словами, существует ли граф с деятью вершинами, у которого степень каждой вершины равна 4?
Прежде всего проведем все стороны девятиугольника; они будут означать, что каждая команда провела две встречи.
Для
того чтобы
получить еще
две встречи
будем, например,
соединять все
вершины диагоналями
через одну (
рис. 19 ). ( Целесообразно
для всех держаться
одной и той же
системы проведения
из них отрезков,
иначе решение
усложнится.
) После этого
все получается.
Ответ: можно.
3.8. Можно ли провести футбольный турнир восьми команд так, чтобы каждая команда провела: а) по четыре встречи; б) по пять встреч
3.9. Можно ли провести футбольный турнир семи команд так, чтобы каждая команда провела по три встречи?
Решение.
Попытки решить эту задачу тем же методом, что и предыдущие задачи, приводят к неудаче. Возникает подозрение, что провести турнир таким образом нельзя.
Для того чтобы доказать нашу гипотезу, попробуем вместо рисунка подсчитать общее число встреч, которые надо провести командам. Оно равно 7 (3/2). Но это число не является целым.
Ответ: нельзя.
3.10. Докажите что общее число вершин графа, которые имеют нечетную степень четно.
3.11. В трех вершинах правильного пятиугольника расположили по фишке. Разрешается передвигать их по диагонали в любую свободную вершину. Можно ли таким образом добиться того, чтобы одна из фишек вернулась на свое место, а две другие поменялись местами?
3.12. Дан правильный 45-и угольник. Можно ли так расставить в его вершинах цифры от 0 до 9 так, чтобы для любой пары различных цифр нашлась сторона, концы которой занумерованы этими цифрами.
Указание.
Рассмотреть полный граф, вершины которого суть цифры от 0 до 9. Задача сводится к его обходу.
3.13. Докажите что общее число вершин графа, которые имеют нечетную степень четно.
Решение.
Обозначим число вершин графа, имеющих нечетную степень, через k, а степени таких вершин – соответственно через а1, а2,…, аk. Кроме того, у графа могут быть вершины с четной степенью; обозначим степени этих вершин соответственно через b1, b2,…, bn.
Допустим, что число k нечетно. Подсчитаем общее число ребер графа. Оно равно [(а1 + а2 +…+ аk) + (b1 + b2 +…+ bn)] /2.
Сумма в первых круглых скобках числителя полученной дроби есть число нечетное, как сумма нечетного числа нечетных слагаемых, а сумма во вторых скобках число четное. Но тогда весь числитель – число нечетное, а значит дробь не является натуральным числом. Мы пришли к противоречию.
3.14. Можно ли 15 телефонов соединить между собой так, чтобы каждый из них был связан ровно с 11 другими?
3.15. Девять школьников, разъезжаясь на каникулы, договорились, что каждый из них пошлет открытки пятерым из остальных. Может ли оказаться, что каждый из них получит открытки именно от тех друзей, которым напишет сам?
3.16. В шахматном турнире в один круг участвуют 17 шахматистов. Верно ли, что в любой момент турнира найдется шахматист, сыгравший к этому моменту четное число партий ( может быть ни одной )?
Задачи на обведение контура фигуры непрерывной линией
3.17. В 18 веке город Кенигсберг ( ныне Калининград в составе нашей страны ) был расположен на берегах реки и двух островах. Различные части города были соединены семью мостами (рис. 20). Можно ли обойти все эти мосты так, чтобы побывать на каждом из них ровно один раз?
Это и есть задача Эйлера о кенигсбергских мостах, о которой упоминалось в начале параграфа.
Решение.
Обозначим различные части города буквами А, В, С и К и изобразим их точками. Мосты изобразим линиями, соединяющими эти точки. Получим граф ( рис. 21).
Задача сводится к следующей: существует ли путь, проходящий по всем ребрам графа, причем по каждому ребру только один раз?
Рассмотрим два случая.
1) Предположим, что существует такой замкнутый путь. Тогда степень каждой вершины графа должна быть четной, так как, входя в какую-либо вершину, мы затем должны из нее выйти, причем по другому ребру. Что касается начала пути, то после выхода из него мы должны в конце концов в него и вернуться, поскольку путь замкнутый. Однако на рисунке 20 нет ни одной вершины, степень которой была бы четной. Значит этот случай невозможен.
2)Пусть существует такой незамкнутый путь; например, пусть он начинается в вершине А, а заканчивается в С.
Тогда из вершин А и С должно выходить уже нечетное число ребер, а из промежуточных вершин В и К – по-прежнему четное число. Но на рисунке степени вершин В и К нечетны. Следовательно, и этот случай отпадает.
Ответ: нельзя.
Хотя рассуждение проведенное при решении задачи 3.13, выполнено для частного случая, оно носит общий характер:
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. В школьном турнире в один круг играют шесть шахматистов: Алеша, Боря, Витя, Гриша, Дима и Костя. Ежедневно игрались три партии, и весь турнир окончился в пять дней. В первый день Боря играл с Алешей, а во второй – с Костей. Витя в четвертый день играл с Костей, а в пятый с Димой. Кто с кем играл в каждый день турнира?
Решение.
Обозначим шахматистов соответственно точками А, Б, В, Г, Д и К, а сыгранные ими партии – отрезками, соединяющими эти точки.
Точки лучше располагать так, чтобы при последовательном их соединении они стали вершинами правильного шестиугольника.
Первый день турнира. По условию в этот день Боря играл с Алешей. С кем играл Витя? Только с Гришей, так как с Димой и Костей он играл в другие дни. Следовательно, третью партию в первый день играли Дима с Костей. Построим соответствующий граф (рис. 26).
Второй день турнира. В этот день Боря играл с Костей, поэтому Витя, учитывая первый и пятый дни, мог играть лишь с Алешей (рис. 27).
Третий день турнира. Витя, с учетом всех предыдущих и последующих турнира, мог играть только с Борей. Так как Дима уже играл с Костей и Гришей, то в этот день он играл с Алешей (рис. 28). Значит Гриша играл с Костей.
Четвертый день турнира. Здесь нетрудно определить, кто с кем играл: Витя – с Костей, Алеша – с Гришей, Боря с Димой (рис.29) .
Пятый день турнира (рис. 30).
3.28. В одном купе поезда ехали четыре пассажира. Среди них не было трех человек, которые прежде были знакомы друг с другом, но один был знаком с тремя остальными. Докажите, что эти три последних пассажира прежде не были знакомы друг с другом.
3.29. Каждые две из шести ЭВМ соединены проводом. Можно ли все эти провода раскрасить в один из пяти цветов так, чтобы из каждой ЭВМ выходили пять проводов разного цвета?
Решение.Для решения начертим выпуклый шестиугольник
и проведем в нем все диагонали (рис. 31). Пусть каждая вершина шестиугольника означает однуB из ЭВМ, а каждый отрезок провод, соединяющий две ЭВМ. Занумеруем различные цвета натуральными числами от 1 до 5 для того, чтобы отличать их друг от друга. Начнем например с вершины Апроведем из нее отрезки всех пяти цветов. Перейдем к вершине В и из нее проведем четыре отрезка всех цветов с №2 по №5, учитывая, что отрезок ВА, выходящий из этой вершины, уже окрашен в цвет №1. Затем займемся вершиной С. И т. д. В итоге получаем положительный ответ на вопрос задачи.
Ответ: можно.
На рисунке 31 каждые две вершины графа соединены своим ребром. Такой граф называется полным.
3.30. На туристском слете выяснилось, что каждый юноша знаком с 8 девушками, каждая девушка знакома с 6 юношами. Кого на слете больше: юношей или девушек?
3.30. На кружке, в котором участвуют шесть школьников, было дано шесть задач. Каждый школьник решил две задачи, и каждую задачу решили два школьника. Докажите, что разбор задач можно организовать так, чтобы каждый школьник изложил решение одной из решенных им задач и все задачи были разобраны.
Решение.
Изобразим школьника точкой, а решенную им задачу – линией исходящей из этой точки. Пусть один из школьников обозначен точкой А.. Проведем из нее линию. Так как каждую задачу решили два школьника , то проведенная линия соединяет точку А с другой точкой В, которая обозначает второго школьника, решившего ту же задачу. Так как каждый школьник решил две задачи, то из точки В должна выходить еще одна линия, которая соединяет точку В с еще одной точкой С и т. д.
Возможны следующие случаи.
Может получиться шестиугольник. Тогда утверждение задачи выполняется.
Может получиться четырехугольник и «двуугольник» ; последнее возможно тогда, когда два школьника решили одни и те же задачи.
Могут получиться два треугольника.
Могут получиться три «двуугольника».
Этим исчерпываются все возможности. В каждом из рассмотренных случаев утверждение задачи выполняется.
3.31. На столе в приемной парикмахерской лежат журналы. Каждый клиент парикмахерской просмотрел два журнала; каждый журнал просмотрели три человека; для каждой пары журналов имеется только один клиент, который их просмотрел. Сколько журналов и сколько клиентов в приемной парикмахерской?
Решение.
Обозначим журнал точкой, а клиента, просмотревшего этот журнал – отрезком, выходящим из этой точки.
Возьмем одну такую точку А. Так как каждый журнал просмотрели три человека, то из точки А должны выходить три отрезка. Так как каждый клиент просмотрел два журнала, то каждый
Отрезок соединят две точки. (рис. 32).
Поскольку каждую пару журналов просмотрел один человек, то нужно каждую пару точек соединить отрезком. Получаем четырехугольник с диагоналями (рис. 33). Проверьте еще сами, что здесь все три условия задачи выполняются.
Может возникнуть вопрос: а не существует ли еще хотя одна , пятая точка Е, такая, что все условия задачи выполняются? Тогда из каждой из пяти точек будет выходить не по три, а по четыре отрезка, а это противоречит условиям задачи.
Ответ: 4 журнала, 6 клиентов.
3.32. В одном учреждении каждый сотрудник выписывает две газеты, каждую газету выписывает пять человек и каждую пару газет выписывает только один человек. Сколько человек в учреждении и сколько они выписывают газет.
3.33. Шесть точек, из которых никакие три не лежат на одной прямой соединены всевозможными отрезками и каждый отрезок окрашен в черный или красный цвет. Докажите, что найдется треугольник с вершинами в данных точках, у которого все стороны черные, или треугольник, у которого все стороны красные.
Решение.
Возьмем одну из шести точек А1более четырех отрезков ( по обобщенному принципу Дирихле ). Пусть отрезки А1А2, А1А3 и А1А4 – красные. Рассмотрим два случая.
Допустим, что среди отрезков А2А3, А2А4 и А3А4 имеется красный, например отрезок А2А3. Тогда у треугольника А1А2А3 все стороны красные. Именно этот вариант изображен на рисунке 34.
Если допустим, что среди отрезков А2А3, А2А4 и А3А4 нет красного, тогда все эти отрезки – черные, а следовательно у треугольника А2А3А4 все стороны черные.
3.34. Докажите, что если в задаче 3.33 вместо шести точек взять пять, треугольник с одноцветными сторонами может и не найтись.
3.35. В международном туристическом лагере шесть туристов познакомились между собой. Выяснилось, что среди любых трех из них имеются двое, которые могут разговаривать друг с другом на каком-нибудь языке. Верно ли, что среди них найдутся трое, каждый из которых может разговаривать с каждым из двух других на каком- нибудь языке?
3.36. 17 ученых из разных стран переписываются между собой на одном из трех языков: английском, французском или русском. Докажите, что среди них найдутся трое, которые переписываются между собой на одном и том же языке.
Решение.
Обозначим каждого из ученых точкой и соединим эти точки всевозможными отрезками. Точки расположим так, чтобы никакие три из них не лежали на одной прямой. Так как каждый ученый переписывается с 16 остальными, то из каждой точки выходит 16 отрезков. Каждый из отрезков, означающий переписку ученых на английском языке, окрасим в черный цвет, на французском – в красный, на русском – в белый.
Рассмотрим два случая.
Пусть среди отрезков, соединяющих точки А2, А3, А4, А5, А6 и А7 попарно между собой, имеется черный, скажем А2А3. Тогда у треугольника А1А2А3 все стороны черные, т. е. соответствующая тройка ученых переписываются между собой на английском языке.
Пусть среди этих отрезков нет черного. В этом случае отрезки между шестью точками А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 обойти конем по одному разу и вернуться в исходную клетку?
Решение.
Каждым ходом конь меняет цвет клетки, поэтому, если существует обход, то число черных клеток равно числу белых, что неверно.
4.3. Дан куб 6х6х6. Найти максимально возможное число параллелепипедов 4х1х1 (со сторонами параллельными сторонам куба), которые можно поместить в этот куб без пересечений.
Идея решения.
Легко поместить 52 параллелепипеда внутрь куба. Докажем, что нельзя больше. Разобьем куб на 27 кубиков 2х2х2. Раскрасим их в шахматном порядке. При этом образуется 104 клетки одного цвета (белого) и 112 - другого (черного). Осталось заметить, что каждый параллелепипед содержит две черных и две белых клетки.
Ответ: 52.
4.4. Прямая раскрашена в 2 цвета. Докажите, что найдутся 3 точки А, В, С одного цвета такие, что AB = ВС.
4.5. Раскрасьте прямую в 3 цвета так, чтобы нельзя было найти трех точек А, В, С разного цвета таких, что AB = ВС.
5. Плоскость раскрашена а) в 2 цвета, б) в 3 цвета. Докажите, что найдутся 2 точки одного цвета, расстояние между которыми равно 1
Идею, вынесенную в заглавие, хорошо иллюстрирует следующая задача. 4.6. Имеется квадрат 8Х8, у которого удалены две угловые клетки, расположенные на одной диагонали. Можно ли этот квадрат замостить костяшками домино размерами 1Х2? Решение дает нам правильная «шахматная» раскраска этой доски. Каждая костяшка домино закрывает две клетки разного цвета, в то время как клеток черного и белого цветов различное количество.
А вот еще две задачи на эту идею.
4.7. Участок прямоугольной формы разбит на квадраты, образующие n рядов по m квадратов в каждом ряду. Каждый квадрат является отдельным участком, соединенным калитками со всеми соседними участками. При каких m и n можно обойти все квадратные участки, побывав в каждом по одному разу, и вернуться в первоначальный?
Решение.
Раскрасим квадраты в шахматном порядке. При каждом переходе меняется цвет квадрата. Поэтому, если такой маршрут возможен, то число шагов должно быть четным, т. е. m или n четно. Осталось проверить, что в этом случае искомый маршрут возможен.
4.8. Все мы в детстве играли в «морской бой». Напомним, что играется он на квадрате 10Х10, на клетчатой бумаге. «Линкором» в этой игре называется «корабль» 1х4. В связи с этим возникает вопрос: можно ли весь квадрат для морского боя разрезать на 25 линкоров? А кстати, ответьте еще на один вопрос: какое наименьшее число «выстрелов» надо сделать, чтобы наверняка хотя бы один раз попасть в линкор, одиноко плавающий по морю?
Решение.
Раскрасим клетки в 4 цвета, как на рис. 36. Каждый «линкор» закрывает четыре клетки разного цвета. Но клеток цвета 2 всего 26, а «линкоров» должно быть 25.
Эта же раскраска помогает ответить и на второй вопрос. Наименьшее число выстрелов равно числу клеток цвета 4, т. е. 24.
5. Задачи с целыми числами. Четные и нечетные числа
Обычно четные и нечетные числа связывают только с натуральными числами. Здесь мы