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

Чичиков играет с Ноздрёвым. Сначала Ноздрёв раскладывает 1001 орех по трём коробочкам. Посмотрев на раскладку, Чичиков называет любое целое число <i>N</i> от 1 до 1001. Далее Ноздрёв должен переложить, если надо, один или несколько орехов в пустую четвёртую коробочку и предъявить Чичикову одну или несколько коробочек, где в сумме ровно <i>N</i> орехов. В результате Чичиков получит столько мертвых душ, сколько орехов переложил Ноздрёв. Какое наибольшее число душ может гарантировать себе Чичиков, как бы ни играл Ноздрёв?

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

В некоторых клетках доски 10<i>× </i>10поставили<i> k </i> ладей, и затем отметили все клетки, которые бьет хотя бы одна ладья (считается, что ладья бьет клетку, на которой стоит). При каком наибольшем <i> k </i>может оказаться, что после удаления с доски любой ладьи хотя бы одна отмеченная клетка окажется не под боем?

По кругу стоят 100 напёрстков. Под одним из них спрятана монетка. За один ход разрешается перевернуть четыре напёрстка и проверить, лежит ли под одним из них монетка. После этого их возвращают в исходное положение, а монетка перемещается под один из соседних с ней напёрстков. За какое наименьшее число ходов наверняка удастся обнаружить монетку?

Пете и Васе подарили одинаковые наборы из <i>N</i> гирь, в которых массы любых двух гирь различаются не более, чем в 1,25 раз. Пете удалось разделить все гири своего набора на 10 равных по массе групп, а Васе удалось разделить все гири своего набора на 11 равных по массе групп. Найдите наименьшее возможное значение <i>N</i>.

На острове живут100рыцарей и100лжецов, у каждого из них есть хотя бы один друг. Рыцари всегда говорят правду, а лжецы всегда лгут. Однажды утром каждый житель произнес либо фразу "Все мои друзья – рыцари", либо фразу "Все мои друзья – лжецы", причем каждую из фраз произнесло ровно100человек. Найдите наименьшее возможное число пар друзей, один из которых рыцарь, а другой – лжец.

При каком наименьшем $n$ для любого набора $A$ из $2007$ множеств найдется такой набор $B$ из $n$ множеств, что каждое множество набора $A$ является пересечением двух различных множеств набора $B$?

а) В городе Мехико для ограничения транспортного потока для каждой частной автомашины устанавливаются два дня недели, в которые она не может выезжать на улицы города. Семье требуется каждый день иметь в распоряжении не менее десяти машин. Каким наименьшим количеством машин может обойтись семья, если её члены могут сами выбирать запрещенные дни для своих автомобилей? б) В Мехико для каждой частной автомашины устанавливается один день в неделю, в который она не может выезжать на улицы города. Состоятельная семья из десяти человек подкупила полицию, и для каждой машины они называют два дня, один из которых полиция выбирает в качестве невыездного дня. Какое наименьшее количество машин нужно купить семье, чтобы каждый день каждый член семьи мог самостоятельно ездить, если утверждение невыездных...

На столе стоят 2004 коробочки, в каждой из которых лежит по одному шарику. Известно, что некоторые из шариков– белые, и их количество четно. Разрешается указать на любые две коробочки и спросить, есть ли в них хотя бы один белый шарик. За какое наименьшее количество вопросов можно гарантированно определить какие-нибудь две коробочки, в которых лежат белые шарики?

На столе стоят 2004 коробочки, в каждой из которых лежит по одному шарику. Известно, что некоторые из шариков – белые, и их количество четно. Разрешается указать на любые две коробочки и спросить, есть ли в них хотя бы один белый шарик. За какое наименьшее количество вопросов можно гарантированно определить какую-нибудь коробочку, в которой лежит белый шарик?

В классе 16 учеников. Каждый месяц учитель делит класс на две группы.

Какое наименьшее количество месяцев должно пройти, чтобы каждые два ученика в какой-то из месяцев оказались в разных группах?

На берегу круглого острова Гдетотам расположено 20 деревень, в каждой живёт по 20 борцов. Был проведён турнир, в котором каждый борец встретился со всеми борцами из всех других деревень. Деревня <i>А</i> считается сильнее деревни <i>Б</i>, если хотя бы <i>k</i> поединков между борцами из этих деревень заканчивается победой борца из деревни <i>А</i>. Выяснилось, что каждая деревня сильнее следующей за ней по часовой стрелке. Какое наибольшее значение может иметь <i>k</i>? (У всех борцов разная сила, и в поединке всегда побеждает сильнейший.)

а) Электрическая схема имеет вид решётки 3×3: всего в схеме 16 узлов (вершины квадратиков решётки), которые соединены проводами (стороны квадратиков решётки). Возможно, часть проводов перегорела. За одно измерение можно выбрать любую пару узлов схемы и проверить, проходит ли между ними ток (то есть, проверить, существует ли цепочка неперегоревших проводов, соединяющая эти узлы). В действительности схема такова, что ток проходит от любого узла к любому. За какое наименьшее число измерений всегда можно в этом удостовериться? б) Тот же вопрос для решётки 7×7 (всего 64 узла).

а) Электрическая схема имеет вид решетки 3×3: всего в схеме 16 узлов (вершины квадратиков решётки), которые соединены проводами (стороны квадратиков решётки). Возможно, часть проводов перегорела. За одно измерение можно выбрать любую пару узлов схемы и проверить, проходит ли между ними ток (то есть, проверить, существует ли цепочка неперегоревших проводов, соединяющая эти узлы). В действительности схема такова, что ток проходит от каждого узла к любому другому. За какое наименьшее число измерений всегда можно в этом удостовериться? б) Тот же вопрос для решётки 5×5 (всего 36 узлов).

Имеется набор из 20 гирь, с помощью которых можно взвесить любой целый вес от 1 до 1997 г (гири кладутся на одну чашку весов, измеряемый вес – на другую). Каков минимально возможный вес самой тяжелой гири такого набора, если:

  а) веса гирь набора все целые,

  б) веса не обязательно целые?

Есть доска 1×1000, вначале пустая, и куча из <i>n</i> фишек. Двое ходят по очереди. Первый своим ходом "выставляет" на доску не более 17 фишек по одной на любое свободное поле (он может взять все 17 из кучи, а может часть – из кучи, а часть – переставить на доске). Второй снимает с доски любую <i>серию</i> фишек (серия – это несколько фишек, стоящих подряд, то есть без свободных полей между ними) и кладёт их обратно в кучу. Первый выигрывает, если ему удастся выставить все фишки в ряд без пробелов.

  а) Докажите, что при  <i>n</i> = 98  первый всегда может выиграть.

  б) При каком наибольшем <i>n</i> первый всегда может выиграть?

Фигура Ф представляет собой пересечение <i>n</i> кругов  (<i>n</i> ≥ 2,  радиусы не обязательно одинаковы). Какое максимальное число криволинейных "сторон" может иметь фигура Ф?  (Криволинейная сторона – это участок границы Ф, принадлежащий одной из окружностей и ограниченный точками пересечения с другими окружностями.)

64 друга одновременно узнали 64 новости, причём каждый узнал одну новость. Они стали звонить друг другу и обмениваться новостями. Каждый разговор длится 1 час. Какое минимальное количество часов необходимо, чтобы все узнали все новости? (Во время одного разговора можно передать сколько угодно новостей.)

Каково наименьшее число гирь в наборе, который можно разложить и на 4, и на 5, и на 6 кучек равной массы?

На листе бумаги отмечены точки<i>A</i>,<i>B</i>,<i>C</i>,<i>D</i>. Распознающее устройство может абсолютно точно выполнять два типа операций: а) измерять в сантиметрах расстояние между двумя заданными точками; б) сравнивать два заданных числа. Какое наименьшее число операций нужно выполнить этому устройству, чтобы наверняка определить, является ли четырёхугольник<i>ABCD</i>прямоугольником?

Найти наименьшее<i>n</i>такое, что любой выпуклый 100-угольник можно получить в виде пересечения<i>n</i>треугольников. Докажите, что для меньших<i>n</i>это можно сделать не с любым выпуклым 100-угольником.

Два маляра красят забор, огораживающий дачные участки. Они приходят через день и красят по одному участку (участков 100 штук) в красный или зелёный цвет. Первый маляр дальтоник и путает цвета, он помнит, что и в какой цвет он сам покрасил, и видит, что покрасил второй маляр, но не знает, в какой цвет. Первый маляр добивается того, чтобы в наибольшем числе мест зелёный участок граничил с красным. Какого наибольшего числа переходов он может добиться (как бы ни действовал второй маляр)? <b>Замечание.</b> Считается, что дачные участки расположены в одну линию.

Имеется 11 мешков с монетами и весы с двумя чашками и стрелкой, которые показывают, на какой чашке груз тяжелее и на сколько именно. Известно, что в одном мешке все монеты фальшивые, а в остальных – все монеты настоящие. Все настоящие монеты имеют одинаковый вес, а все фальшивые – также одинаковый, но другой вес. За какое наименьшее число взвешиваний можно определить, в каком мешке лежат фальшивые монеты?

Имеется кусок цепи из 60 звеньев, каждое из которых весит 1 г. Какое наименьшее число звеньев надо расковать, чтобы из образовавшихся частей можно было составить все веса в 1 г, 2 г, 3 г, ..., 60 г (раскованное звено весит тоже 1 г)?

По кругу стоит 99 тарелок, на них лежат булочки (на тарелке может быть любое число булочек или вовсе их не быть). Известно, что на любых 20 подряд идущих тарелках лежит суммарно хотя бы $k$ булочек. При этом ни одну булочку ни с одной тарелки нельзя убрать так, чтобы это условие не нарушилось. Какое наибольшее суммарное число булочек может лежать на тарелках?