Олимпиадные задачи по теме «Теория алгоритмов» для 7 класса - сложность 2 с решениями

Два фокусника показывают зрителю такой фокус. У зрителя есть 24 карточки, пронумерованные числами от 1 до 24. Он выбирает из них 13 карточек и передаёт первому фокуснику. Тот возвращает зрителю две из них. Зритель добавляет к этим двум одну из оставшихся у него 11 карточек и, перемешав, передаёт эти три карточки второму фокуснику. Каким образом фокусники могут договориться так, чтобы второй всегда с гарантией мог определить, какую из трёх карточек добавил зритель?

Известно, что среди 63 монет есть 7 фальшивых. Все фальшивые монеты весят одинаково, все настоящие монеты также весят одинаково, и фальшивая монета легче настоящей. Как за три взвешивания на чашечных весах без гирь определить 7 настоящих монет?

Говорящие весы произносят вес, округлив его до целого числа килограммов (по правилам округления: если дробная часть меньше 0,5, то число округляется вниз, а иначе – вверх; например, 3,5 округляется до 4). Вася утверждает, что, взвешиваясь на этих весах с одинаковыми бутылками, он получил такие ответы весов:<div align="center"><img src="/storage/problem-media/116812/problem_116812_img_2.gif"></div> Могло ли такое быть?

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

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

От Майкопа до Белореченска 24 км. Три друга должны добраться: двое из Майкопа в Белореченск, а третий – из Белореченска в Майкоп. У них есть один велосипед, первоначально находящийся в Майкопе. Каждый из друзей может идти (со скоростью не более 6 км/ч) и ехать на велосипеде (со скоростью не более 18 км/ч). Оставлять велосипед без присмотра нельзя. Докажите, что через 2 часа 40 минут все трое друзей могут оказаться в пунктах назначения. Ехать на велосипеде вдвоём нельзя.

Есть длинный ряд луночек. В трёх из них лежит по шарику. Игроки по очереди делают ход: берут один из крайних шариков и перекладывают в свободную луночку между двумя другими. Тот, кто не может сделать ход, считается проигравшим. Кто – начинающий игру или ходящий вторым – победит при правильной игре при показанных на рисунках первоначальных расположениях шариков?

  а)   <img align="absmiddle" src="/storage/problem-media/110925/problem_110925_img_2.gif">

  б)   <img align="absmiddle" src="/storage/problem-media/110925/problem_110925_img_3.gif">

  в)   <img align="absmiddle" src="/storage/problem-media/110925/problem_110925_img_4.gif">

  г) Разберите общий случай: между крайними шариками и средним имее...

При изготовлении партии из  <i>N</i> ≥ 5  монет работник по ошибке изготовил две монеты из другого материала (все монеты выглядят одинаково). Начальник знает, что таких монет ровно две, что они весят одинаково, но отличаются по весу от остальных. Работник знает, какие это монеты и что они легче остальных. Ему нужно, проведя два взвешивания на чашечных весах без гирь, убедить начальника в том, что фальшивые монеты легче настоящих, и в том, какие именно монеты фальшивые. Может ли он это сделать?

Двое играют в такую игру. В начале по кругу стоят числа 1, 2, 3, 4. Каждым своим ходом первый прибавляет к двум соседним числам по 1, а второй меняет любые два соседних числа местами. Первый выигрывает, если все числа станут равными. Может ли второй ему помешать?

В средней клетке полоски 1×2005 стоит фишка. Два игрока по очереди сдвигают ее: сначала первый игрок передвигает фишку на одну клетку в любую сторону, затем второй передвигает ее на 2 клетки, 1-й – на 4 клетки, 2-й – на 8 и т.д. (<i>k</i>-й сдвиг происходит на2<i>^k-</i>1 клеток). Тот, кто не может сделать очередной ход, проигрывает. Кто может выиграть независимо от игры соперника?

Двое по очереди выписывают на доску натуральные числа от 1 до 1000. Первым ходом первый игрок выписывает на доску число 1. Затем очередным ходом на доску можно выписать либо число2<i>a </i>, либо число<i> a+</i>1, если на доске уже написано число<i> a </i>. При этом запрещается выписывать числа, которые уже написаны на доске. Выигрывает тот, кто выпишет на доску число 1000. Кто выигрывает при правильной игре?

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

На доске записаны числа 1, 2, 3, ..., 1000. Двое по очереди стирают по одному числу. Игра заканчивается, когда на доске остаются два числа. Если их сумма делится на 3, то побеждает тот, кто делал первый ход, если нет – то его партнер. Кто из них выиграет при правильной игре?

На столе в ряд лежат четыре монеты. Среди них обязательно есть как настоящие, так и фальшивые (которые легче настоящих). Известно, что любая настоящая монета лежит левее любой фальшивой. Как за одно взвешивание на чашечных весах без гирь определить тип каждой монеты, лежащей на столе?

У Коли есть отрезок длины<i>k</i>, а у Лёвы — отрезок длины <i>l</i>. Сначала Коля делит свой отрезок на три части, а потом Лёва делит на три части свой отрезок. Если из получившихся шести отрезков можно сложить два треугольника, то выигрывает Лёва, а если нет — Коля. Кто из играющих, в зависимости от отношения<i>k</i>/<i>l</i>, может обеспечить себе победу, и как ему следует играть?

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

Камни лежат в трёх кучках: в одной – 51 камень, в другой – 49, а в третьей – 5. Разрешается объединять любые кучки в одну, а также разделять кучку из чётного количества камней на две равные. Можно ли получить 105 кучек по одному камню в каждой?

Петин счет в банке содержит 500 долларов. Банк разрешает совершать операции только двух видов: снимать 300 долларов или добавлять 198 долларов.

Какую максимальную сумму Петя может снять со счета, если других денег у него нет?

На клетчатой бумаге нарисован прямоугольник 5x9. В левом нижнем углу стоит фишка. Коля и Серёжа по очереди передвигают ее на любое количество клеток либо вправо, либо вверх. Первым ходит Коля. Выигрывает тот, кто поставит фишку в правый верхний. Кто выигрывает при правильной игре?

а) На столе лежат 111 спичек. Маша и Даша по очереди берут со стола по несколько спичек, но не больше десяти за один раз. Выигрывает тот, кто возьмет последнюю спичку. Кто победит при правильной игре? б) На полу лежат три кучки - из 3, 4 и 5 спичек. Теперь Маша и Даша за один раз могут взять любое количество спичек, но только из одной кучки. Кто выиграет на этот раз?

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

а) Двое играют в такую игру: на столе лежат 7 монет по два фунта и 7 монет по одному фунту. За ход разрешается взять монет на сумму не более трех фунтов. Забравший последнюю монету выигрывает. Кто победит при правильной игре? б) Тот же вопрос, если и тех, и других монет - по 12.

Есть прямоугольный стол. Два игрока начинают по очереди класть на него по одному евро так, чтобы эти монеты не перекрывали друг друга. Кто не может сделать ход - проигрывает. Кто выиграет при правильной игре?

В Монголии имеются в обращении монеты в 3 и 5 тугриков. Входной билет в центральный парк стоит 4 тугрика. Как-то раз перед открытием в кассу парка выстроилась очередь из 200 посетителей. У каждого из них, а также у кассира есть ровно 22 тугрика. Докажите, что все посетители смогут купить билет в порядке очереди.

В Мексике экологи добились принятия закона, по которому каждый автомобиль хотя бы один день в неделю не должен ездить (владелец сообщает полиции номер автомобиля и "выходной" день недели этого автомобиля). В некоторой семье все взрослые желают ездить ежедневно (каждый – по своим делам!). Сколько автомобилей (как минимум) должно быть в семье, если взрослых в ней

  а) 5 человек?  б) 8 человек?