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

Рассмотрим граф, у которого вершины соответствуют всевозможным трёхэлементным подмножествам множества  {1, 2, 3, ..., 2<i>^k</i>},  а рёбра проводятся между вершинами, которые соответствуют подмножествам, пересекающимся ровно по одному элементу. Найдите минимальное количество цветов, в которые можно раскрасить вершины графа так, чтобы любые две вершины, соединённые ребром, были разного цвета.

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

  а) при  <i>n = k = </i>2;

  б) при произвольных фиксированных <i>n</i> и <i>k</i>?

Дима посчитал факториалы всех натуральных чисел от80 до 99, нашел числа, обратные к ним, и напечатал получившиеся десятичные дроби на 20 бесконечных ленточках (например, на последней ленточке было напечатано число<i> <img align="abscenter" src="/storage/problem-media/111849/2.gif">=</i>0<i>, <img align="absmiddle" src="/storage/problem-media/111849/3.gif"></i>10715<i>.. </i>). Саша хочет вырезать из одной ленточки кусок, на котором записано<i> N </i>цифр подряд и нет запятой. При каком наибольшем<i> N </i>он сможет это сделать так, чтобы Дима не смог определить по этому куску, какую ленточку испортил Саша?

Фокусник с помощником собираются показать такой фокус. Зритель пишет на доске последовательность из <i>N</i> цифр. Помощник фокусника закрывает две соседних цифры чёрным кружком. Затем входит фокусник. Его задача – отгадать обе закрытые цифры (и порядок, в котором они расположены). При каком наименьшем <i>N</i> фокусник может договориться с помощником так, чтобы фокус гарантированно удался?

Мишень "бегущий кабан" находится в одном из<i> n </i>окошек, расположенных в ряд. Окошки закрыты занавесками так, что для стрелка мишень все время остается невидимой. Чтобы поразить мишень, достаточно выстрелить в окошко, в котором она в момент выстрела находится. Если мишень находится не в самом правом окошке, то сразу после выстрела она перемещается на одно окошко вправо; из самого правого окошка мишень никуда не перемещается. Какое наименьшее число выстрелов нужно сделать, чтобы наверняка поразить мишень?

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

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

В классе 30 учеников, и у каждого из них одинаковое число друзей среди одноклассников. Каково наибольшее возможное число учеников, которые учатся лучше большинства своих друзей? (Про любых двух учеников в классе можно сказать, кто из них учится лучше; если <i>A</i> учится лучше <i>B</i>, а тот – лучше <i>C</i>, то <i>A</i> учится лучше <i>C</i>.)

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

У ведущего есть колода из 52 карт. Зрители хотят узнать, в каком порядке лежат карты (при этом не уточняя   сверху вниз или снизу вверх). Разрешается задавать ведущему вопросы вида "Сколько карт лежит между такой-то и такой-то картами?". Один из зрителей подсмотрел, в каком порядке лежат карты. Какое наименьшее число вопросов он должен задать, чтобы остальные зрители по ответам на эти вопросы могли узнать порядок карт в колоде?

Банкир узнал, что среди одинаковых на вид монет одна — фальшивая (более легкая). Он попросил эксперта определить эту монету с помощью чашечных весов без гирь, причем потребовал, чтобы каждая монета участвовала во взвешиваниях не более двух раз. Какое наибольшее число монет может быть у банкира, чтобы эксперт заведомо смог выделить фальшивую за<i>n</i>взвешиваний?

Имеется 100-значное число, состоящее из единиц и двоек. Разрешается в любых десяти последовательных цифрах поменять местами первые пять с пятью следующими. Два таких числа называются<i>похожими</i>, если одно из них получается из другого несколькими такими операциями. Какое наибольшее количество попарно непохожих чисел можно выбрать?

Петя красит каждую клетку доски $2m\times 2n$ в чёрный или белый цвет так, чтобы клетки каждого цвета образовывали многоугольник. Затем Вася разрезает доску на доминошки (прямоугольники из двух клеток). Петя стремится к тому, чтобы в итоге получилось как можно больше двухцветных доминошек, а Вася — к тому, чтобы их получилось как можно меньше. Наличие какого наибольшего числа двухцветных доминошек может гарантировать Петя, как бы ни действовал Вася? (Напомним, что граница многоугольника — замкнутая ломаная без самопересечений.)

Петя красит каждую клетку доски $22 \times 22$ в чёрный или белый цвет так, чтобы клетки каждого цвета образовывали многоугольник. Затем Вася разрезает доску на двухклеточные доминошки. Петя стремится к тому, чтобы в итоге получилось как можно больше разноцветных доминошек, а Вася – к тому, чтобы их получилось как можно меньше. Наличие какого наибольшего числа разноцветных доминошек может гарантировать Петя, как бы ни действовал Вася? (Напомним, что граница многоугольника – замкнутая ломаная без самопересечений.)

У Вани есть клетчатая бумага двух видов: белая и чёрная. Он вырезает кусок из любой бумаги и наклеивает на серую клетчатую доску $45\times 45$, делая так много раз. Какое минимальное число кусков нужно наклеить, чтобы «раскрасить» клетки доски в шахматном порядке? (Каждый кусок – набор клеток, в котором от любой клетки до любой другой можно пройти, переходя из клетки в соседнюю через их общую сторону. Можно наклеивать куски один поверх другого. Все клетки имеют размер $1\times 1$.)

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

Пекарь испёк прямоугольный лаваш и разрезал его на $n^2$ прямоугольников, сделав $n–1$ горизонтальных разрезов и $n–1$ вертикальных. Оказалось, что округлённые до целого числа площади получившихся прямоугольников равны всем натуральным числам от $1$ до $n^2$ в некотором порядке. Для какого наибольшего $n$ это могло произойти? (Полуцелые числа округляются вверх.)

У Карабаса-Барабаса есть большой участок земли в форме выпуклого $12$-угольника, в вершинах которого стоят фонари. Карабасу-Барабасу нужно поставить внутри участка некоторое конечное число фонарей, разделить его на треугольные участки с вершинами в фонарях и раздать эти участки актёрам театра. При этом каждый внутренний фонарь должен освещать не менее шести треугольных участков (фонарь светит недалеко, только на те участки, в вершине которых стоит). Какое максимальное количество треугольных участков может раздать Карабас-Барабас актёрам?

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

У фокусника и помощника есть колода с картами; одна сторона ("рубашка") у всех карт одинакова, а другая окрашена в один из 2017 цветов (в колоде по 1000000 карт каждого цвета). Фокусник и помощник собираются показать следующий фокус. Фокусник выходит из зала, а зрители выкладывают на стол в ряд  <i>n</i> > 1  карт рубашками вниз. Помощник смотрит на эти карты, а затем все, кроме одной, переворачивает рубашкой вверх, не меняя их порядка. Затем входит фокусник, смотрит на стол, указывает на одну из закрытых карт и называет её цвет. При каком наименьшем <i>k</i> фокусник может заранее договориться с помощником так, чтобы фокус гарантированно удался?

У нумизмата есть 100 одинаковых по внешнему виду монет. Он знает, что среди них 30 настоящих и 70 фальшивых монет. Кроме того, он знает, что массы всех настоящих монет одинаковы, а массы всех фальшивых – разные, причём каждая фальшивая монета тяжелее настоящей; однако точные массы монет неизвестны. Имеются двухчашечные весы без гирь, на которых можно за одно взвешивание сравнить массы двух групп, состоящих из одинакового числа монет. За какое наименьшее количество взвешиваний на этих весах нумизмат сможет гарантированно найти хотя бы одну настоящую монету?

На каждой из 2013 карточек написано по числу, все эти 2013 чисел различны. Карточки перевёрнуты числами вниз. За один ход разрешается указать на десять карточек, и в ответ сообщат одно из чисел, написанных на них (неизвестно, какое).

Для какого наибольшего <i>t</i> гарантированно удастся найти <i>t</i> карточек, про которые известно, какое число написано на каждой из них?

Какое наименьшее число гирь необходимо для того, чтобы иметь возможность взвесить любое число граммов от 1 до 100 на чашечных весах, если гири можно класть на обе чашки весов?