141. Сколько можно образовать 7-значных чисел из цифр 1, 2, ..., 8 с тем, чтобы цифра 2 входила в каждое число не менее чем 3 раза? 142. Пусть p1, p2, ..., pn - различные простые числа. Сколько делителей имеет число q = p1p2 .p n , включая 1 и q? 143. Каким числом способов можно разделить колоду из 36 карт пополам так, чтобы в первой и во второй пачке было по 2 туза? 144. В вещевой лотерее разыгрывается 8 предметов. Первый человек вынимает из урны 5 билетов. Каким числом способов он может их вынуть, чтобы: а) было ровно два выигрыша; б) по крайней мере два выигрыша. Всего билетов 50. 145. Даны 2п элементов. Рассматриваются всевозможные раз биения их на пары, причем их разбиения, отличающиеся только порядком элементов внутри пар и порядком расположения пар, считаются совпадающими. Сколько таких разбиений? 146. Сколькими способами можно выбрать 3 пары из п шах матистов? 147. Из колоды в 36 карт наудачу без возвращения вынимают по одной карте 3 раза. Сколько существует различных способов получения 3-х карт, среди которых на первых двух местах - буб на, а на третьем - пика? 24 148. На полке наудачу располагаются 10 книг: а) сколько существует различных способов расположения 10-ти книг? б) сколько существует различных способов расположения 10-ти книг, при которых 2 заранее помеченные книги окажутся рядом? в) сколько существует различных способов расположения 10-ти книг, при которых 3 заранее помеченные книги окажутся рядом? 149. В кондитерском магазине продавались четыре сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить семь пирожных? 150. За круглый стол садятся n мужчин и n женщин. Два лица одного пола не могут сидеть рядом. Сколькими способами можно их рассадить? 151. Группа из 41 студентов успешно сдала сессию из трех экзаменов. Возможные оценки - 3, 4, 5. Доказать, что по крайней мере 5 студентов сдали сессию с одинаковыми оценками. 152. Сколько существует n-значных чисел, у которых сумма цифр равна к (к < 9) ? 153. Сколько существует n-значных натуральных чисел, у которых цифры располагаются в неубывающем порядке? 154. Какова вероятность, купив один билет, угадать в спортлото (из 49): ровно к номеров (k = 1, 2, ..., 6)? 155. Какова вероятность, купив один билет, угадать в спортлото (из 49) хотя бы к номеров? n! 156. Доказать, что X------:------= kn, где суммирование ведется n1!n 2!... nk! по всем упорядоченным разбиениям n на к слагаемых n = n1 + n2+... + nk. 157. Доказать с помощью комбинаторных рассуждений тождество: n , , X d n ,(m- 1)" - k = m n к =0 158. Сколько существует чисел от 0 до 10n, в которые не входит две идущие друг за другом одинаковые цифры? 159. Сколькими способами можно выбрать 6 карт из 52 так, чтобы были карты каждой масти? 25 160. Доказать, что произведение последовательных натураль ных к чисел делится на к\ 161. Доказать, что число последовательностей длины п с элементами из к-элементного множества, содержащих каждый элемент этого множества по крайней мере 1 раз, равно k\S(n, к). 162. Доказать, что число бинарных последовательностей длины n, не содержащих единиц ни в каких двух соседних позициях, равно числу Фибоначчи Fn+1. 163. Найти производящую функцию следующей последова тельности: 165. Доказать, что п С ^1 = кСП. 166. Доказать, что сП+1 = СП + С ^ 1 + С Й +... + С°_ к. 167. Каких чисел больше среди первого миллиона: тех, в записи которых есть 1 или где ее нет? 168. Доказать, что (3п)\ делится на (п\) без остатка. 169. Сколькими способами n-элементное множество делится на два непустых подмножества? 170. Доказать, что в треугольнике Паскаля сумма чисел, сто ящих в п +1 строке, равна 2п . 171. В каких строках треугольника Паскаля все числа нечет ные? 172. Найти количество 6-значных чисел, в десятичной записи которых есть хотя бы одна четная цифра. Найти производящие функции: f (п) 0, п = 0 а п / п\, п = 1,2,... п +1, п = 0,1,... N 0, п > N +1 26 173. Сколько существует бинарных симметрических матриц порядка п? 174. 50 человек пришли на банкет. Найти вероятность того, что обратно хотя бы один из них уйдет в своей шляпе (подразу мевается, что банкет удался и шляпы будут разбираться случайным образом). 175. Определить число различных бинарных квадратных матриц порядка п, содержащих в каждой из первых m строк по r единиц, а в каждой из остальных строк по q единиц. 176. Определить число различных бинарных квадратных матриц порядка п, в каждой строке и в каждом столбце которых стоит по одной единице. 177. Из чисел от 1 до п составлены всевозможные произ ведения, состоящие из к различных сомножителей (к фиксировано). Сколько полученных произведений делится на простое число р<=п? 178. При условии, что никакие три диагонали выпуклого п- угольника (п < 5) не пересекаются в одной точке, найти число отрезков, на которые разбиваются диагонали точками пересечения. 179. На плоскости даны пять точек. Среди прямых, соединя ющих эти точки, нет параллельных, перпендикулярных и совпа дающих. Проводим через каждую точку перпендикуляры ко всем прямым, которые можно построить, соединяя попарно остальные четыре точки. Каково максимальное число точек пересечения этих перпендикуляров между собой, не считая данных пяти точек? 180. На окружности дано п точек и проведены всевозможные хорды, соединяющие эти точки. Известно, что никакие три из проведенных хорд не пересекаются в одной точке. На сколько частей разбивается круг? 181. В розыгрыше первенства страны по футболу участвуют 20 команд. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже игравшие между собой? 182. На шахматную доску произвольным образом поставили две ладьи (черную и белую). Что вероятнее: эти ладьи могут побить друг друга или нет? 27 183. Шахматная доска размером 6x6 покрыта 18 костями домино размером 2 x 1 (таким образом, что каждая кость покры вает две клетки). Доказать, что при любом таком покрытии доску можно разрезать на две части по горизонтальной или вертикальной прямой, не повредив ни одной кости домино. 184. Клетки шахматной доски занумерованы по порядку числами от 1 до 64: первый горизонтальный ряд слева направо — числами от 1 до 8, второй горизонтальный ряд слева направо - числами от 9 до 16 и т. д. На доске расставлены 8 ладей так, чтобы они не били друг друга. Какое значение может принимать сумма номеров клеток, на которых стоят ладьи? 185. В каждой клетке шахматной доски размером n х n по ставили число, указывающее количество прямоугольников, в кото рые входит эта клетка. Чему равна сумма всех поставленных чи сел? 186. Доказать, что из любых пяти грибов, растущих в лесу и не расположенных на одной прямой, всегда можно найти четыре таких, которые служат вершинами выпуклого четырехугольника. 187. В городе N живет человек, совершающий ежедневно про гулку и проходящий при этом путь длины п. Расстояние между со седними перекрестками равно 1. Этот человек никогда не движется на северо-запад или северо-восток. На каждом перекрестке он с ве роятностью 1/2 поворачивает или на юго-восток, или на юго-запад. Если путь начинается в точке А, то какова вероятность этому человеку в конце прогулки попасть в к-й перекресток n-го ряда? 188. Доказать, что вероятность попасть в четные перекрестки n-го ряда равна вероятности попасть в нечетные перекрестки n-го ряда (см предыдущую задачу). Какое свойство сочетаний СП из этого следует? 189. В уравнении ах = b параметры a и b выбираются наудачу соответственно из сегментов l<a<m, 1 < b< п. Какова вероятность того, что корень этого уравнения будет больше 1, при условии, что т, п, а, b — натуральные числа? 190. (т, п) — точка с целыми неотрицательными координатами тип. Найти число различных путей длины т+п, ведущих из начала координат в точку (т, п) и состоящих из отрезков, параллельных осям координат, при условии, что концами отрезков служат точки с целочисленными координатами. Теория графов 215. Спортивное соревнование проводится по круговой схеме: каждая пара игроков встречается между собой ровно один раз. Докажите, что в любой момент времени найдутся хотя бы два игрока, проведшие одинаковое число встреч. 216. В соревнованиях по круговой схеме с пятью участника ми только Ваня и Леша сыграли одинаковое число встреч, а все остальные различное. Сколько встреч сыграли Ваня и Леша? 217. Каждый из 17 ученых переписывается с остальными. В их переписке речь идет лишь о трех темах. Каждая пара ученых переписывается друг с другом только по одной теме. Доказать, что не менее 3 ученых переписываются друг с другом по одной теме. 218. В футбольном турнире 20 команд сыграли 8 туров: каждая команда сыграла с восьмью разными командами. Дока жите, что найдутся три команды, не сыгравшие между собой ни одного матча. 219. В некотором государстве система авиалиний устроена так, что любой город соединен авиалиниями не более чем с тремя другими и из любого города в любой другой можно перелететь, сделав не более одной пересадки. Какое наибольшее число горо дов может быть в этом государстве? 220. У каждого из депутатов парламента не более трех про тивников. (Если депутат А - противник депутата В, то депутат В - противник депутата А.) Докажите, что депутатов можно разбить на две палаты так, что каждый депутат будет иметь не более одного противника в своей палате. 221. В теннисном турнире каждый игрок команды «синих» встречается с каждым игроком команды «красных». Число игроков в командах одинаково и не больше восьми. «Синие» выиграли в четыре раза больше встреч, чем «красные». Сколько человек в каждой из команд? 222. Каждый из семи мальчиков имеет не менее трех братьев. Докажите, что все мальчики - братья. 223. В каждой из трех школ учится по 300 человек. Любой ученик имеет в сумме 301 знакомого из двух других школ. Дока 38 жите, что можно выбрать по одному ученику из каждой школы так, чтобы выбранные ученики были знакомы между собой. 224. Летом Иван отдыхал в молодежном лагере «Восход», где вместе с ним находилось 53 школьника. После окончания отдыха некоторые пары обменялись адресами, причем у каждого из отдыхающих оказалось не менее 26 адресов. Через некоторое время Ивану понадобился адрес Николая, с которым он адресом не обменивался. Докажите, что Иван может узнать адрес Нико лая, т. е. существует цепочка из школьников, которая начинается с Ивана и оканчивается Николаем и в которой каждая пара соседей обменялась адресами. 225. Маша отдыхала в молодежном лагере «Росинка», где вместе с ней находилось 45 школьников. После окончания отды ха 950 пар обменялись адресами. Через некоторое время Маше понадобился адрес Ирины, с которой она не обменивалась адре сами. Докажите, что с помощью отдыхающих в лагере Маша может найти адрес Ирины (см. предыдущую задачу). 226. Докажите, что в группе из шести человек всегда найдутся три человека, знакомые между собой, или три человека, не знакомые между собой. 227. В международном фестивале участвовало несколько сотен делегатов из разных стран мира. Выяснилось, что из трех любых делегатов, по крайней мере, двое могут объясниться между собой на каком-то языке. Докажите, что найдется тройка делегатов, в которой каждый может объясниться с каждым. 228. В некоторой компании любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Докажите, что в этой компании все имеют одинаковое число знакомых. 229. Про некоторую компанию известно, что если два чело века из нее знакомы, то они имеют одинаковое в этой компании число знакомых, а если незнакомы - то разное. Докажите, что в компании из семидесяти человек обязательно найдется один, имеющий не менее одиннадцати знакомых. 230. Про некоторую компанию известно, что каждый человек знаком в ней ровно с шестью людьми, и для любой группы из 39 шести человек найдется член компании, знакомый с каждым из этой шестерки. Сколько человек в компании? 231. В лагере отдыхают 50 школьников. Известно, что среди любых четырех школьников найдется, по крайней мере, один, знакомый с тремя остальными. Докажите, что найдется школь ник, знакомый со всеми остальными школьниками. 232. На конгресс собрались ученые, среди которых есть зна комые. Оказалось, что никакие двое ученых, имеющих на конгрессе равное число знакомых, не имеют общих знакомых. Докажите, что найдется ученый, который имеет только одного знакомого. 233. В трехмерном пространстве 9 точек расположены так, что никакие три из них не лежат на одной прямой. Каждая точка соединена отрезками ровно с четырьмя другими. Докажите, что найдутся три отрезка, образующие треугольник. 234. Может ли в государстве, в котором из каждого города выходят ровно три дороги, быть ровно 100 дорог? 235. Группа, в составе которой Петр совершил туристскую поездку, состояла из пятнадцати человек. Вернувшись из путе шествия, Петр рассказал, что каждый участник группы был ранее знаком ровно с пятью другими участниками. Возможно ли это? 236. Одиннадцать школьников, уезжая на каникулы, догово рились, что каждый из них пошлет открытки трем из остальных. Может ли оказаться так, что каждый получит открытки именно от тех, кому напишет сам. 237. Докажите, что число людей, живших когда-либо на Зем ле и сделавших нечетное число рукопожатий, четное. 238. Можно ли на плоскости так нарисовать 9 отрезков, что бы каждый из них пересекался ровно с тремя другими? 239. Города страны соединены авиалиниями. Из столицы выходит 21 линия, из города Дальний - одна, а из каждого из остальных городов - по двенадцать линий. Докажите, что из столицы можно долететь до города Дальний (возможно с пере садками). 240. Среди 9 мушкетеров некоторые поссорились и вызвали друг друга на дуэль. Оказалось, что нет ни одной такой тройки мушкетеров, в которой все должны драться между собой. 40 Докажите, что найдется четверка мушкетеров, в которой нет ни одной пары поссорившихся. 241. В стране некоторые пары городов соединены авиа линиями, причем каждый город соединен не менее, чем с поло виной других городов. Докажите, что можно найти такой мар шрут облета городов, который начинается и заканчивается в од ном и том же городе и каждый город посещается ровно один раз. 242. Печатная плата представляет собой пластинку из изолирующего материала, в специально изготовленные гнезда которой устанавливают электронные приборы. В качестве проводников, соединяющих эти приборы, служат напыленные металлический дорожки. Поскольку проводники не изолируются, то дорожки не должны пересекаться. Если это может произойти, то дорожку переносят на другую сторону платы. Конструктор Иванов придумал хорошую схему печатной платы, которая состоит из 12 приборов и 32 проводников, соединяющих их. Можно ли изготовить такую плату так, чтобы все проводники были расположены на одной ее стороне? 243. Пусть А - матрица смежности помеченного графа на n вершинах. Какой смысл имеет a3 (i, i) ? 244. Сколь много ребер может иметь n-вершинный граф без треугольников? 245. Сколь много ребер может иметь n-вершинный граф, степени вершин которого < d ? 246. Расставить 8 ферзей на шахматной доске так, чтобы они не били друг друга. 247. Доказать непланарность графа Петерсена. 248. Существуют ли графы, степени вершин которых есть: а) 2, 2, 2, 3, 4, 5, 5, 5, 7, 7; б) 2, 2, 2, 3, 4, 5, 5, 5, 7, 7, 7. 249. Найти хроматическое число n-вершинного дерева Tn (n>1). 250. Указать число компонент связанности леса, имеющего 76 вершин и 53 ребра. 251. Показать, что граф с n вершинами и числом ребер больше (n-1)(n-2)/2 связен. 41 252. Показать, что для любого натурального t существует однородный степени 3 граф с 6t вершинами, каждая вершина которого принадлежит одному треугольнику. 253. Граф, вершинами которого являются все к-подмножест- ва некоторого n-множества, а два к-подмножества соединены ребром о их пересечение содержат ровно I элементов, называется (n, к, 1)-графом. Определить порядок и размерность (число ребер) (n, к, 1)-графа. Является ли он регулярным? 254. Графом n-перестановок называется граф, вершины которого - все перестановки элементов n-элементного множест ва, и две вершины смежны о одна из них преобразуется в дру гую транспозицией двух элементов. Указать порядок, размер ность и степень каждой вершины графа n-перестановок. Является ли граф регулярным? 255. Изобразить на плоскости граф 3-перестановок. 256. Определить количество деревьев на 6 вершинах (с точ ностью до изоморфизма). 257. Изобразить все неизоморфные деревья на 7 вершинах. 258. Каково число помеченных (р, д)-графов? 259. Перечислить все помеченные деревья на 4 вершинах. 260. Найти 1-факторизацию графа k4. 261. Найти 1-факторизацию графа кз,з. 262. Указать 1-факторизацию графа к8. 263. Представить граф к9 в виде суммы 4 основных простых циклов. 264. е-графом назовем граф, каждая вершина которого имеет четную степень. Определить число помеченных е-графов с р вершинами. 265. Реализовать граф к6 с минимальным количеством пере сечений ребер. 266. Привести примеры графов, не являющихся графами пересечений интервалов на числовой прямой. 267. Два людоеда и два миссионера должны переправиться на другой берег реки. Лодка выдерживает двоих. На одном берегу не может находиться людоедов больше, чем миссионеров, т. к. они имеют привычку поедать своих святых наставников. Как осуществить переправу? 42 268. Найти такую раскраску ребер полного 5-графа, что ни один 3-подграф не является монохроматическим. 269. Шахматная доска раскрашена 10 красками так, что клетки, имеющие общую сторону, окрашены в разные цвета, причем, все 10 красок использованы. Две краски называются соседними, если существуют окрашенные ими соседние клетки, то есть клетки, имеющие общую сторону. Чему равно наименьшее число пар соседних красок? 270. Государство Филиппины расположено на островах. Между некоторыми из островов ежедневно курсируют тепло ходы (один рейс в одном направлении и один в противо положном). С любого острова можно добраться на любой другой, возможно с пересадками. Полиция Филиппин пригласила Крутого Уокера для помощи в поимке опасного преступника. Преступник суеверен и не плывет на теплоходе 13 числа каждого месяца и каждый понедельник. Уокер не суеверен. Кроме того, он с помощью агентуры всегда знает, на каком острове находится преступник. Докажите, что если Уокер и преступник будут пользоваться только теплоходами, то Уокер, в конце концов, окажется на одном острове с преступником. 271. В некотором поселке 1000 жителей. Ежедневно каждый из них делится новостями, узнанными вчера, со всеми своими знакомыми. Известно, что с течением какого-то времени любая новость становится известна всем жителям. Докажите, что можно выбрать 90 жителей так, что если одновременно сообщить им некоторую новость, то через 10 дней она станет известной всем жителям поселка. 272. Алексей пошел в тир с отцом. Уговор был такой: Алек сей делает пять выстрелов и за каждое попадание получает право еще на два выстрела. Алексей выстрелил 25 раз. Сколько раз он попал? 273. Борцовский турнир с 13 участниками проводится по олимпийской системе, при которой проигравший выбывает. На одну встречу, с учетом подготовки к ней и отдыха участников, отводится час. Сколько времени нужно, чтобы провести турнир, если в распоряжении организаторов только 5 борцовских ковров? 43 274. Есть бактерия, которая делится на 3 бактерии. В даль нейшем появляются бактерии, которые могут делиться на 4 бак терии, могут на 2, а могут и не делиться. Образовалось 102 бакте рии. Определите число делений, если известно, что число бактерий, разделившихся на 2, в 6 раз больше, чем число бакте рий, разделившихся на 4. 275. Насыщенным углеводородом называется соединение угле рода C, имеющее валентность 4, и водорода H, имеющее ва лентность 1, в котором при заданном числе атомов углерода содержится наибольшее число атомов водорода. Найдите формулу насыщенного углеводорода, содержащего n атомов углерода. 276. В городе с любой станции метро можно проехать на любую другую. Докажите, что одну из станций можно закрыть на ремонт без права проезда через нее так, чтобы из любой оставшейся станции можно было проехать на любую другую. 277. Турист, который приехал в город Минск на поезде, весь день прогулял по городу. Поужинав на площади Бангалор, он решил вернуться на вокзал, следуя по тем улицам, которые уже проходил нечетное число раз. Докажите, что такое возвращение возможно. 278. Из какого минимального числа кусков проволоки можно спаять каркас куба? (Толщина всех ребер каркаса должна быть одинаковой). 279. На пир при дворе короля Артура собралось четное число рыцарей, которые либо дружат, либо враждуют. Оказалось, что у каждого из рыцарей друзей больше, чем врагов. Докажите, что волшебник Мерлин может так рассадить рыцарей за круглым столом, что справа и слева от каждого из них будет сидеть друг. 280. Мэрия решила построить в каждом квартале города, имеющего 155 перекрестков и 260 отрезков улиц между пере крестками, универсам. Сколько будет построено универсамов? 281. Имеются 3 дома и 3 колодца. Каждый хозяин пользуется любым из трех колодцев. В некоторый момент обитатели домов поссорились и решили проложить свои дорожки до колодцев так, чтобы они не пересекались. Возможно ли это? 282. Мышка грызет куб сыра с ребром 3, разбитый на 27 еди ничных кубиков. Когда мышка съедает какой-либо кубик, она пере 44 ходит к другому кубику, имеющему общую грань с предыдущим. Может ли мышка съесть весь куб, кроме центрального кубика? 283. Можно ли так соединить дорожками пять домов, чтобы дорожки не пересекались и каждая пара домов была соединена одной дорожкой? (Две дорожки считаются пересекающимися, если они имеют хотя бы одну общую точку.) 284. Нефтяная компания имеет несколько перекачивающих станций, которые соединены нефтепроводами. Группа диверсан тов должна вывести из строя систему нефтепроводов, взорвав несколько станций так, чтобы образовались хотя бы две станции, между которыми нельзя было перекачать нефть. Докажите, что для этой цели достаточно взорвать не более пяти станций. 285. Может ли существовать такая пятерка государств, в которой каждая пара государств соседствует друг с другом? (Граница каждого государства является замкнутой кривой. Соседними считаются государства, имеющие общую границу ненулевой длины.) 286. На карте Англии нет точек, в которых сходятся границы более чем трех графств. Докажите, что: а) четное число графств имеет нечетное число соседей; б) существует графство, которое имеет не более пяти соседей. 287. Докажите, что у любого выпуклого многогранника найдутся две грани с одинаковым числом ребер. 288. Докажите, что не существует выпуклого многогранника, у которого все грани шестиугольники. 289. Докажите, что для раскраски произвольной геогра фической карты, при которой две любые соседние страны окра шены в различные цвета, достаточно шести красок. (Рассмат риваются карты, в которых граница любой страны состоит из одной замкнутой линии, а соседними считаются страны, имеющие общую границу ненулевой длины). 290. Докажите, что для раскраски произвольной географичес кой карты (см. предыдущую задачу) достаточно пяти красок. 291. Дорожная полиция для наблюдения за порядком в городе собирается установить телекамеры на его перекрестках. Каждая телекамера контролирует перекресток, на котором она установлена, все улицы, выходящие из этого перекрестка, 45 включая и соседние перекрестки. Сколько нужно установить телекамер, если в городе 75 перекрестков, а наибольшее число телекамер, которое можно установить так, чтобы ни одна из них не наблюдала за другой, равно 30. 292. Дорожная полиция установила 30 телекамер на пере крестках города (см. предыдущую задачу). Известно, что это наибольшее количество телекамер, которые можно расставить так, чтобы ни одна из них не наблюдала другую. Докажите, что можно так проложить, не более 30 маршрутов патрулирования, чтобы каждый перекресток посещался только одной патрульной машиной и каждый маршрут содержал любой отрезок улицы между двумя перекрестками не более одного раза. (Некоторые участки улиц могут не посещаться патрульными машинами.) 293. Нефтяная компания решила установить автозаправочные колонки на перекрестках улиц города, который имеет 282 отрез ков улиц. Решено было не устанавливать более одной колонки на соседних перекрестках. Известно, что в городе на каждом перекрестке сходится не менее четырех улиц. Докажите, что при этих условиях компания не сможет установить более 70 колонок. 294. Нефтяная компания решила установить автозаправочные колонки на улицах города так, чтобы на отрезках улиц, выхо дящих из одного перекрестка, было не более одной колонки. Известно, что в городе 210 отрезков улиц и на одном перекрестке сходится самое большее 6 улиц. Докажите, что при этих условиях может быть установлено не менее 20 колонок. 295. Полицейские участки размешаются на перекрестках города, причем для любого перекрестка участок находится или на этом перекрестке, или на соседнем. Известно, что в городе 155 перекрестков и на каждом из них сходится не более шести улиц. Докажите, что в городе не менее 23 полицейских участков. 296. На вечере собралось несколько юношей и девушек. При этом оказалось, что для любой группы юношей число девушек, знакомых хотя бы с одним из юношей этой группы, будет не меньше числа юношей в группе. Докажите, что все юноши могут одновременно танцевать в парах со знакомыми девушками. 297. На вечере среди собравшихся было 20 юношей. Ока залось, что для любых к юношей число девушек, знакомых хотя 46 бы с одним из юношей, не меньше, чем (к - 10). Докажите, что не менее половины юношей могут одновременно танцевать в паре со знакомой девушкой. 298. На вечере первые два танца каждый из юношей танцевал с одной из своих знакомых девушек, возможно, первый танец с одной, а второй - с другой. Некоторые танцевали два танца, неко торые - один, а очень застенчивые не танцевали ни разу. Дока жите, что третий танец могут танцевать все юноши, танцевавшие первый танец, и все девушки, танцевавшие второй. 299. Среди участников вечера несколько юношей и девушек имеют одинаковое наибольшее число знакомых противополож ного пола. Докажите, что все они могут одновременно танцевать в паре со своими знакомыми. 300. На математической олимпиаде предлагалось 16 задач. Оказалось, что каждый из 16 школьников решил две задачи и каждую задачу решили два школьника. Докажите, что можно организовать разбор задач таким образом, что каждый школьник расскажет одну из решенных им задач. 301. На математической олимпиаде предлагалось n задач. Оказалось, что каждый из n школьников решил к задач и каждую задачу решили к школьников. Докажите, что можно организовать разбор задач таким образом, что каждый школьник расскажет одну из решенных задач и все задачи будут разобраны. 302. Каждые два из шести компьютеров соединены своим проводом. Укажите, как раскрасить каждый из этих проводов в один из пяти цветов, чтобы из каждого компьютера выходило пять проводов разного цвета. 303. Можно ли соединить нечетное число приборов разно цветными проводами так, чтобы из каждого прибора выходили провода разных цветов и цветов было на один меньше, чем приборов.