Две фирмы по очереди нанимают программистов, среди которых есть $4$ гения. Первого программиста каждая фирма выбирает произвольно, а каждый следующий должен быть знаком с кем-то из ранее нанятых данной фирмой. Если фирма не может нанять программиста по этим правилам, она прекращает приём, а другая может продолжать. Список программистов и их знакомств заранее известен. Могут ли знакомства быть устроены так, что фирма, вступающая в игру второй, сможет нанять по крайней мере $3$ гениев, как бы ни действовала первая фирма?
Ответ:
Решение:
Дан треугольник, у которого нет равных углов. Петя и Вася играют в такую игру: за один ход Петя отмечает точку на плоскости, а Вася красит её по своему выбору в красный или синий цвет. Петя выиграет, если какие-то три из отмеченных им и покрашенных Васей точек образуют одноцветный треугольник, подобный исходному. За какое наименьшее число ходов Петя сможет гарантированно выиграть (каков бы ни был исходный треугольник)?
Ответ:
Решение:
Петя и Вася играют в игру. Для каждых пяти различных переменных из набора $x_1, \ldots, x_{10}$ имеется единственная карточка, на которой записано их произведение. Петя и Вася по очереди берут по карточке, начинает Петя. Когда все карточки разобраны, Вася присваивает переменным значения как хочет, но так, что $0\leqslant x_1\leqslant\ldots\leqslant x_{10}$. Может ли Вася гарантированно добиться того, чтобы сумма произведений на его карточках была больше, чем у Пети?
Ответ:
Решение:
В ряд лежат $100N$ бутербродов, каждый с колбасой и сыром. Дядя Фёдор и кот Матроскин играют в игру. Дядя Фёдор за одно действие съедает один бутерброд с одного из краёв. Кот Матроскин за одно действие может стянуть колбасу с одного бутерброда (а может ничего не делать). Дядя Фёдор каждый ход делает по 100 действий подряд, а кот Матроскин делает только 1 действие; дядя Фёдор ходит первым, кот Матроскин вторым, далее ходы чередуются до тех пор, пока дядя Фёдор не доест все бутерброды. Дядя Фёдор выигрывает, если последний съеденный им бутерброд был с колбасой. Верно ли, что при каждом натуральном $N$ он сможет выиграть независимо от ходов кота Матроскина?
Ответ:
Решение:
Ответ:
Решение:
На острове расположено несколько деревень. Между некоторыми деревнями проложены дороги. Известно, что из любой деревни в любую другую можно добраться, причём по единственному маршруту. Также известно, что есть четыре деревни, из которых выходят $5$, $6$, $7$ и $9$ дорог соответственно, а из остальных деревень выходит ровно по одной дороге. Сколько деревень может быть на острове?
Ответ:
Решение:
В караване $17$ верблюдов. В понедельник каждый верблюд плюнул ровно в $N$ других верблюдов. При каком наименьшем $N$ можно гарантировать, что нашлись два верблюда, которые плюнули друг в друга?
Ответ:
Решение:
В Империи Вестероса было 1000 городов и 2017 дорог (каждая дорога соединяет какие-то два города). Из каждого города можно было проехать в каждый. Однажды злой волшебник заколдовал $N$ дорог, и ездить по ним стало нельзя. Образовалось 7 королевств, так, что в каждом королевстве можно добраться из любого города в любой по дорогам, а из одного королевства в другое по дорогам добраться нельзя. При каком наибольшем $N$ это возможно?
Ответ:
Решение:
В компьютерном центре стоит 200 компьютеров, некоторые из них (попарно) соединены кабелями, всего использовано 345 кабелей. Будем называть «кластером» множество компьютеров, такое, что из любого компьютера этого множества сигнал по проводам может добраться до всех остальных. В начале все компьютеры образовывали один кластер. Но однажды ночью злой хакер перерезал несколько кабелей так, что образовалось 8 кластеров. Найдите наибольшее возможное число кабелей, которые были перерезаны.
Ответ:
Решение:
В турнире по волейболу участвовало 20 команд. Каждая команда играла со всеми остальными по одному разу, за выигрыш начислялось 3 очка, за проигрыш очки не начислялись (ничьих в волейболе нет). Очки, набранные командами, образуют убывающую арифметическую прогрессию. Сколько очков набрала команда, занявшая второе место?
Ответ:
Решение:
В некотором государстве $35$ городов. Каждая пара городов соединена авиарейсом одной из двух авиакомпаний. Оказалось, что из каждого города выходит ровно $12$ авиарейсов первой авиакомпании. Назовём тройку городов $A$, $B$, $C$ замкнутой, если все три авиарейса $AB$, $BC$, $CA$ осуществляются одной авиакомпанией. Каково наибольшее возможное количество замкнутых троек городов может быть в этом государстве?
Ответ:
Решение:
Каждый из участников школьного кружка, кроме Андрея, дружит с разным числом других участников. Андрей дружит с $9$ из них. Каково наибольшее возможное число школьников в кружке?
Ответ:
Решение:
Английский клуб посещают $20$ джентльменов. Некоторые из них знакомы (знакомства взаимные, т. е. если $A$ знает $B$, то и $B$ знает $A$). Известно, что в клубе нет трех попарно знакомых между собой джентльменов. Однажды джентльмены пришли в клуб, и каждая пара знакомых пожала друг другу руки (один раз). Какое наибольшее число рукопожатий могло быть сделано?
Ответ:
Решение:
В городе $10$ проспектов и $23$ улицы, которые образуют прямоугольную сетку: все улицы параллельны между собой и все проспекты перпендикулярны улицам (см. рис.). Точку пересечения улицы и проспекта будем называть «перекрёстком». Городские власти проводят дорожные работы на некоторых участках дороги (отрезок улицы или проспекта между соседними перекрёстками). Во время ремонта ездить по этому участку нельзя. Какое наибольшее количество участков можно ремонтировать одновременно, чтобы при этом из любого перекрестка можно было проехать на любой другой?
Ответ:
Решение:
В шахматном кружке провели турнир — каждый сыграл с каждым по одной партии. Оказалось, что для любой тройки участников среди результатов их взаимных партий есть хотя бы одна ничья и хотя бы одна игра с победителем. Какое наибольшее число игроков могло участвовать в турнире?
Ответ:
Решение:
Пете необходимо спаять электрическую схему, состоящую из $10$ чипов, соединённых между собой проводами (один провод соединяет два различных чипа; два чипа может соединять не более одного провода), при этом из одного чипа должно выходить $9$ проводов, из одного — $8$, из одного — $7$, из двух — по $5$, из трёх — по $3$, из одного — $2$, из одного — $1$. Может ли Петя спаять такую схему?
Ответ:
Решение:
В турнире каждый участник встретился с каждым из остальных один раз. Каждую встречу судил один арбитр, и все арбитры судили разное количество встреч. Игрок Иванов утверждает, что все его встречи судили разные арбитры. То же самое утверждают о себе игроки Петров и Сидоров. Может ли быть, что никто из них не ошибается?
Ответ:
Решение:
В турнире по футболу участвует $2n$ команд ($n\gt 1$). В каждом туре команды разбиваются на $n$ пар и команды в каждой паре играют между собой. Так провели $2n-1$ тур, по окончании которых каждая команда сыграла с каждой ровно один раз. За победу давалось $3$ очка, за ничью — $1$, за поражение — $0$ очков. Оказалось, что для каждой команды отношение набранных ею очков к количеству сыгранных ею игр после последнего тура не изменилось. Докажите, что все команды сыграли вничью все партии.
Ответ:
Решение:
Волейбольный чемпионат с участием 16 команд проходил в один круг (каждая команда играла с каждой ровно один раз, ничьих в волейболе не бывает). Оказалось, что какие-то две команды одержали одинаковое число побед. Докажите, что найдутся три команды, которые выиграли друг у друга по кругу (то есть $A$ выиграла у $B$, $B$ выиграла у $C$, а $C$ выиграла у $A$).
Ответ:
Решение:
Сколькими способами можно начертить линию \[ x\sin\sqrt{16-x^2-y^2}=0 \] без отрывов и повторов, т. е. не отрывая карандаша и не проводя более одного раза по одной и той же линии.
Ответ:
Решение: