Устная олимпиада "Открытие"
5-7 класс (май 2012 года)
Задачи
I. НАЙДИ УМНОГО
За круглым столом сидит компания из 30 человек.
Каждый из них либо дурак, либо умный.
Всех сидящих спрашивают: «Кто Ваш сосед справа — умный или дурак?»
В ответ умный говорит правду, а дурак может сказать как правду, так и ложь.
Ваша цель — указать на умного, зная лишь ответы на этот вопрос.
(а) Найдите сначала дурака, если известно, что среди сидящих он ровно один.
(б) Можно ли найти умного, если среди сидящих 15 дураков?
(в) Возможно ли такое, что дураков меньше половины, а умного всё равно не найти?
(г) Возможно ли такое, что среди сидящих 9 дураков, а умного всё равно не найти?
(д) Пусть нам сообщили, что среди сидящих ровно N дураков. Из этого гарантированно можно сделать вывод, что наибольшая группа умных, сидящих подряд, больше любой группы дураков, сидящих подряд. Докажите, что тогда N не более 8.
(е) При каком наибольшем числе дураков можно гарантировано найти умного?
II. УЗНАТЬ ВСЕ ИМЕНА
Перед Наполеоном выстроили 9 солдат-героев в виде квадратного каре 3х3, в котором три ряда по три солдата. Имена всех солдат различны.
Наполеон хочет узнать имена всех солдат. Он указывает на какое-то квадратное каре и просит назвать имена этих солдат. Это может быть один солдат, часть солдат в виде каре 2х2.... Ему дают ответ, но не указывают, у какого солдата какое имя.
(а) Наполеон, конечно, может спросить про каждого солдата отдельно, для этого потребуется 9 вопросов. А как ему узнать имена всех 9 солдат менее чем за 9 вопросов?
(б) За какое наименьшее число вопросов Наполеон может узнать все имена?
Пусть теперь перед Наполеоном построили каре 9х9.
(в) Может ли Наполеон узнать все имена, спрашивая только про каре 5х5?
(г) Может ли Наполеон узнать все имена менее чем за 25 вопросов, спрашивая только про каре 5х5?
(д) Пусть 32 солдат каре, стоящие у края, возьмутся за руки. С каждым вопросом происходит следующее: если два солдата держались за руки, но один оказался внутри указанного Наполеоном каре, а другой — вне, то они перестают держаться за руки.
Через сколько вопросов Наполеона не останется солдат, держащихся за руки?
(е) За какое наименьшее число вопросов Наполеон может узнать все имена?
III. СУММЫ И РАЗНОСТИ
Дана таблица, в которой 6 строк и 6 столбцов. Строки занумеровали шестью различными натуральными числами. Столбцы занумеровали теми же числами. Сделали два экземпляра таблицы и выдали их Саше и Руслану.
Саша в каждую ячейку своей таблицы написал сумму номера строки и столбца.
Руслан в каждую ячейку своей таблицы написал неотрицательную разность номера строки и столбца.
(а) Может ли оказаться, что в таблице Саши каждое число встречается не более двух раз?
(б) Может ли оказаться, что в таблице Руслана все ненулевые числа встречается не более двух раз?
(в) Может ли оказаться так, что в таблице Руслана каждое число встречается не более 2 раз, а в таблице Саши есть положительное число, которое встречается более 2 раз?
(г) Докажите, что если у Руслана есть четыре равных числа, то у Саши также найдется четыре равных ненулевых числа.
(д) Какое наибольшее количество равных чисел может оказаться в таблице Саши?
(е) В таблице Руслана ровно 6 различных чисел. Сколько различных чисел может оказаться в таблице Саши?
| 
