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

30 девочек – 13 в красных платьях и 17 в синих платьях – водили хоровод вокруг новогодней ёлки. Впоследствии каждую из них спросили, была ли её соседка справа в синем платье. Оказалось, что правильно ответили те и только те девочки, которые стояли между девочками в платьях одного цвета. Сколько девочек могли ответить утвердительно?

За круглым столом сидят 30 человек – рыцари и лжецы (рыцари всегда говорят правду, а лжецы всегда лгут). Известно, что у каждого из них за этим же столом есть ровно один друг, причём у рыцаря этот друг – лжец, а у лжеца этот друг – рыцарь (дружба всегда взаимна). На вопрос "Сидит ли рядом с вами ваш друг?" сидевшие через одного ответили "Да". Сколько из остальных могли также ответить "Да"?

В турнире каждый участник встретился с каждым из остальных один раз. Каждую встречу судил один арбитр, и все арбитры судили разное количество встреч. Игрок Иванов утверждает, что все его встречи судили разные арбитры. То же самое утверждают о себе игроки Петров и Сидоров. Может ли быть, что никто из них не ошибается?

Члены Государственной Думы образовали фракции так, что для любых двух фракций<i> A </i>и<i> B </i>(не обязательно различных)<i> <img src="/storage/problem-media/109909/problem_109909_img_2.gif"> </i>– тоже фракция (через<i> <img src="/storage/problem-media/109909/problem_109909_img_3.gif"> </i>обозначается множество всех членов Думы, не входящих в<i> C </i>). Докажите, что для любых двух фракций<i> A </i>и<i> B </i><i> A<img src="/storage/problem-media/109909/problem_109909_img_4.gif"> B </i>– также фракция.

Саша и Маша загадали по натуральному числу и сообщили их Васе. Вася написал на одном листе бумаги сумму загаданных чисел, а на другом – их произведение, после чего один из листов спрятал, а другой (на нём оказалось написано число 2002) показал Саше и Маше. Увидев это число, Саша сказал, что не знает, какое число загадала Маша. Услышав это, Маша сказала, что не знает, какое число загадал Саша. Какое число загадала Маша?

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

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

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

Известно, что вруны всегда врут, правдивые всегда говорят правду, а хитрецы могут и врать, и говорить правду. Вы можете задавать вопросы, на которые есть ответ "да" или "нет" (например: "верно ли, что этот человек – хитрец?").

  a) Перед вами трое – врун, правдивый и хитрец, которые знают, кто из них кто. Как и вам это узнать?

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

  В школьном совете выбирают председателя. Кандидатов четверо: А, Б, В и Г. Предложена специальная процедура – каждый член совета должен записать на специальном листке кандидатов в порядке своих предпочтений. Например, АВГБ значит, что член совета на первое место ставит А, не очень возражает против В и считает, что он лучше, чем Г, зато меньше всего хотел бы видеть председателем Б. Первое место даёт кандидату 3 очка, второе – 2 очка, третье – 1 очко, а четвёртое – 0 очков. После сбора всех листков избирательная комиссия суммирует очки у каждого кандидата. Победит тот, у кого наибольшая сумма очков.

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

За круглым столом сидят 2015 человек, каждый из них – либо рыцарь, либо лжец. Рыцари всегда говорят правду, лжецы всегда лгут. Им раздали по одной карточке, на каждой карточке написано по числу; при этом все числа на карточках различны. Посмотрев на карточки соседей, каждый из сидящих за столом сказал: "Мое число больше, чем у каждого из двух моих соседей". После этого <i>k</i> из сидящих сказали: "Мое число меньше, чем у каждого из двух моих соседей". При каком наибольшем <i>k</i> это могло случиться?

На дереве сидело 100 попугайчиков трёх видов: зелёные, жёлтые, пёстрые. Пролетая мимо, Ворона каркнула: "Среди вас зелёных больше чем пёстрых!" – "Да!" – согласилось 50 попугайчиков, а остальные прокричали "Нет!". Обрадовавшись завязавшемуся диалогу, Ворона снова каркнула: "Среди вас пёстрых больше чем жёлтых!" Опять половина попугайчиков закричали "Да!", а остальные – "Нет!". Зелёные попугайчики оба раза сказали правду, жёлтые – оба раза солгали, а каждый из пёстрых один раз солгал, а один раз сказал правду. Могло ли жёлтых попугайчиков быть больше чем зелёных?

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

Ученик Коля Васин при помощи метода математической индукции смог доказать, что в любом табуне все лошади одной масти. Если есть только одна лошадь, то она своей масти, так что база индукции верна. Для индуктивного перехода предположим, что есть<i>n</i>лошадей (с номерами от 1 до<i>n</i>). По индуктивному предположению лошади с номерами от 1 до<i>n</i>- 1 одинаковой масти. Аналогично лошади с номерами от 2 до<i>n</i>также имеют одинаковую масть. Но лошади с номерами от 2 до<i>n</i>- 1 не могут менять свою масть в зависимости от того как они сгруппированы — это лошади, а не хамелеоны. Поэтому все<i>n</i>лошадей должны быть одинаковой масти. Есть ли ошибка в этом рассуждении, и если есть, то какая?

<b>Гениальные математики.</b>а) Каждому из двух гениальных математиков сообщили по натуральному числу, причем им известно, что эти числа отличаются на единицу. Они поочередно спрашивают друг друга: "Известно ли тебе мое число?" Докажите, что рано или поздно кто-то из них ответит "да". Сколько вопросов они зададут друг другу? (Математики предполагаются правдивыми и бессмертными.) б) Как изменится число заданных вопросов, если с самого начала известно, что данные числа не превосходят 1000?

Цифры 0, 1, ..., 9 разбиты на несколько непересекающихся групп. Из цифр каждой группы составляются всевозможные числа, для записи каждого из которых все цифры группы используются ровно один раз (учитываются и записи, начинающиеся с нуля). Все полученные числа расположили в порядке возрастания и <i>k</i>-му числу поставили в соответствие <i>k</i>-ю букву алфавита АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ. Оказалось, что каждой букве соответствует число и каждому числу соответствует некоторая буква. Шифрование сообщения осуществляется заменой каждой буквы соответствующим ей числом. Если ненулевое число начинается с нуля, то при шифровании этот нуль не выписывается. Восстановите сообщение 873146507381 и укажите таблицу замены букв числами.

Каждую букву исходного сообщения заменили её двузначным порядковым номером в русском алфавите согласно таблице:<div align="center"><img src="/storage/problem-media/35741/problem_35741_img_2.gif"><img src="/storage/problem-media/35741/problem_35741_img_3.gif"></div>Полученную цифровую последовательность разбили (справа налево) на трёхзначные цифровые группы без пересечений и пропусков. Затем каждое из полученных трёхзначных чисел умножили на 77 и оставили только три последние цифры произведения. В результате получилась следующая последовательность цифр:  317564404970017677550547850355.  Восстановите исходное сообщение.

Для проверки телетайпа, печатающего буквами русского алфавита АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ передан набор из 9 слов, содержащий все 33 буквы алфавита. В результате неисправности телетайпа на приемном конце получены слова ГЪЙ АЭЁ БПРК ЕЖЩЮ НМЬЧ СЫЛЗ ШДУ ЦХОТ ЯФВИ Восстановите исходный текст, если известно, что характер неисправности таков, что каждая буква заменяется буквой, отстоящей от нее в указанном алфавите не дальше, чем на две буквы. Например, буква Б может перейти в одну из букв А, Б, В, Г.

(Задача с сайта<a href="http://www.cryptography.ru">www.cryptography.ru</a>.)

Выписаны в ряд числа от 1 до 2002. Играют двое, делая ходы поочередно. За один ход разрешается вычеркнуть любое из записанных чисел вместе со всеми его делителями. Выигрывает тот, кто зачеркнёт последнее число. Докажите, что у первого игрока есть способ играть так, чтобы всегда выигрывать.

Криптограмма 12 2 24 5 3 21 6 29 28 2 20 18 20 21 5 10 27 17 2 11 2 16 - 19 2 27 5 8 29 12 31 22 2 16, 19 2 19 5 17 29 8 29 6 29 16: 8 2 19 19 29 10 19 29 14 19 29 29 19 10 2 24 2 11 2 16 10 14 18 21 17 2 20 2 28 29 16 21 29 28 6 29 16. </pre>получена заменой букв на числа (от 1 до 32) так, что разным буквам соответствуют разные числа. Отдельные слова разделены несколькими пробелами, буквы - одним пробелом, знаки препинания сохранены. Буквы е'' и ё'' не различаются. Прочтите четверостишие В. Высоцкого.

При построении восемь мальчиков разместились так, что

1. А был впереди Б и В; 2) Б - впереди К через одного;
2. Л впереди А, но после Д; 4)В - после Е через одного;
3. Д - между Б и Г; 6) Е - рядом с К, но впереди В. В каком порядке выстроились мальчики?

Два стрелка произвели по 5 выстрелов, причём попадания были следующие: 10, 9, 9, 8, 8, 5, 4, 4, 3, 2. Первыми тремя выстрелами они выбили одинаковое количество очков, но тремя последними выстрелами первый стрелок выбил втрое больше очков, чем второй.

Сколько очков набрал каждый из них третьим выстрелом?

Был очень жаркий день, и четыре пары выпили вместе 44 бутылки кока-колы. Aнна выпила 2, Бетти 3, Кэрол 4 и Дороти 5 бутылок. М-р Браун выпил столько же бутылок, сколько и его жена, но каждый из других мужчин выпил больше, чем его жена: м-р Грин вдвое, м-р Вайт в три раза и м-р Смит в четыре раза. Назовите жён этих мужчин.

Каждый вечер Иван Таранов приходит в случайное время на автобусную остановку. На этой остановке останавливаются два маршрута - на одном из них Иван может ехать к себе домой, а на другом - в гости к другу Козявкину. Иван ждет первого автобуса и в зависимости от того, какой автобус подошел, он едет либо домой, либо к другу. Через некоторое время Иван заметил, что в гостях у Козявкина он оказывается при этом примерно в два раза чаще, чем дома. На основе этого Иван делает вывод, что один из автобусов ходит в два раза чаще другого. Прав ли он? Могут ли при выполнении условия задачи автобусы ходить с одинаковой частотой? (Предполагается, что автобусы ходят не случайным образом, а по некоторому расписанию.)

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