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

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

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

Лиса Алиса и кот Базилио вырастили на дереве 20 фальшивых купюр и теперь вписывают в них семизначные номера. На каждой купюре есть 7 пустых клеток для цифр. Базилио называет по одной цифре "1" или "2" (других он не знает), а Алиса вписывает названную цифру в любую свободную клетку любой купюры и показывает результат Базилио. Когда все клетки заполнены, Базилио берет себе как можно больше купюр с разными номерами (из нескольких с одинаковым номером он берет лишь одну), а остаток забирает Алиса. Какое наибольшее количество купюр может получить Базилио, как бы ни действовала Алиса?

Перед гномом лежат три кучки бриллиантов: 17, 21 и 27 штук. В одной из кучек лежит один фальшивый бриллиант. Все бриллианты имеют одинаковый вид, все настоящие бриллианты весят одинаково, а фальшивый отличается от них по весу. У гнома есть чашечные весы без гирь. Гному надо за одно взвешивание найти кучку, в которой все бриллианты настоящие. Как это сделать?

Победив Кащея, потребовал Иван золота, чтобы выкупить Василису у разбойников. Привёл его Кащей в пещеру и сказал: "В сундуке лежат золотые слитки. Но просто так их унести нельзя: они заколдованы. Переложи себе в суму один или несколько. Потом я переложу из сумы в сундук один или несколько, но обязательно другое число. Так мы будем по очереди перекладывать их: ты в суму, я в сундук, каждый раз новое число. Когда новое перекладывание станет невозможным, сможешь унести свою суму со слитками". Какое наибольшее число слитков может унести Иван, как бы ни действовал Кащей, если в сундуке исходно лежит  а) 13;  б) 14 золотых слитков? Как ему это сделать?

Семь монет расположены по кругу. Известно, что какие-то четыре из них, идущие подряд, – фальшивые и что каждая фальшивая монета легче настоящей. Объясните, как найти две фальшивые монеты за одно взвешивание на чашечных весах без гирь. (Все фальшивые монеты весят одинаково.)

В вершинах шестиугольника <i>ABCDEF</i> (см. рис.) лежали 6 одинаковых на вид шариков: в <i>A</i> — массой 1 г, в <i>B</i> — 2 г, ..., в <i>F</i> — 6 г. Шутник поменял местами два шарика в противоположных вершинах. Имеются двухчашечные весы, позволяющие узнать, в какой из чаш масса шариков больше. Как за одно взвешивание определить, какие именно шарики переставлены?<div align="center"><img src="/storage/problem-media/116208/problem_116208_img_2.gif"></div>

Дракон запер в пещере шестерых гномов и сказал: "У меня есть семь колпаков семи цветов радуги. Завтра утром я завяжу вам глаза и надену на каждого по колпаку, а один колпак спрячу. Затем сниму повязки, и вы сможете увидеть колпаки на головах у других, но общаться я вам уже не позволю. После этого каждый втайне от других скажет мне цвет спрятанного колпака. Если угадают хотя бы трое, всех отпущу. Если меньше – съем на обед". Как гномам заранее договориться действовать, чтобы спастись?

В тюрьме Кощея пять камер, пронумерованных числами от1до5. В каждой камере сидит по одному узнику. Василиса уговорила Кощея провести эксперимент: на стене каждой камеры она один раз напишет какой-нибудь номер и в полночь каждый узник перейдёт в камеру с указанным номером (если номер на стене совпадает с номером камеры, то узник никуда не переходит). В следующую полночь узники опять должны перейти из камеры в камеру согласно указаниям на стене, и так они действуют в течение пяти ночей. Если расположение узников в камерах в течение всех шести дней (включая первый) ни разу не повторится, то Василисе дадут звание Премудрой, а узников отпустят. Помогите Василисе написать номера в камерах.

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

У Юры есть калькулятор, который позволяет умножать число на 3, прибавлять к числу 3 или (если число делится на 3 нацело) делить на 3. Как на этом калькуляторе получить из числа 1 число 11?

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

  а)   <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">

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

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

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

Кощей Бессмертный похитил у царя трёх дочерей. Отправился Иван-царевич их выручать. Приходит он к Кощею, а тот ему и говорит: "Завтра поутру увидишь пять заколдованных девушек. Три из них – царёвы дочери, а ещё две – мои. Для тебя они будут неотличимы, а сами друг дружку различать смогут. Я подойду к одной из них и стану у неё спрашивать про каждую из пятерых: "Это царевна?". Она может отвечать и правду, и неправду, но ей дозволено назвать царевнами ровно двоих (себя тоже можно называть). Потом я так же опрошу каждую из остальных девушек, и они тоже должны будут назвать царевнами ровно двоих. Если после этого угадаешь, кто из них и вправду царевны, отпущу тебя восвояси невредимым. А если ещё и догадаешься, которая царевна старшая, которая средняя, а которая младшая, то и их...

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

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

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

На физическом кружке учитель поставил следующий эксперимент. Он разложил на чашечные весы 16 гирек массами 1, 2, 3, ..., 16 грамм так, что одна из чаш перевесила. Пятнадцать учеников по очереди выходили из класса и забирали с собой по одной гирьке, причем после выхода каждого ученика весы меняли свое положение и перевешивала противоположная чаша весов. Какая гирька могла остаться на весах?

Таня стоит на берегу речки. У неё есть два глиняных кувшина: один — на 5 литров, а про второй Таня помнит лишь то, что он вмещает то ли 3, то ли 4 литра. Помогите Тане определить ёмкость второго кувшина. (Заглядывая в кувшин, нельзя понять, сколько в нём воды.)

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

Три ёжика делили три кусочка сыра массами 5 г, 8 г и 11 г. Лиса стала им помогать. Она может от любых двух кусочков одновременно отрезать и съесть по 1 г сыра. Сможет ли лиса оставить ёжикам равные кусочки сыра?

Семья ночью подошла к мосту. Папа может перейти его за 1 минуту, мама – за 2, малыш – за 5, а бабушка – за 10 минут. У них есть один фонарик. Мост выдерживает только двоих. Как им перейти мост за 17 минут? (Если переходят двое, то они идут с меньшей из их скоростей. Двигаться по мосту без фонарика нельзя. Светить издали нельзя. Носить друг друга на руках нельзя.)

Имеются 6 запертых чемоданов и 6 ключей к ним. При этом неизвестно, к какому чемодану подходит какой ключ. Какое наименьшее число попыток надо сделать, чтобы наверняка открыть все чемоданы? А сколько понадобится попыток, если ключей и чемоданов будет не по 6, а по 10?

Миша загадал число не меньше 1 и не больше 1000. Васе разрешено задавать только такие вопросы, на которые Миша может ответить «да» или «нет» (Миша всегда говорит правду). Может ли Вася за 10 вопросов определить загаданное число?

Имеются неправильные чашечные весы, мешок крупы и правильная гиря в 1 кг. Как отвесить на этих весах 1 кг крупы?