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

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

В строку в неизвестном порядке записаны все целые числа от 1 до 100. За один вопрос про любые 50 чисел можно узнать, в каком порядке относительно друг друга записаны эти 50 чисел. За какое наименьшее число вопросов наверняка можно узнать, в каком порядке записаны все 100 чисел?

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

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

В городе Удоеве выборы мэра проходят следующим образом. Если в очередном туре голосования никто из кандидатов не набрал больше половины голосов, то проводится следующий тур с участием всех кандидатов, кроме последнего по числу голосов. (Никогда два кандидата не набирают голосов поровну; если кандидат набрал больше половины голосов, то он становится мэром и выборы заканчиваются.) Каждый избиратель в каждом туре голосует за одного из кандидатов. Если это кандидат вышел в следующий тур, то избиратель снова голосует за него. Если же кандидат выбыл, то все его избиратели голосуют за одного и того же кандидата из числа оставшихся. На очередных выборах баллотировалось 2002 кандидата. Мэром стал Остап Бендер, занявший в первом туре <i>k</i>-е место по числу голосов. Определ...

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

  а) спрятали;

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

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

На химической конференции присутствовало<i>k</i>учёных химиков и алхимиков, причём химиков было больше, чем алхимиков. Известно, что на любой вопрос химики всегда отвечают правду, а алхимики иногда говорят правду, а иногда лгут. Оказавшийся на конференции математик про каждого учёного хочет установить, химик тот или алхимик. Для этого он любому учёному может задать вопрос: "Кем является такой-то: химиком или алхимиком?" (В частности, может спросить, кем является сам этот учёный.) Доказать, что математик может установить это за 2<i>k</i>− 3 вопросов.

На химической конференции присутствовало<i>k</i>учёных химиков и алхимиков, причём химиков было больше, чем алхимиков. Известно, что на любой вопрос химики всегда отвечают правду, а алхимики иногда говорят правду, а иногда лгут. Оказавшийся на конференции математик про каждого учёного хочет установить, химик тот или алхимик. Для этого он любому учёному может задать вопрос: ``Кем является такой-то: химиком или алхимиком?'' (В частности, может спросить, кем является сам этот учёный.) Доказать, что математик может установить это за: а) 4<i>k</i>вопросов; б) 2<i>k</i>- 2 вопросов.

На<i>n</i>карточках, выложенных по окружности, записаны числа, каждое из которых<nobr>равно 1</nobr><nobr>или –1.</nobr>За какое наименьшее число вопросов можно наверняка определить произведение всех<nobr><i>n</i> чисел,</nobr>если за один вопрос разрешено узнать произведение чисел на<nobr>а) любых</nobr>трёх карточках;<nobr>б) любых</nobr>трёх карточках, лежащих подряд? (Здесь<nobr><i>n</i> —</nobr>натуральное число,<nobr>большее 3).</nobr>

Двое играют в следующую игру. Один называет цифру, а другой вставляет её по своему усмотрению вместо одной из звёздочек в следующей разности:<font face="Symbol"></font> – <font face="Symbol"></font>.Затем первый называет ещё одну цифру, второй ставит её, первый опять называет цифру, и так играют до тех пор, когда все звёздочки будут заменены цифрами. Первый стремится к тому, чтобы разность получилась как можно больше, а <nobr>второй —</nobr> чтобы она стала как можно меньше. Докажите, что а) второй может расставлять цифры так, чтобы полученная разность стала не больше 4000, независимо от того, какие цифры называл первый; б) первый может называть цифры так, чтобы разность стала не меньше 4000, независимо от того, куда расставля...

Король решил поощрить группу из $n$ мудрецов. Их поставят в ряд друг за другом (чтобы все смотрели в одном направлении), на каждого наденут чёрную или белую шляпу. Каждый будет видеть шляпы всех впереди стоящих. Мудрецы по очереди (от последнего к первому) назовут цвет (белый или чёрный) и натуральное число по своему выбору. В конце подсчитывается число мудрецов, которые назвали цвет, совпадающий с цветом своей шляпы: ровно столько дней всей группе будут платить надбавку к жалованью. Мудрецам разрешили договориться заранее, как отвечать. При этом мудрецы знают, что ровно $k$ из них безумны (кто именно – им неизвестно). Безумный мудрец называет белый или чёрный цвет и число вне зависимости от договорённостей. Какое максимальное число дней с надбавкой к жалованью могут гарантировать группе м...