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

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

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

Петя и Вася играют в следующую игру. Петя загадывает натуральное число <i>x</i> с суммой цифр 2012. За один ход Вася выбирает любое натуральное число <i>a</i> и узнаёт у Пети сумму цифр числа  |<i>x – a</i>|.  Какое минимальное число ходов необходимо сделать Васе, чтобы гарантированно определить <i>x</i>?

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

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

На столе лежит куча из более чем <i>n</i>² камней. Петя и Вася по очереди берут камни из кучи, первым берёт Петя. За один ход можно брать любое простое число камней, меньшее <i>n</i>, либо любое кратное <i>n</i> число камней, либо один камень. Докажите, что Петя может действовать так, чтобы взять последний камень независимо от действий Васи.

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

Имеется 200 гирек массами 1, 2, ..., 200 грамм. Их разложили на две чаши весов по 100 гирек на каждую, и весы оказались в равновесии. На каждой гирьке записали, сколько гирек на противоположной чаше легче неё. Докажите, что сумма чисел, записанных на гирьках левой чаши, равна сумме чисел, записанных на гирьках правой чаши.

На клетчатой доске из 2012 строк и  <i>k</i> > 2  столбцов в какой-то клетке самого левого столбца стоит фишка. Двое ходят по очереди, за ход можно передвинуть фишку вправо, вверх или вниз на одну клетку, при этом нельзя передвигать фишку на клетку, в которой она уже побывала. Игра заканчивается, как только один из игроков передвинет фишку в самый правый столбец. Но будет ли такой игрок выигравшим или проигравшим – сообщается игрокам только в тот момент, когда фишка попадает в предпоследний столбец (второй справа). Может ли один из игроков обеспечить себе выигрыш?

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

На дверце сейфа написано произведение степеней<i>a</i>^<i>n</i><i>b</i>^<i>m</i><i>c</i>^<i>k</i>. Чтобы дверца открылась, надо заменить каждую из шести букв натуральным числом так, чтобы в произведении получился куб натурального числа. Пинки, не подумав, уже заменил какие-то три буквы числами. Всегда ли Брейн сможет заменить три оставшиеся, чтобы дверца открылась?

Оля и Максим оплатили путешествие по архипелагу из 2009 островов, где некоторые острова связаны двусторонними маршрутами катера. Они путешествуют, играя. Сначала Оля выбирает остров, на который они прилетают. Затем они путешествуют вместе на катерах, по очереди выбирая остров, на котором еще не были (первый раз выбирает Максим). Кто не сможет выбрать остров, проиграл. Докажите, что Оля может выиграть.

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

Есть 40 гирек массой 1 г, 2 г, ..., 40 г. Из них выбрали 10 гирь чётной массы и положили на левую чашу весов. Затем выбрали 10 гирь нечётной массы и положили на правую чашу весов. Весы оказались в равновесии. Докажите, что на какой-нибудь чаше есть две гири с разностью масс в 20 г.

В вершинах шестиугольника <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 до 1001 один прячут, а остальные в случайном порядке надевают на мудрецов. Каждый видит только номера на колпаках всех впереди стоящих. Далее мудрецы по порядку от заднего к переднему называют вслух целые числа. Каждое число должно быть от 1 до 1001, причём нельзя называть то, что уже было сказано. Результат теста – число мудрецов, назвавших номер своего колпака. Мудрецы заранее знали условия теста и могли договориться, как действовать.

  а) Могут ли они гарантировать результат более 500?

  б) Могут ли они гарантировать результат не менее 999?

Было8грузиков массами1,2, <i> .. </i>, 8 г. Один из них потерялся, а остальные выложили в ряд по возрастанию массы. Есть весы с лампочкой, при помощи которых можно проверить, имеют ли две группы грузиков одинаковую массу. Как за3 проверки определить, какой именно грузик потерялся?

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

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

Игровое поле представляет собой полоску1<i>× N </i>. В начале игры на нескольких крайних левых полях стоит по одной белой шашке, на стольких же крайних правых полях — по одной чёрной шашке. Белые и Чёрные ходят по очереди, начинают Белые. Ход заключается в передвижении одной из своих шашек в направлении противника (Белые ходят направо, Чёрные — налево). Можно делать простой ход или бить шашки соперника. При простом ходе разрешается перемещать шашку на любое число клеток, но нельзя перепрыгивать ни через свои шашки, ни через чужие. Бьют шашки соперника по тем же правилам, что и в обычных шашках: Шашка бьёт шашку соперника, стоящую на соседнем поле, если следующее за ним поле свободно. При этом своя шашка перемещается на это свободное поле, а побитая шашка соперника снимается с д...

Двое играют на треугольной доске (см. рис.), закрашивая по очереди на ней треугольные клеточки. Одна клетка (начальная) уже закрашена перед началом игры. Первым ходом закрашивается клеточка, граничащая (по стороне) с начальной, а каждым следующим ходом — клетка, граничащая с только что закрашенной. Повторно клетки красить нельзя. Тот, кто не может сделать ход, проигрывает. Кто — начинающий или его соперник — победит в этой игре, как бы ни играл его партнёр? Рассмотрите случаи: а) Начальная клетка — угловая, поле любого размера; б) Поле и начальная клетка как на рисунке к этому заданию; в) Общий случай: поле любого размера, и начальная клетка в нём произвольная. г)<b>Дополнительное задание.</b>Можно подумать, что начальная клетка определяет исход партии независимо от действий иг...

Два игрока ходят по очереди. Перед началом игры у них есть поровну горошин. Ход состоит в передаче сопернику любого числа горошин. Не разрешается передавать такое количество горошин, которое до этого уже кто-то в этой партии передавал. Ноль горошин тоже передавать нельзя. Тот, кто не может сделать очередной ход по правилам, — считается проигравшим. Кто — начинающий или его соперник — победит в этой игре, как бы ни играл его партнёр? Рассмотрите случаи: а) У каждого по две горошины; б) У каждого по три горошины; в) У каждого по десять горошин; г) Общий случай: у каждого по<i> N </i>горошин.

В ряд слева направо лежит 31 кошелёк, в каждом по 100 монет. Из одного кошелька часть монет переложили: по одной монете в каждый из кошельков справа от него. За один вопрос можно узнать суммарное число монет в любом наборе кошельков. За какое наименьшее число вопросов можно гарантированно вычислить "облегчённый" кошелёк?

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