Олимпиадные задачи по теме «Логика и теория множеств» для 11 класса - сложность 2-3 с решениями

Чичиков играет с Ноздрёвым. Сначала Ноздрёв раскладывает 1001 орех по трём коробочкам. Посмотрев на раскладку, Чичиков называет любое целое число <i>N</i> от 1 до 1001. Далее Ноздрёв должен переложить, если надо, один или несколько орехов в пустую четвёртую коробочку и предъявить Чичикову одну или несколько коробочек, где в сумме ровно <i>N</i> орехов. В результате Чичиков получит столько мертвых душ, сколько орехов переложил Ноздрёв. Какое наибольшее число душ может гарантировать себе Чичиков, как бы ни играл Ноздрёв?

Из 239 неотличимых на вид монет две – одинаковые фальшивые, а остальные – одинаковые настоящие, отличающиеся от фальшивых по весу. Как за три взвешивания на чашечных весах без гирь выяснить, какая монета тяжелее – фальшивая или настоящая? Сами фальшивые монеты находить не нужно.

Говорящие весы произносят вес, округлив его до целого числа килограммов (по правилам округления: если дробная часть меньше 0,5, то число округляется вниз, а иначе – вверх; например, 3,5 округляется до 4). Вася утверждает, что, взвешиваясь на этих весах с одинаковыми бутылками, он получил такие ответы весов:<div align="center"><img src="/storage/problem-media/116812/problem_116812_img_2.gif"></div> Могло ли такое быть?

На окружности отмечено 2<i>n</i> + 1  точек, делящих её на равные дуги  (<i>n</i> ≥ 2).  Двое по очереди стирают по одной точке. Если после хода игрока все треугольники с вершинами в ещё отмеченных точках – тупоугольные, он выигрывает, и игра заканчивается. Кто выиграет при правильной игре: начинающий игру или его противник?

Банк обслуживает миллион клиентов, список которых известен Остапу Бендеру. У каждого есть свой PIN-код из шести цифр, у разных клиентов коды разные. Остап Бендер за один ход может выбрать любого клиента, которого он еще не выбирал, и подсмотреть у него цифры кода на любых <i>N</i> позициях (у разных клиентов он может выбирать разные позиции). Остап хочет узнать код миллионера Корейко. При каком наименьшем <i>N</i> он гарантированно сможет это сделать?

Белая ладья стоит на поле b2 шахматной доски 8×8, а чёрная – на поле c4. Игроки ходят по очереди, каждый – своей ладьей, начинают белые. Запрещается ставить свою ладью под бой другой ладьи, а также на поле, где уже побывала какая-нибудь ладья. Тот, кто не может сделать ход, проигрывает. Кто из игроков может обеспечить себе победу, как бы ни играл другой? (За ход ладья сдвигается по горизонтали или вертикали на любое число клеток, и считается, что она побывала только в начальной и конечной клетках этого хода.)

После обеда на <i>прозрачной</i> квадратной скатерти остались тёмные пятна общей площади <i>S</i>. Оказалось, что если сложить скатерть пополам вдоль любой из двух линий, соединяющих середины противоположных её сторон, или же вдоль одной из двух её диагоналей, то общая видимая площадь пятен будет равна <i>S</i>₁. Если же сложить скатерть пополам вдоль другой её диагонали, то общая видимая площадь пятен останется равна <i>S</i>. Какое наименьшее значение может принимать величина  <i>S</i>₁ : <i>S</i>?

На собрание пришло <i>n</i> человек  (<i>n</i> > 1).  Оказалось, что у каждых двух из них среди собравшихся есть ровно двое общих знакомых.

  а) Докажите, что каждый из них знаком с одинаковым числом людей на этом собрании.

  б) Покажите, что <i>n</i> может быть больше 4.

В Академии Наук 999 академиков. Каждая научная тема интересует ровно троих академиков, и у каждых двух академиков есть ровно одна тема, интересная им обоим. Докажите, что можно выбрать 250 тем из их общей области научных интересов так, чтобы каждый академик интересовался не более чем одной из них.

100 пиратов сыграли в карты на золотой песок, а потом каждый посчитал, сколько он в сумме выиграл либо проиграл. У каждого проигравшего хватает золота, чтобы расплатиться. За одну операцию пират может либо раздать всем поровну золота, либо получить с каждого поровну золота. Докажите, что можно за несколько таких операций добиться того, чтобы каждый получил (в сумме) свой выигрыш либо выплатил проигрыш. (Разумеется, общая сумма выигрышей равна сумме проигрышей.)

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

Два мага сражаются друг с другом. Вначале они оба парят над морем на высоте 100 метров. Маги по очереди применяют заклинания вида "уменьшить высоту парения над морем на <i>a</i> метров у себя и на <i>b</i> метров у соперника", где <i>a, b</i> – действительные числа,  0 < <i>a</i> < <i>b</i>.  Набор заклинаний у магов один и тот же, их можно использовать в любом порядке и неоднократно. Маг выигрывает дуэль, если после чьего-либо хода его высота над морем будет положительна, а у соперника – нет. Существует ли такой набор заклинаний, что второй маг может гарантированно выиграть (как бы ни действовал первый), если при этом число заклинаний в наборе

  а) конечно;  б) бесконечно?

По кругу стоят 100 напёрстков. Под одним из них спрятана монетка. За один ход разрешается перевернуть четыре напёрстка и проверить, лежит ли под одним из них монетка. После этого их возвращают в исходное положение, а монетка перемещается под один из соседних с ней напёрстков. За какое наименьшее число ходов наверняка удастся обнаружить монетку?

Игровое поле представляет собой полоску1<i>× N </i>. В начале игры на нескольких крайних левых полях стоит по одной белой шашке, на стольких же крайних правых полях — по одной чёрной шашке. Белые и Чёрные ходят по очереди, начинают Белые. Ход заключается в передвижении одной из своих шашек в направлении противника (Белые ходят направо, Чёрные — налево). Можно делать простой ход или бить шашки соперника. При простом ходе разрешается перемещать шашку на любое число клеток, но нельзя перепрыгивать ни через свои шашки, ни через чужие. Бьют шашки соперника по тем же правилам, что и в обычных шашках: Шашка бьёт шашку соперника, стоящую на соседнем поле, если следующее за ним поле свободно. При этом своя шашка перемещается на это свободное поле, а побитая шашка соперника снимается с д...

Двое играют на треугольной доске (см. рис.), закрашивая по очереди на ней треугольные клеточки. Одна клетка (начальная) уже закрашена перед началом игры. Первым ходом закрашивается клеточка, граничащая (по стороне) с начальной, а каждым следующим ходом — клетка, граничащая с только что закрашенной. Повторно клетки красить нельзя. Тот, кто не может сделать ход, проигрывает. Кто — начинающий или его соперник — победит в этой игре, как бы ни играл его партнёр? Рассмотрите случаи: а) Начальная клетка — угловая, поле любого размера; б) Поле и начальная клетка как на рисунке к этому заданию; в) Общий случай: поле любого размера, и начальная клетка в нём произвольная. г)<b>Дополнительное задание.</b>Можно подумать, что начальная клетка определяет исход партии независимо от действий иг...

Два игрока ходят по очереди. Перед началом игры у них есть поровну горошин. Ход состоит в передаче сопернику любого числа горошин. Не разрешается передавать такое количество горошин, которое до этого уже кто-то в этой партии передавал. Ноль горошин тоже передавать нельзя. Тот, кто не может сделать очередной ход по правилам, — считается проигравшим. Кто — начинающий или его соперник — победит в этой игре, как бы ни играл его партнёр? Рассмотрите случаи: а) У каждого по две горошины; б) У каждого по три горошины; в) У каждого по десять горошин; г) Общий случай: у каждого по<i> N </i>горошин.

В ряд слева направо лежит 31 кошелёк, в каждом по 100 монет. Из одного кошелька часть монет переложили: по одной монете в каждый из кошельков справа от него. За один вопрос можно узнать суммарное число монет в любом наборе кошельков. За какое наименьшее число вопросов можно гарантированно вычислить "облегчённый" кошелёк?

На левую чашу весов положили два шара радиусов 3 и 5, а на правую — один шар радиуса 8. Какая из чаш перевесит? (Все шары изготовлены целиком из одного и того же материала.)

Пете и Васе подарили одинаковые наборы из <i>N</i> гирь, в которых массы любых двух гирь различаются не более, чем в 1,25 раз. Пете удалось разделить все гири своего набора на 10 равных по массе групп, а Васе удалось разделить все гири своего набора на 11 равных по массе групп. Найдите наименьшее возможное значение <i>N</i>.

На острове живут100рыцарей и100лжецов, у каждого из них есть хотя бы один друг. Рыцари всегда говорят правду, а лжецы всегда лгут. Однажды утром каждый житель произнес либо фразу "Все мои друзья – рыцари", либо фразу "Все мои друзья – лжецы", причем каждую из фраз произнесло ровно100человек. Найдите наименьшее возможное число пар друзей, один из которых рыцарь, а другой – лжец.

При каком наименьшем $n$ для любого набора $A$ из $2007$ множеств найдется такой набор $B$ из $n$ множеств, что каждое множество набора $A$ является пересечением двух различных множеств набора $B$?

На столе лежат  <i>N</i> > 2  кучек по одному ореху в каждой. Двое ходят по очереди. За ход нужно выбрать две кучки, где числа орехов взаимно просты, и объединить эти кучки в одну. Выиграет тот, кто сделает последний ход. Для каждого <i>N</i> выясните, кто из играющих может всегда выигрывать, как бы ни играл его противник.

Фокусник с завязанными глазами выдаёт зрителю 29 карточек с номерами от 1 до 29. Зритель прячет две карточки, а остальные отдаёт ассистенту фокусника. Ассистент указывает зрителю на две из них, и зритель называет номера этих карточек фокуснику (в том порядке, в каком захочет). После этого фокусник угадывает номера карточек, спрятанных у зрителя. Как фокуснику и ассистенту договориться, чтобы фокус всегда удавался?

Андрей и Борис играют в следующую игру. Изначально на числовой прямой в точке<i> p </i>стоит робот. Сначала Андрей говорит расстояние, на которое должен сместиться робот. Потом Борис выбирает направление, в котором робот смещается на это расстояние, и т.д. При каких<i> p </i>Андрей может добиться того, что за конечное число ходов робот попадет в одну из точек 0 или 1 вне зависимости от действий Бориса?

Клетчатая прямоугольная сетка <i>m</i>×<i>n</i> связана из верёвочек единичной длины. Двое делают ходы по очереди. За один ход можно разрезать (посередине) не разрезанную ранее единичную верёвочку. Если не останется ни одного замкнутого верёвочного контура, то игрок, сделавший последний ход, считается проигравшим. Кто из игроков победит при правильной игре и как он должен для этого играть?