Сборник задач Решение задач по графам

Выполнила: Харенко Екатерина

Руководитель: Кустуртова А.С.

Актобе- 2016г.

33. Шесть городов соединены автобусными маршрутами. Стоимость проезда между этими городами указана на схеме. За какую наименьшую сумму можно проехать из города А в город В? (А) 70 (В) 80 (С) 90 (D) 100 (Е) 110

34. Ваня рассматривает свое генеалогическое дерево, где отмечены одни мужчины. Стрелка идет от отца к сыну. Как звали сына брата деда брата отца Вани?

13

2

3

29. В кафе встретились три друга: скульптор Белов, скрипач Чернов и художник Рыжов. «Замечательно, что у одного из нас белые, у другого черные, а у третьего рыжие волосы, но ни у кого цвет волос не соответствует фамилии»,- заметил черноволосый. «Ты прав»,- сказал Белов. Какой цвет волос у художника?

30. Олег, Игорь и Оля учатся в одном классе. Среди них есть лучший математик, лучший спринтер, лучший художник класса. Известно, что 1) лучший художник не рисовал своего портрета, но рисовал портрет Игоря; 2) Оля никогда не уступала мальчикам в спринте. Кто из них лучший математик, лучший спринтер, лучший художник класса?

31. Кто-то принес в класс цветы. Были высказаны различные предположения: это Андрей и Борис, Андрей и Даша, Андрей и Сергей, Борис и Даша, Борис и Володя, Володя и Галя, Галя и Даша. Учитель сказал, что в одном из этих предположений одно имя названо правильно, а второе - неправильно, во всех же остальных предположениях оба имени названы неправильно. Кто принес цветы?

32. «Сколько бабушек и прабабушек было у ваших прабабушек и прадедушек?»

12

22. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

23. В государстве 50 городов, и из каждого выходит 8 дорог. Сколько всего дорог в государстве?

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

25. Из города А в город В ведут три дороги, а из города В в город С - четыре дороги. Сколькими способами можно проехать из А в С через В?

26. Четыре футбольных команды А,В,С,D провели дуг с другом несколько тренировочных матчей. Известно, что команда А участвовала в 6 матчах, команда В - в 5 матчах, С - в 7 матчах, D - в 10 матчах. Сколько всего состоялось матчей?

27. Можно ли устроить такой турнир, чтобы в нём участвовало 10 команд и каждая команда сыграла бы ровно 5 матчей?

28. Можно ли устроить такой турнир, чтобы в нём участвовало тринадцать команд, и каждая команда сыграла бы ровно пять матчей.

11

4

5

19. Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу).

Сколько всего рукопожатий было сделано?

20. Беседуют трое друзей: Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Любопытно, что один из нас блондин, другой брюнет, а третий рыжий, но ни у одного цвет волос не соответствует фамилии». Какой цвет волос имеет каждый из друзей?

21. В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проходит по круговой системе - каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галина с Еленой; Борис, как уже говорилось, с Андреем и еще с Галиной; Виктор - с Галиной, Дмитрий с Виктором и Елена - с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось?

10

14.Можно ли провести в городе 10 автобусных маршрутов и установить на них остановки так, что какие бы 8 маршрутов ни были взяты, найдётся остановка, не лежащая ни на одном из них, а любые 9 маршрутов проходят через все остановки.

15. В классе больше 32, но меньше 40 человек. Каждый мальчик дружит с тремя девочками, а каждая девочка - с пятью мальчиками. Сколько человек в классе?

16. За круглым столом сидят несколько гостей. Некоторые из них знакомы между собой; знакомство взаимно. Все знакомые каждого гостя (считая его самого) сидят вокруг стола через равные промежутки. (Для другого человека эти промежутки могут быть другими.) Известно, что каждые двое имеют хотя бы одного общего знакомого. Докажите, что все гости знакомы друг с другом.

17. Докажите, что среди любых шести человек есть либо трое попарно знакомых, либо трое попарно незнакомых.

18. В классе учится 15 мальчиков и 15 девочек. В день 8 Марта некоторые мальчики позвонили некоторым девочкам и поздравили их с праздником (никакой мальчик не звонил одной и той же девочке дважды). Оказалось, что детей можно единственным образом разбить на 15 пар так, чтобы в каждой паре оказались мальчик с девочкой, которой он звонил. Какое наибольшее число звонков могло быть сделано?

Задачи:

1. В стране Мера расположено несколько замков. Из каждого замка ведут три дороги. Из какого-то замка выехал рыцарь. Странствуя по дорогам, он из каждого замка, стоящего на его пути, поворачивает либо направо, либо налево по отношению к дороге, по которой приехал. Рыцарь никогда не сворачивает в ту сторону, в которую он свернул перед этим. Доказать, что когда-нибудь он вернётся в исходный замок.

2. Дано несколько белых и несколько чёрных точек. Из каждой белой точки идет стрелка в каждую чёрную, на каждой стрелке написано натуральное число. Известно, что если пройти по любому замкнутому маршруту, то произведение чисел на стрелках, идущих по направлению движения, равно произведению чисел на стрелках, идущих против направления движения. Обязательно ли тогда можно поставить в каждой точке натуральное число так, чтобы число на каждой стрелке равнялось произведению чисел на ее концах?

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

6

4. Грани некоторого многогранника раскрашены в два цвета так, что соседние грани имеют разные цвета. Известно, что все грани, кроме одной, имеют число рёбер, кратное 3. Доказать, что и эта одна грань имеет кратное 3 число рёбер.

5. а) Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?

б) Какое наименьшее число раз придется ломать проволоку, чтобы всё же изготовить требуемый каркас?

6. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими?

7. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 - по 4 друга, а 10 - по 5 друзей?

8. В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?

7

9. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?

10. На лесосеке было 16 штабелей бревен по 55 штук в каждом и 12 штабелей по 42 штуки в каждом. Сколько штук бревен было на лесопилке?

11. Один автомат в минуту закрывает 60 банок, а другой на 5 банок больше. За сколько минут оба автомата при их одновременном включении закроют 2500 банок?

12. Я задумал число. Если к нему прибавить 24, потом полученную сумму умножить на 9, затем из произведения вычесть 76 и, наконец, полученную разность разделить на 19, то получится число 23. Найти задуманное число.

13. Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все они поздоровались друг с другом за руку. Сколько мальчиков поехали за город, если всего было 10 рукопожатий? 8