43. Задачка с 17 утюМа.

В стране Фалкерсонии некоторые города соединены авиалиниями, причем из города А в город Б нельзя попасть, сделав менее 10 пересадок. Докажите, что все авиалинии можно распродать 11 авиакомпаниям таки образом, что любой маршрут из А в Б будет проходить по линиям, принадлежащим всем 11 авиакомпаниям.

Решение. Подвесим за вершину А, скажем, что это уровень 0.

Все инцидентные её ребра покрасим в первый цвет. Смежные вершины назовем уровнем 1. Теперь все ребра, идущие от уровня 1 в вершины, пока еще без уровня, покрасим во второй цвет, а вершины, куда мы пришли, назовем уровнем 2. И т.д.

Таким образом, во все вершины, удаленные от А на длину 11 мы должны будем придти, пройти по ребрам 11 цветов.

Кстати, ребра внутри уровней мы можем красить как угодно. :)

44. Задачка с математической регаты 9 класса 2005/06 учебного года.

Возможнали такая компания, в которой у каждого ровно 10 друзей, а у любых двух - ровно 4 общих друга?

45. Задачка с 1 Северного турнира.

В Тридевятом царстве 20 городов и 3 авиакомпании. Между любыми двумя городами существуют не более одной авиалинии. Известно, что от любого города до любого другого можно долететь на самолетах не более, чем двух разных авиалиний. Какое наименьшее количество авиалиний может быть в Тридевятом царстве, если каждая авиалиния обслуживает хотя бы одну авиалинию?

46. Задачка с регаты на Турнире регионов, 2005.

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

47. Задачка с областной олимпиады 2001 года, 8 класс

Некоторая страна, в которой n городов и из каждого города в другие выходит не менее k дорог, была разбита на m частей так, что в каждой части никакие два города не соединены дорогой. Докажите, что m>=n/(n-k).

48. Задачка с московской олимпиады 1994 года, 10 класс

Каждый из 1994 жепутатов парламента дал пощечину ровно одному своему коллеге. Докажите, что можно составить парламентскую комиссию из 665 человек, члены которой не выясняли отношений между собой указанным выше способом.

49. Задачка с карусели на 2 Кубке памяти Колмогорова.

В однокруговом волейбольном турнире участвовало 23 команды. Три команды A, B, C образуют циклическую тройку, если A выиграла у B, B выиграла у C, С выиграла у A. Какое наибольшее возможное количество циклических троек?

50. Задачка с районного тура Московской областной олимпиады, 1998/99 год, 9 класс.

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

51. Задачка с командной олимпиады сеньоров 12 Кубка памяти Колмогорова.

Каждые два из 21 города соединены прямым рейсом одной из четырех авиакомпаний. Докажите, что существует замкнутый маршрут из четырех рейсов одной авиакомпании.

52. Задачка с 14 Кубка памяти Колмогорова.

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

53. Задачка с 13 Кубка памяти Колмогорова (абака, юниоры)

В графе 5 вершин и 6 ребер. Сколько вершин может иметь степень 3?

54. Задачка с 22 УТЮМа.

На вечеринке гость считается застенчивым, если у него не более трех знакомых. Оказалось, что у каждого гостя не менее трех застенчивых знакомых. Докажите, что все гости – застенчивые.

55. Задачка с 9 Кубка памяти Колмогорова.

На шахматной доске стоит k коней. Известно, что некоторые (k-1) из них могут сделать одновременно ход, после которого все кони вновь окажутся одновременно в разных клетках доски. При каком наибольшем k это возможно?

56. Задачка с 18 УТЮМа.

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

57. Задачка с заключительного этапа III олимпиады имени Эйлера.

За круглым столом сидят 40 человек. Может ли случиться, что у любых двух из них, между которыми сидит четное число человек, есть за столом общий знакомый, а у любых двух, между которыми сидит нечетное число человек, общих знакомых нет?

58. Задачка с абаки на 13 Кубке памяти Колмогорова.

В графе 5 вершин и 6 ребер. Сколько вершин могут иметь степень 3? (В графе нет петель и кратных ребер.)

59. Задачка с 11 Кубка памяти Колмогорова.

100 человек устраиваются работать на 100 различных вакантных мест. Каждый из двух агентов по трудоустройству предложил каждому из этих 100 человек одно определенное место, причем разным людям - разные места. Каждый из 100 претендентов принял одно из двух предложений, и оказалось, что все места заполнены. Докажите, что если бы каждый принял другое предложение, все места тоже оказались бы заполненными.

60. Задачка с 24 УТЮМа.

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

61. Задачка с абаки 12 Кубка памяти Колмогорова.

В полном графе на 10 вершинах удалили один цикл длины три. Сколько циклом длины 3 осталось?

62. Задачка с абаки 11 Кубка памяти Колмогорова.

В классе учится 20 человек, при этом нет трех девочек, которые имели бы поровну друзей среди одноклассников-мальчиков. Какое наименьшее число мальчиков может учиться в этом классе?

63. Задачка с 29 УТЮМа.

В классе учатся n мальчиков и n девочек. Каждый мальчик составил рейтинг девочек в порядке убывания: какая нравится ему больше всего, какая на втором месте и т.д. (никакие две девочки не нравятся никакому мальчику в одинаковой степени). На день святого Валентина каждому мальчику подарили по девочке. Обсуждая полученные подарки, мальчики заметили, что при любом другом распределении девочек хотя бы одному из них досталась бы меньша нравящаяся ему девочка. Докажите, что хотя бы один из мальчиков получил ту девочку, которая нравилась ему больше всего.

64. Задачка с 8 УТЮМа.

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

65. Задачка с 6 Кубка памяти Колмогорова.

На симпозиум приехали 100 человек. Из них 15 французов, каждый из которых знаком хотя бы с 70 участниками симпозиума, и 85 немцев, каждый из которых знаком не более, чем с 10 участниками. Их расселили в 21 комнату. Докажите, что в какой-то из комнат ни одной пары знакомых.

66. Задачка с 34 УТЮМа.

Некоторые города Графинии соединены дорогами. Из каждого города выходит не более n дорог, но среди каждых m городов есть два, соединенные дорогой, не проходящей через другие города. Какое наибольшее количество городов может быть в Графинии?

67. Задачка с 37 УТЮМа.

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

68. Задачка из книги Баранова, Стечкина.

Пусть ex(v,C_5) - наибольшее число ребер в графе на v вершинах, не содержащем в качестве подграфа граф C_5 (цикл на 5 вершинах).

Докажите, что

ex(v,C_5)=C_v^2 при 2<=v<=4;

ex(5,C_5)=7;

ex(v,C_5)=[v^2/4] при v>=6.

69. Каждый ученик школы занимается хотя бы в одном из 30 кружков, но не более чем в двух из них. Оказалось, что в каждом кружке занимается 30 человек, а для каждых двух кружков есть ученик, который посещает оба этих кружка. Какое наибольшее количество учеников может быть в этой школе?

70. Задачка с 27 УТЮМа. 

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

71. Задачка с московской олимпиады 1983 года.

В пространстве выбрано 8 точек, никакие 4 из которых не лежат в одной плоскости. Проведено 17 отрезков, у каждого из которых оба конца лежат в упомянутых точка. Докажите, что

а) отрезки образуют хотя бы один треугольник;

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

72. Задачка с 7 УТЮМа.

Во дворе дома вкопали 6 столбцов - один в центре и пять по окружности вокруг него. Центральный соединили веревками с пятью остальными. Кроме того, пять соединили по кругу веревками. Сколькими различными способами можно снять 5 веревок так, чтобы по оставшимся веревкам можно было добраться от любого столба до любого другого?

73. Задачка с 37 УТЮМа.

В кружке 6 человек и у каждого ровно 3 друга в этом кружке. Верно ли, что всех кружковцев можно рассадить за три парты, за каждой из которых сидят два друга?

74. Задачка с 8 УТЮМа.

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

75. Задачка с 8 Кубка памяти Колмогорова.

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

76. Задачка с 5 Кубка памяти Колмогорова.

Буратино,Мальвина и Пьеро приехали в страну Дураков. В этой стране 8 городов и междукаждымидвумя ходят электрички. Встолице, в Центральном Дурагенстве им предложили 28 билетов: по одному накаждый из маршрутов. По такому билету одна персона может проехать между даннымидвумя городами в любом направлении, но при выходе с электрички билетотбирается. Смогут ли друзья, взяв каждый по 8 билетов, посетить все города ивновь встретиться возле Центрального Дурагенства?

77. Задачка с московской олимпиады 1996 года.

8 школьников решали 8 задач, причем каждую задачу решили 5 школьников. Докажите, что найдутся два школьника, решившие вместе все задачи.

77. Задача из листочка группы "Кобальт" VIII Летней математической школы ЦДМО (Курган).

Ребра полного графа на 2k+1 вершине покрашены в три цвета. Докажите, что найдется связный одноцветный граф на k+1 вершине.

78. Связный граф G имеет 2007 вершин, причем степень любой вершины не более 11.Докажите, что можно выбрать 334 вершины так, чтобы любой нечетный цикл графа G проходил не только через выбранные вершины.

79. Задачка с 27 УТЮМа.

2006 школьников решали 6 задач. Оказалось, что в каждых трех работах можно найти решения по крайней мере пяти разных задач. Какое наименьшее количество решений могли сдать все школьники?

80. Задачка с 21 УТЮМа.

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

81. Задачка с 20 УТЮМа.

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