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

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

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

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

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

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

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

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

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

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

Фокусник с завязанными глазами выдаёт зрителю пять карточек с номерами от 1 до 5. Зритель прячет две карточки, а три отдаёт ассистенту фокусника. Ассистент указывает зрителю на две из них, и зритель называет номера этих карточек фокуснику (в том порядке, в каком захочет). После этого фокусник угадывает номера карточек, спрятанных у зрителя. Как фокуснику и ассистенту договориться, чтобы фокус всегда удавался?

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

  а)   <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 настоящие и две фальшивые, одинаковые по весу, но неизвестно, тяжелее или легче настоящих. Как за наименьшее число взвешиваний найти хотя бы одну настоящую монету?

В колоде 52 карты, по 13 каждой масти. Ваня вынимает из колоды по одной карте. Вынутые карты в колоду не возвращаются. Каждый раз перед тем, как вынуть карту, Ваня загадывает какую-нибудь масть. Докажите, что если Ваня каждый раз будет загадывать масть, карт которой в колоде осталось не меньше, чем карт любой другой масти, то загаданная масть совпадет с мастью вынутой карты не менее 13 раз.

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

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

На тарелке лежат 9 разных кусочков сыра. Всегда ли можно разрезать один из них на две части так, чтобы полученные 10 кусочков делились бы на две порции равной массы по 5 кусочков в каждой?

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

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

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

Двое играют в следующую игру: первый выписывает в ряд по своему желанию буквы А или Б (слева направо, одну за другой; по одной букве за ход), а второй после каждого хода первого меняет местами любые две из выписанных букв или ничего не меняет (это тоже считается ходом). После того, как оба игрока сделают по 1999 ходов, игра заканчивается. Может ли второй играть так, чтобы при любых действиях первого игрока в результате получился палиндром (то есть слово, которое читается одинаково слева направо и справа налево)?

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

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