17 Количество информации и взвешивания.
11-13 января
17.1 Петя загадал натуральное число от 1 до 8. Вася хочет отгадать его, задавая Пете вопросы, на которые тот будет давать ответы «да» или «нет». Удастся ли ему узнать число за 3 вопроса? А если число от 1 до 9?
17.2 А сколько вопросов понадобится Васе, если Петя загадал число от 1 до 32? До 33?
17.3 Одна из 9 монет – фальшивая, она весит меньше настоящей. Можно ли ее найти за 2 взвешивания на чашечных весах без гирь? А если монет 10? А сколько взвешиваний нужно для 26, 27, 28 монет?
17.4 Одна из N монет фальшивая (легче настоящей). При каких N можно определить ее за 4 взвешивания?
17.5 Из 3 монет одна фальшивая, причем неизвестно, легче она или тяжелее настоящей. а)Можно ли за 2 взвешивания найти фальшивую монету и определить легче ли она настоящей или тяжелее? б)Можно ли за одно взвешивание найти фальшивую монету, если не требуется определять, легче ли она настоящей или тяжелее?
17.6 На шахматной доске 8×8 одна из клеток закрашена невидимыми чернилами. Разрешается выделить любой прямоугольник и спросить, есть ли в нем выделенная клетка. За какое минимальное число вопросов можно найти выделенную клетку?
17.7 В лавке Зловредного Торговца на полке стоит 64 одинаковых коробки. В одной из них – вкуснющий Торт, а остальные – пустые. Торговец согласен продать Вам любую из коробок за 100 рублей. Вот только покупать пустую коробку за 100 рублей совсем не хочется. Торговец согласен всего за 10 рублей честно ответить на любой вопрос о коробках и торте, лишь бы на него можно было ответить «Да» или «Нет». Во сколько Вам обойдется Торт?
17.8 Фокусник кладет перед зрителем колоду из n карт, и просит его посмотреть и запомнить одну карту. После этого фокусник раскладывает все карты в 6 стопок, и просит зрителя сказать, в какой из них лежит загаданная карта. Затем фокусник тасует карты, опять раскладывает их в 6 стопок, и просит зрителя назвать ту из стопок, в которой на этот раз лежит задуманная карта. Едва услышав ответ, фокусник сразу вытаскивает загаданную карту из стопки. Для какого наибольшего n можно с успехом показывать такой фокус?
17.9 В орфографическом словаре 120 страниц, причем на каждой из них по 60 слов. Петя открыл словарь на случайной странице и загадал случайное слово с этой страницы. Сможет ли Витя угадать его за 13 вопросов? А за меньшее число?
17.10 Пусть имеется 7 серебряных монет и 2 медных (серебряные отличаются от медных по весу и по виду). Известно, что одна из монет фальшивая (легче настоящей), а остальные настоящие. Найдите ее за два взвешивания.
17.11 Есть 5 серебряных и 4 золотые монеты. Известно, что одна из них фальшивая. Фальшивая серебряная монета весит меньше настоящей серебряной, а фальшивая золотая – больше настоящей золотой. Найдите фальшивую монету за 2 взвешивания.
17.12 а)Имеются 4 гири с маркировками 1г, 2г, 3г и 4г. Одна из них дефектная (отличается по весу). Можно ли за 2 взвешивания на двухчашечных весах найти дефектную гирю, и определить, легче она или тяжелее?
б) А можно ли за 3 взвешивания найти одну дефектную среди 13 гирь с маркировками 1г, 2г, …, 13г.
17.13 Среди 8 монет, возможно, есть одна фальшивая (легче настоящей). Как за 2 взвешивания найти фальшивую монету, или доказать, что ее нет?
17.14 В англо-русском словаре 80 страниц, на каждой из них по 50 слов. Петя открыл словарь на случайной странице и загадал случайное слово с этой страницы. Сможет ли Витя угадать его за 12 вопросов, на которые Петя будет отвечать «да» или «нет»?
17.15 Имеется 9 гирек-эталонов весом 100г,200г,…,900. К сожалению, одна из гирек побывала в руках нечестных торговцев, и теперь весит немного (но не более, чем на 10 г) легче, чем раньше. Как определить эту гирьку за 2 взвешивания на двухчашечных весах?
17.16 Прокл задумал одно из ребер полного графа на 20 вершинах (граф называют полным, если каждая вершина соединена со всеми остальными). Изначально все ребра покрашены в красный цвет. У Вакулы есть красная, синяя и зеленая краски. За один ход Вакула может перекрасить любые ребра и спросить Прокла, какого цвета задуманное ребро. За какое количество вопросов Вакула сможет наверняка узнать задуманное ребро?
17.17 Петя загадывает два натуральных числа от 1 до 10 – одно четное, и одно нечетное. Помогите Вите угадать эти числа за 5 вопросов, на которые Петя будет отвечать «да» или «нет». (Приведите вопросы, которые должен задавать Витя и объясните, почему эти вопросы наверняка позволят ему угадать Петино число)
Письменное домашнее задание (сдать в тетради 17 января)
17.18 а) Пантелеймону понравилась одна из сторон выпуклого восьмиугольника. Викентий может провести любую диагональ в этом восьмиугольнике и спросить Пантелеймона, в какой из получившихся частей лежит понравившаяся ему сторона. За какое наименьшее количество вопросов Викентий может наверняка узнать выбор Пантелеймона? б) Решите ту же задачу для пятнадцатиугольника.
17.19 Хитрец и Простак договорились сыграть в такую игру: Хитрец загадывает натуральное число от 1 до 10. Простак задает сопернику вопросы, на которые тот отвечает только «да» или «нет». Если Простак после нескольких вопросов назвал число Хитреца – он победил. Однако Хитрец решил немного слукавить и в случае необходимости поменять свое число. Конечно же, он делает это так, чтобы обман не раскрылся.
а) Докажите, что за три вопроса Простаку не выиграть.
б) Как нужно действовать Простаку, чтобы выиграть за 4 вопроса?
