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

Известно, что Шакал всегда лжёт, Лев говорит правду, Попугай просто повторяет последний услышанный ответ (а если его спросить первым, ответит как попало), а Жираф дает честный ответ, но на предыдущий заданный ему вопрос (а на первый вопрос отвечает как попало). Мудрый Ёжик в тумане наткнулся на Шакала, Льва, Попугая и Жирафа и решил выяснить, в каком порядке они стоят. Спросив всех по очереди "Ты Шакал?", он понял только лишь, где Жираф. Спросив всех в том же порядке: "Ты Жираф?", он смог ещё понять, где Шакал, но полной ясности так и не наступило. И лишь после того как на вопрос "Ты Попугай?" первый ответил "Да", Ежу, наконец, стало ясно, в каком порядке стояли животные. Так в каком же?

("Как попало" означает, что один из ответов "Д...

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

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

К натуральному числу<i> A </i>приписали справа три цифры. Получившееся число оказалось равным сумме всех натуральных чисел от 1 до<i> A </i>. Найдите<i> A </i>.

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

В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей – молчунов. Докажите, что учитель может пригласить на факультатив не менее половины класса так, чтобы все болтуны молчали.

Юра выложил в ряд 2001 монету достоинством 1, 2 и 3 копейки. Оказалось, что между любыми двумя копеечными монетами лежит хотя бы одна монета, между любыми двумя двухкопеечными монетами лежат хотя бы две монеты, а между любыми двумя трехкопеечными монетами лежат хотя бы три монеты. Сколько у Юры могло быть трехкопеечных монет?

Таня задумала натуральное число  <i>X</i> ≤ 100,  а Саша пытается его угадать. Он выбирает пару натуральных чисел <i>M</i> и <i>N</i>, меньших 100, и задаёт вопрос: "Чему равен наибольший общий делитель  <i>X + M</i>  и <i>N</i>?" Докажите, что Саша может угадать Танино число, задав семь таких вопросов.

Имеются пять внешне одинаковых гирь с попарно различными массами. Разрешается выбрать любые три из них <i>A</i>, <i>B</i> и <i>C</i> и спросить, верно ли, что

<i>m</i>(<i>A</i>) < <i>m</i>(<i>B</i>) < <i>m</i>(<i>C</i>)  (через <i>m</i>(<i>x</i>) обозначена масса гири <i>x</i>). При этом даётся ответ "Да" или "Нет". Можно ли за девять вопросов гарантированно узнать, в каком порядке идут веса гирь?

Переаттестация Совета Мудрецов происходит так: король выстраивает их в колонну по одному и надевает каждому колпак белого или чёрного цветов. Все мудрецы видят цвета всех колпаков впереди стоящих мудрецов, а цвет своего и всех стоящих сзади не видят. Раз в минуту один из мудрецов должен выкрикнуть один из двух цветов (каждый мудрец выкрикивает цвет один раз). После окончания этого процесса король казнит каждого мудреца, выкрикнувшего цвет, отличный от цвета его колпака. Накануне переаттестации все сто членов Совета Мудрецов договорились и придумали, как минимизировать число казнённых. Скольким из них гарантированно удастся избежать казни?

  Переаттестация Совета Мудрецов происходит так: король выстраивает их в колонну по одному и надевает каждому колпак белого, синего или красного цветов. Все мудрецы видят цвета всех колпаков впереди стоящих мудрецов, а цвет своего и всех стоящих сзади не видят. Раз в минуту один из мудрецов должен выкрикнуть один из трёх цветов (каждый мудрец выкрикивает цвет один раз).

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

  Накануне переаттестации все сто членов Совета Мудрецов договорились и придумали, как минимизировать число казненных. Скольким из них гарантированно удастся избежать казни?

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

Кощей Бессмертный похитил у царя трёх дочерей. Отправился Иван-царевич их выручать. Приходит он к Кощею, а тот ему и говорит: "Завтра поутру увидишь пять заколдованных девушек. Три из них – царёвы дочери, а ещё две – мои. Для тебя они будут неотличимы, а сами друг дружку различать смогут. Я подойду к одной из них и стану у неё спрашивать про каждую из пятерых: "Это царевна?". Она может отвечать и правду, и неправду, но ей дозволено назвать царевнами ровно двоих (себя тоже можно называть). Потом я так же опрошу каждую из остальных девушек, и они тоже должны будут назвать царевнами ровно двоих. Если после этого угадаешь, кто из них и вправду царевны, отпущу тебя восвояси невредимым. А если ещё и догадаешься, которая царевна старшая, которая средняя, а которая младшая, то и их...

Жестокий халиф завоевал страну Иванушки-дурацка, а его самого заключил в темницу. Оттуда ведет две двери: одна - в клетку с голодным тигром, а другая - на свободу. У каждой двери стоит по джинну, один из которых всегда говорит правду, а другой всегда лжет. Халиф разрешил Иванушке задать ровно один вопрос одному из джиннов (по внешности джинны не отличаются), на который тот ответит "да" или "нет". а) Сможет ли Иванушка выйти на свободу? б) Сможет ли он выйти на свободу, если один из джиннов уйдет курить кальян?

Вадик написал название своего родного города и все его циклические сдвиги (перестановки по кругу), получив таблицу 1. Затем, упорядочив эти ''слова'' по алфавиту, он составил таблицу 2 и выписал её последний столбец:<tt>ВКСАМО</tt>. Саша сделал то же самое с названием своего родного города и получил ''слово'' <tt>МТТЛАРАЕКИС</tt>. Что это за город, если его название начинается с буквы <tt>С</tt>?

<img src="/storage/problem-media/103897/problem_103897_img_2.gif">

Расшифровать пример на умножение, если буквой Ч зашифрованы чётные числа, а буквой Н – нечётные. <div align="center"><img src="/storage/problem-media/102865/problem_102865_img_2.gif"></div>

В компанию из <i>n</i> человек пришёл журналист. Ему известно, что в этой компании есть человек <i>Z</i>, который знает всех остальных членов компании, но его не знает никто. Журналист может к каждому члену компании обратиться с вопросом: "Знаете ли вы такого-то?"

  а) Может ли журналист установить, кто из компании есть <i>Z</i>, задав менее <i>n</i> вопросов?

  б) Найдите наименьшее количество вопросов, достаточное для того, чтобы наверняка найти <i>Z</i>, и докажите, что меньшим числом вопросов обойтись нельзя.

(Все отвечают на вопросы правдиво. Одному человеку можно задавать несколько вопросов.)

<b><em>Попугаи.</em></b>Собрались три попугая — Гоша, Кеша и Рома. Один из них всегда говорит правду, другой всегда лжет, а третий — хитрец, он иногда говорит правду, иногда лжет. На вопрос: «Кто Кеша?» — попугаи ответили так: Гоша: — Кеша лжец. Кеша: — Я хитрец! Рома: — Он абсолютно честный попугай. Кто же из попугаев честный, кто лжец, а кто хитрец?

<b> Шесть на два.</b>Восстановите числовой пример на деление <div align="center"><img src="/storage/problem-media/88333/problem_88333_img_2.gif"></div><br clear="all">

В Пустоземье живут три племени: эльфы, гоблины и хоббиты. Эльф всегда говорит только правду, гоблин всегда лжёт, а хоббит через раз говорит то правду, то ложь. Однажды за круглым столом пировало несколько пустоземцев, и один из них сказал, указав на своего левого соседа: "Он - хоббит". Сосед сказал: "Мой правый сосед солгал". В точности ту же фразу затем повторил его левый сосед, потом её же произнёс следующий по кругу, и так они говорили "Мой правый сосед солгал" много-много кругов, да и сейчас ещё, возможно, говорят. Определите, из каких племён были пирующие, если известно, что за столом сидело а) девять; б) десять жителей Пустоземья. Объясните своё решение.

На какое целое число надо умножить999 999 999, чтобы получить число, состоящее из одних единиц?

Требуется записать число вида 7...7, используя только семёрки (их можно писать и по одной, и по нескольку штук подряд), причём разрешены только сложение, вычитание, умножение, деление и возведение в степень, а также скобки. Для числа 77 самая короткая запись – это просто 77. А существует ли число вида 7...7, которое можно записать по этим правилам, используя меньшее количество семёрок, чем в его десятичной записи?

На острове живут рыцари, лжецы и подпевалы; каждый знает про всех, кто из них кто. В ряд построили всех 2018 жителей острова и попросили каждого ответить "Да" или "Нет" на вопрос: "На острове рыцарей больше, чем лжецов?". Жители отвечали по очереди и так, что их слышали остальные. Рыцари отвечали правду, лжецы лгали. Каждый подпевала отвечал так же, как большинство ответивших до него, а если ответов "Да" и "Нет" было поровну, давал любой из этих ответов. Оказалось, что ответов "Да" было ровно 1009. Какое наибольшее число подпевал могло быть среди жителей острова?

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

В зоопарке жили 200 попугаев. Однажды они по очереди сделали по одному заявлению. Начиная со второго, все заявления были "Среди сделанных ранее заявлений ложных – более 70%". Сколько всего ложных заявлений сделали попугаи?