На некотором собрании присутствовало $n$ человек. Известно, что каждые два знакомых из них не имеют никаких общих знакомых, а каждые два незнакомых между собой лица имеют ровно двух общих знакомых.
а) Доказать, что все присутствующие имеют одно и то же число знакомых.
б) При каких $n$ возможно условие задачи?
Подробнее
В городе «Многообразие» живут 10 000 жителей, каждые два из которых либо враждуют, либо дружат между собой. Каждый день не более чем один житель города может «начать новую жизнь», т.е. перессориться со всеми своими друзьями и подружиться со всеми врагами; при этом любые три жителя могут подружиться между собой. Доказать, что все без исключения жители могут подружиться между собой. Какого наименьшего числа дней наверное достаточно для этого?
Подробнее
В стране Оз имеется несколько замков, из каждого из которых ведут три пути. Странствующий рыцарь выедал из своего родового замка и пустился в путешествие по стране. Рыцарь любит разнообразие; поэтому, доезжая до очередного замка, он каждый раз поворачивает налево, если в предшествующий раз повернул направо, и поворачивает направо, если до этого он повернул налево. (Проезжая первый на своем пути замок, рыцарь может повернуть в любую сторону.) Докажите, что когда-нибудь рыцарь вернется в свой замок.
Подробнее
При дворе короля Артура собрались $2n$ рыцарей, причем каждый из них имеет среди присутствующих не более $n - 1$ врагов. Доказать, что Мерлин - советник Артура - может так рассадить рыцарей за круглым столом, что ни один из них не будет сидеть рядом со своим врагом.
Подробнее
а) Известно, что среди 80 монет имеется одна фальшивая, более легкая, чем остальные, имеющие все одинаковый вес. При помощи четырех взвешиваний на чашечных весах без гирь найти фальшивую монету.
б) Известно, что среди $n$ монет есть одна фальшивая, более легкая, чем остальные, имеющие все одинаковый вес. Каково наименьшее число $k$ такое, что $k$ взвешиваниями на чашечных весах без гирь всегда можно выделить фальшивую монету?
Подробнее
Некоторые из 20 металлических кубиков, одинаковых по размеру и внешнему виду, алюминиевые, остальные - дюралевые (более тяжелые). Как при помощи не более 11 взвешиваний на чашечных весах без гирь определить число дюралевых кубиков?
Примечание. В задаче предполагается, что все кубики могут быть алюминиевые, но дюралевыми все они быть не могут (ведь, если бы все кубики оказались одного веса, то без этого условия мы никак не смогли бы определить, алюминиевые они или дюралевые).
Подробнее
Среди 12 монет имеется одна фальшивая. Известно, что фальшивая монета отличается по весу от настоящих, но не известно, легче она настоящих или тяжелее. Настоящие монеты все одного веса. С помощью трех взвешиваний на чашечных весах без гирь выделить фальшивую монету и одновременно установить, легче она или тяжелее остальных.
Подробнее
а) К хозяину гостиницы однажды пришел постоялец, не имевший денег, но обладавший серебряной цепочкой, состоящей из семи звеньев. Хозяин согласился держать этого постояльца неделю, при условии, что тот будет ему ежедневно отдавать в виде платы одно из звеньев цепочки. Какое наименьшее число звеньев надо распилить для того, чтобы владелец цепочки смог ежедневно в течение семи дней расплачиваться с хозяином (быть может, забирая у него при этом отданные ранее звенья и выдавая взамен их другие)?
б) Цепь состоит из 2000 звеньев. Какое наименьшее число звеньев надо распилить для того, чтобы любое число звеньев от 1 до 2000 можно было набрать, взяв некоторое число из образовавшихся частей?
Подробнее
В городе Лиссе все станции метро связаны между собой, т. е. с любой станции можно проехать (возможно с пересадками) на любую другую. Доказать, что при этом можно закрыть одну станцию метро (без права проезда через нее) так, чтобы с любой из оставшихся станций можно было проехать на любую другую станцию.
Подробнее
На всех улицах города Зурбагана существовало двустороннее движение. Когда, однако, городским властям потребовалось произвести ремонт всех дорог, они вынуждены были временно ввести на части улиц одностороннее движение, оставив движение на остальных улицах двусторонним; после этого, напротив, односторонним было сделано движение по тем улицам, которые ранее не ремонтировались, а по улицам, где движение ранее было односторонним, снова было разрешено ехать в обоих направлениях. При этом в период ремонта дорог в обоих случаях можно было проехать из любого пункта Зурбаганэ в любой другой. Доказать, что в Зурбагане можно ввести одностороннее движение по всем улицамч так, чтобы проезд из любого пункта города в любой другой оставался возможным.
Подробнее
В стране Дельфинии имеется $n$ городов, каждые два из которых соединены шоссе, причем движение по всем шоссе является односторонним. Доказать, - что если $n \neq 2$ или 4, го направления движения по шоссе можно выбрать так, чтобы из каждого города в любой другой можно было попасть с заездом не более чем еще в один город; если же $n = 2$ или 4, то так движение организовать нельзя.
Подробнее
В Швамбрании имеется 100 городов; при этом если два города $A$ и $B$ не соединены прямой телефонной связью, то имеются регулярные авиарейсы из $A$ в $B$ и наоборот, а если между $A$ и $B$ прямая телефонная связь есть, то таких рейсов нет. Известно, что в Швамбрании каждые два города могут быть (может быть - через- посредство нескольких промежуточных пунктов) соединены между собой телефоном и что из каждого города в каждый другой можно долететь самолетом, - возможно, с несколькими посадками в пути. Докажите, что в Швамбрании имеются такие 4 города, что из каждого из них можно и дозвониться и долететь в любой другой, используя, в случае необходимости, в качестве промежуточных пунктов лишь два других города этой четверки.
Подробнее
Можно ли ходом шахматного коня попасть из левого нижнего угла доски в правый верхний, побывав на каждом поле ровно один раз?
Подробнее
На шахматной доске размером $1000 \times 1000$ клеток стоит белый король и 499 черных ладей. Доказать, что при произвольном положении фигур (и при произвольной игре черных) король может «сыграть в поддавки», т. е. за ряд ходов стать на находящееся под боем одной из ладей поле, вынудив тем самым себя побить. (Фигуры на нашей доске ходят по обычным правилам.)
Подробнее
12 полей расположены по кругу и на четырех соседних полях стоят четыре разноцветные фишки; красная, желтая, зеленая и синяя.
Одним ходом можно передвинуть любую фишку с поля, на котором она стоит, через четыре любых поля на пятое (если оно свободно) в любом из двух возможных направлений. После нескольких ходов фишки могут стать снова на те же четыре поля. Как они могут при этом переставиться?
Подробнее