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

Петя и Вася играют в следующую игру. Петя загадывает натуральное число <i>x</i> с суммой цифр 2012. За один ход Вася выбирает любое натуральное число <i>a</i> и узнаёт у Пети сумму цифр числа  |<i>x – a</i>|.  Какое минимальное число ходов необходимо сделать Васе, чтобы гарантированно определить <i>x</i>?

Оля и Максим оплатили путешествие по архипелагу из 2009 островов, где некоторые острова связаны двусторонними маршрутами катера. Они путешествуют, играя. Сначала Оля выбирает остров, на который они прилетают. Затем они путешествуют вместе на катерах, по очереди выбирая остров, на котором еще не были (первый раз выбирает Максим). Кто не сможет выбрать остров, проиграл. Докажите, что Оля может выиграть.

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

  а) Могут ли они гарантировать результат более 500?

  б) Могут ли они гарантировать результат не менее 999?

Мишень "бегущий кабан" находится в одном из<i> n </i>окошек, расположенных в ряд. Окошки закрыты занавесками так, что для стрелка мишень все время остается невидимой. Чтобы поразить мишень, достаточно выстрелить в окошко, в котором она в момент выстрела находится. Если мишень находится не в самом правом окошке, то сразу после выстрела она перемещается на одно окошко вправо; из самого правого окошка мишень никуда не перемещается. Какое наименьшее число выстрелов нужно сделать, чтобы наверняка поразить мишень?

Среди 18 деталей, выставленных в ряд, какие-то три подряд стоящие весят по 99 г, а все остальные – по 100 г. Двумя взвешиваниями на весах со стрелкой определите все 99-граммовые детали.

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

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

В клетчатом прямоугольнике 49×69 отмечены все50<i>· </i>70вершин клеток. Двое играют в следующую игру: каждым своим ходом каждый игрок соединяет две точки отрезком, при этом одна точка не может являться концом двух проведенных отрезков. Отрезки могут содержать общие точки. Отрезки проводятся до тех пор, пока точки не кончатся. Если после этого первый может выбрать на всех проведенных отрезках направления так, что сумма всех полученных векторов равна нулевому вектору, то он выигрывает, иначе выигрывает второй. Кто выигрывает при правильной игре?

На оборотных сторонах 2005 карточек написаны различные числа (на каждой по одному). За один вопрос разрешается указать на любые три карточки и узнать множество чисел, написанных на них. За какое наименьшее число вопросов можно узнать, какие числа записаны на каждой карточке?

У Ани и Бори было по длинной полосе бумаги. На одной из них была написана буква А, на другой – Б. Каждую минуту один из них (не обязательно по очереди) приписывает справа или слева к слову на своей полосе слово с полосы другого. Докажите, что через сутки слово с Аниной полосы можно будет разрезать на 2 части и переставить их местами так, что получится то же слово, записанное в обратном порядке.

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

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

В Думе 1600 депутатов, которые образовали 16000 комитетов по 80 человек в каждом.

Докажите, что найдутся два комитета, имеющие не менее четырёх общих членов.

На столе лежат три кучки спичек. В первой кучке находится 100 спичек, во второй – 200, а в третьей – 300. Двое играют в такую игру. Ходят по очереди, за один ход игрок должен убрать одну из кучек, а любую из оставшихся разделить на две непустые части. Проигравшим считается тот, кто не может сделать ход. Кто выиграет при правильной игре: начинающий или его партнер?

Игроки <i>A</i> и <i>B</i> по очереди ходят конем на шахматной доске 1994×1994. Игрок <i>A</i> может делать только горизонтальные ходы, то есть такие, при которых конь перемещается на соседнюю горизонталь. Игроку <i>B</i> разрешены только вертикальные ходы, при которых конь перемещается на соседнюю вертикаль. Игрок <i>A</i> ставит коня на поле, с которого начинается игра, и делает первый ход. При этом каждому игроку запрещено ставить коня на то поле, на котором он уже побывал в данной игре. Проигравшим считается игрок, которому некуда ходить. Докажите, что для игрока <i>A</i> существует выигрышная стратегия.

У ведущего есть колода из 52 карт. Зрители хотят узнать, в каком порядке лежат карты (при этом не уточняя   сверху вниз или снизу вверх). Разрешается задавать ведущему вопросы вида "Сколько карт лежит между такой-то и такой-то картами?". Один из зрителей подсмотрел, в каком порядке лежат карты. Какое наименьшее число вопросов он должен задать, чтобы остальные зрители по ответам на эти вопросы могли узнать порядок карт в колоде?

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

В тюрьму поместили 100 узников. Надзиратель сказал им: "Я дам вам вечер поговорить друг с другом, а потом рассажу по отдельным камерам, и общаться вы больше не сможете. Иногда я буду одного из вас отводить в комнату, в которой есть лампа (вначале она выключена). Уходя из комнаты, вы можете оставить лампу как включенной, так и выключенной. Если в какой-то момент кто-то из вас скажет мне, что вы все уже побывали в комнате, и будет прав, то я всех вас выпущу на свободу. А если неправ - скормлю всех крокодилам. И не волнуйтесь, что кого-нибудь забудут - если будете молчать, то все побываете в комнате, и ни для кого никакое посещение комнаты не станет последним." Придумайте стратегию, гарантирующую узникам освобождение.

Из колоды вынули семь карт, показали всем, перетасовали и раздали Грише и Лёше по три карты, а оставшуюся карту

  а) спрятали;

  б) отдали Коле.

Гриша и Лёша могут по очереди сообщать вслух любую информацию о своих картах. Могут ли они сообщить друг другу свои карты так, чтобы при этом Коля не смог вычислить местонахождение ни одной из тех карт, которых он не видит? (Гриша и Лёша не договаривались о каком-либо особом способе общения; все переговоры происходят <i>открытым текстом</i>.)

В таблице из <i>n</i> столбцов и 2^<i>n</i> строк, в которых выписаны все возможные различные наборы из <i>n</i> чисел 1 и –1, некоторые числа заменены нулями. Докажите, что можно выбрать некоторое непустое подмножество строк так, что:

  а) сумма всех чисел в выбранных строках равна 0;

  б) сумма всех выбранных строк есть нулевая строка.

(Строки складываются покоординатно как векторы.)

30 учеников одного класса решили побывать друг у друга в гостях. Известно, что ученик за вечер может сделать несколько посещений, и что в тот вечер, когда к нему кто-нибудь должен прийти, он сам никуда не уходит. Покажите, что для того, чтобы все побывали в гостях у всех,

  а) четырёх вечеров недостаточно,

  б) пяти вечеров также недостаточно,

  в) а десяти вечеров достаточно,

  г) и даже семи вечеров тоже достаточно.

См. задачу <a href="https://mirolimp.ru/tasks/179385">179385</a> в) и г).

Два мудреца играют в следующую игру. Выписаны числа 0, 1, 2,..., 1024. Первый мудрец зачёркивает 512 чисел (по своему выбору), второй зачёркивает 256 из оставшихся, затем снова первый зачёркивает 128 чисел и т.д. На десятом шаге второй мудрец зачёркивает одно число; остаются два числа. После этого второй мудрец платит первому разницу между этими числами. Как выгоднее играть первому мудрецу? Как второму? Сколько уплатит второй мудрец первому, если оба будут играть наилучшим образом? (Ср. с задачей<a href="https://mirolimp.ru/tasks/178710">178710</a>и с задачей<a href="https://mirolimp.ru/tasks/178716">178716</a>.)

Белые и чёрные играют в следующую игру. В углах шахматной доски стоят два короля: белый на a1, чёрный на h8. Играющие делают ход по очереди. Начинают белые. Играющий может ставить своего короля на любое соседнее поле (если только оно свободно), соблюдая следующие правила: нельзя увеличивать расстояние между королями (расстоянием между двумя полями называется наименьшее число шагов короля, за которое он может пройти с одного поля на другое: так, в начале игры расстояние между королями – 7 ходов). Выигрывает тот, кто поставит своего короля на противоположную кромку доски (белого короля на вертикаль h или восьмую горизонталь, чёрного – на вертикаль a или первую горизонталь). Кто выиграет при правильной игре?

а) Из 19 шаров 2 радиоактивны. Про любую кучку шаров за одну проверку можно узнать, имеется ли в ней хотя бы один радиоактивный шар (но нельзя узнать, сколько их). Доказать, что за 8 проверок всегда можно выделить оба радиоактивных шара.б) Из 11 шаров два радиоактивны. Доказать, что менее чем за 7 проверок нельзя гарантировать нахождение обоих радиоактивных шаров,

а за 7 проверок их всегда можно обнаружить.