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

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

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

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

  а) спрятали;

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

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

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