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

Можно ли множество всех натуральных чисел разбить на непересекающиеся конечные подмножества  <i>A</i>₁, <i>A</i>₂, <i>A</i>₃, ...  так, чтобы при любом натуральном <i>k</i> сумма всех чисел, входящих в подмножество <i>A_k</i>, равнялась  <i>k</i> + 2013?

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

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

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

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

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

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

На столе лежит куча из более чем <i>n</i>² камней. Петя и Вася по очереди берут камни из кучи, первым берёт Петя. За один ход можно брать любое простое число камней, меньшее <i>n</i>, либо любое кратное <i>n</i> число камней, либо один камень. Докажите, что Петя может действовать так, чтобы взять последний камень независимо от действий Васи.

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

На дверце сейфа написано произведение степеней<i>a</i>^<i>n</i><i>b</i>^<i>m</i><i>c</i>^<i>k</i>. Чтобы дверца открылась, надо заменить каждую из шести букв натуральным числом так, чтобы в произведении получился куб натурального числа. Пинки, не подумав, уже заменил какие-то три буквы числами. Всегда ли Брейн сможет заменить три оставшиеся, чтобы дверца открылась?

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

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

Было8грузиков массами1,2, <i> .. </i>, 8 г. Один из них потерялся, а остальные выложили в ряд по возрастанию массы. Есть весы с лампочкой, при помощи которых можно проверить, имеют ли две группы грузиков одинаковую массу. Как за3 проверки определить, какой именно грузик потерялся?

Можно ли раскрасить натуральные числа в 2009 цветов так, чтобы каждый цвет встречался бесконечное число раз, и не нашлось тройки чисел, покрашенных в три различных цвета, таких, что произведение двух из них равно третьему?

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

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

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

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

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

Двое играющих по очереди пишут – каждый на своей половине доски – по одному натуральному числу (повторения разрешаются) так, чтобы сумма всех чисел на доске не превосходила 10000. После того, как сумма всех чисел на доске становится равной 10000, игра заканчивается подсчетом суммы всех цифр на каждой половине. Выигрывает тот, на чьей половине сумма цифр меньше (при равных суммах – ничья). Может ли кто-нибудь из игроков выиграть, как бы ни играл противник?

В каждой клетке квадрата 101<i>×</i>101, кроме центральной, стоит один из двух знаков: "поворот" или "прямо". Машинка въезжает извне в произвольную клетку на границе квадрата, после чего ездит параллельно сторонам клеток, придерживаясь двух правил:

  1) в клетке со знаком "прямо" она продолжает путь в том же направлении;

  2) в клетке со знаком "поворот" она поворачивает на 90° (в любую сторону по своему выбору).

Центральную клетку квадрата занимает дом. Можно ли расставить знаки так, чтобы у машинки не было возможности врезаться в дом?

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

Фокусник Арутюн и его помощник Амаяк собираются показать следующий фокус. На доске нарисована окружность. Зрители отмечают на ней 2007 различных точек, затем помощник фокусника стирает одну из них. После этого фокусник впервые входит в комнату, смотрит на рисунок и отмечает полуокружность, на которой лежала стертая точка. Как фокуснику договориться с помощником, чтобы фокус гарантированно удался?

Два игрока по очереди проводят диагонали в правильном (2<i>n+</i>1)-угольнике  (<i>n</i> > 1).  Разрешается проводить диагональ, если она пересекается (по внутренним точкам) с чётным числом ранее проведённых диагоналей (и не была проведена раньше). Проигрывает игрок, который не может сделать очередной ход. Кто выиграет при правильной игре?

На бесконечной в обе стороны ленте бумаги выписаны все целые числа, каждое – ровно по одному разу.

Могло ли оказаться, что между каждыми двумя числами не стоит их среднее арифметическое?

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