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

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

100 пиратов сыграли в карты на золотой песок, а потом каждый посчитал, сколько он в сумме выиграл либо проиграл. У каждого проигравшего хватает золота, чтобы расплатиться. За одну операцию пират может либо раздать всем поровну золота, либо получить с каждого поровну золота. Докажите, что можно за несколько таких операций добиться того, чтобы каждый получил (в сумме) свой выигрыш либо выплатил проигрыш. (Разумеется, общая сумма выигрышей равна сумме проигрышей.)

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

На левую чашу весов положили два шара радиусов 3 и 5, а на правую — один шар радиуса 8. Какая из чаш перевесит? (Все шары изготовлены целиком из одного и того же материала.)

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

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

  а)   <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>x</i>³ + ...<i>x</i>² + ...<i>x</i> + ... = 0.  Два школьника по очереди вписывают вместо многоточий действительные числа. Цель первого – получить уравнение, имеющее ровно один действительный корень. Сможет ли второй ему помешать?

На прямоугольном листе бумаги отмечены

  а) несколько точек на одной прямой;

  б) три точки.

Разрешается сложить лист бумаги несколько раз по прямой так, чтобы отмеченные точки не попали на линии сгиба, и затем один раз шилом проколоть сложенный лист насквозь. Докажите, что это можно сделать так, чтобы дырки оказались в точности в отмеченных точках и лишних дырок не получилось.

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

Имеется 81 гиря весом 1²г, 2²г, 3²г, ..., 81²г. Разложить их на 3 равные по весу кучи.

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

Мама и сын играют. Сначала сын режет головку сыра 300 г на 4 куска. Затем мама распределяет 280 г масла на 2 тарелки. Наконец, сын раскладывает куски сыра на те же тарелки. Он выиграет, если на каждой тарелке сыра будет не меньше, чем масла (иначе выиграет мама). Кто из них может победить, как бы ни действовал другой?

На столе лежит колода из 36 карт, верхняя из которых червонный туз. За одно «перемешивание» фокусник снимает верхнюю половину колоды и кладёт рядом с нижней, а затем делает так, чтобы карты двух стопок чередовались: сначала нижняя карта левой или правой стопки, потом первая снизу другой стопки, потом вторая снизу карта первой стопки, вторая снизу карта другой стопки, и так далее (см. рисунок).<img src="/storage/problem-media/67472/problem_67472_img_2.png">Какое наименьшее число перемешиваний нужно сделать фокуснику, чтобы червонный туз оказался нижней картой колоды? При каждом перемешивании то, из какой половины карта окажется снизу, фокусник выбирает сам.

Кусок сыра массой 1 кг разрезали на $n\geqslant 4$ кусков массами меньше 600 г. Оказалось, что их нельзя разбить на две кучки так, чтобы масса каждой кучки была не меньше 400 г, но не больше 600 г (кучка может состоять из одного или нескольких кусков). Докажите, что найдутся три таких куска, что суммарная масса любых двух из них больше 600 г.

Если Вася делит пирог или кусок пирога на две части, то всегда делает их равными по массе. А если делит на большее число частей, то может сделать их какими угодно, но обязательно все разной массы. За несколько таких дележей Вася разрезал пирог на $N$ частей. При каждом ли $N$ ≥ 10 все части могли получиться равными по массе? (Объединять части нельзя.)

Если Вася делит пирог или кусок пирога на две части, то всегда делает их равными по массе. А если делит на большее число частей, то может сделать их какими угодно, но обязательно все разной массы. За несколько таких дележей Вася разрезал пирог на 17 частей. Могли ли все части оказаться равными по массе? (Объединять части нельзя.)

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

У математика есть 19 различных гирь, массы которых в килограммах равны $\ln 2$, $\ln 3$, $\ln 4, \ldots, \ln 20$, и абсолютно точные двухчашечные весы. Он положил несколько гирь на весы так, что установилось равновесие. Какое наибольшее число гирь могло оказаться на весах?

Петя и Вася играют на отрезке $[0; 1]$, в котором отмечены точки $0$ и $1$. Игроки ходят по очереди, начинает Петя. Каждый ход игрок отмечает ранее не отмеченную точку отрезка. Если после хода очередного игрока нашлись три последовательных отрезка между соседними отмеченными точками, из которых можно сложить треугольник, то сделавший такой ход игрок объявляется победителем, и игра заканчивается. Получится ли у Пети гарантированно победить?

Петя загадал положительную несократимую дробь $x = \frac{m}{n}$. За один ход Вася называет положительную несократимую дробь $y$, не превосходящую 1, и Петя в ответ сообщает Васе числитель несократимой дроби, равной сумме $x+y$. Как Васе за два хода гарантированно узнать $x$?

На Поле Чудес выросло 8 золотых монет, но стало известно, что ровно три из них фальшивые. Все настоящие монеты весят одинаково, все фальшивые тоже, но они легче настоящих. Лиса Алиса и Буратино собрали монеты и стали их делить. Алиса собирается отдать Буратино три монеты, но он хочет сначала проверить, все ли они настоящие. Сможет ли он сделать это за два взвешивания на чашечных весах без гирь?

16 карточек с целыми числами от 1 до 16 разложены лицевой стороной вниз в виде таблицы $4\times4$ так, что карточки, на которых записаны соседние числа, лежат рядом (соприкасаются по стороне). Какое наименьшее число карточек нужно одновременно перевернуть, чтобы наверняка определить местоположение всех чисел (как бы ни были разложены карточки)?

В комнате находится несколько детей и куча из 1000 конфет. Дети по очереди подходят к куче. Каждый подошедший делит количество конфет в куче на количество детей в комнате, округляет (если получилось нецелое), забирает полученное число конфет и выходит из комнаты. При этом мальчики округляют вверх, а девочки – вниз. Докажите, что суммарное количество конфет у мальчиков, когда все выйдут из комнаты, не зависит от порядка детей в очереди.

а) У Тани есть 4 одинаковые с виду гири, массы которых равны 1000, 1002, 1004 и 1005 г (неизвестно, где какая), и чашечные весы (показывающие, какая из двух чаш перевесила или что имеет место равенство). Может ли Таня за 4 взвешивания гарантированно определить, где какая гиря? (Следующее взвешивание выбирается по результатам прошедших.) б) Тот же вопрос, если у весов левая чашка на 1 г легче правой, так что весы показывают равенство, если масса на левой чашке на 1 г больше, чем на правой.

По кругу стоят буквы A и B, всего 41 буква. Можно заменять ABA на B и наоборот, а также BAB на A и наоборот.

Верно ли, что из любого начального расположения можно получить такими операциями круг, на котором стоит ровно одна буква?