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

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

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

В вершинах шестиугольника <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?

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

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

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

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

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

На столе лежат в ряд пять монет: средняя — вверх орлом, а остальные — вверх решкой. Разрешается одновременно перевернуть три рядом лежащие монеты. Можно ли при помощи нескольких таких переворачиваний все пять монет положить вверх орлом?

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

Петя и Миша играют в такую игру. Петя берёт в каждую руку по монетке: в одну – 10 коп., а в другую – 15. После этого содержимое левой руки он умножает на 4, 10, 12 или 26, а содержимое правой руки – на 7, 13, 21 или 35. Затем Петя складывает два получившихся произведения и называет Мише результат. Может ли Миша, зная этот результат, определить, в какой руке у Пети – правой или левой – монета достоинством в 10 коп.?

<b>Продавец с гирями.</b>Четырьмя гирями продавец может взвесить любое целое число килограммов, от 1 до 40 включительно. Общая масса гирь равна 40 кг. Какими гирями располагает продавец?

Первоначально на каждом поле доски 1×<i>n</i> стоит шашка. Первым ходом разрешается переставить любую шашку на соседнюю клетку (одну из двух, если шашка не с краю), так что образуется столбик из двух шашек. Далее очередным ходом каждый столбик можно передвинуть в любую сторону на столько клеток, сколько в нём шашек (в пределах доски); если столбик попал на непустую клетку, он ставится на стоящий там столбик и объединяется с ним. Докажите, что за  <i>n</i> – 1  ход можно собрать все шашки на одной клетке.

На экране компьютера горит число, которое каждую минуту увеличивается на 102. Начальное значение числа 123. Программист Федя имеет возможность в любой момент изменять порядок цифр числа, находящегося на экране. Может ли он добиться того, чтобы число никогда не стало четырёхзначным?

Как при помощи чашечных весов без гирь разделить 24 кг гвоздей на две части  — 9 и 15 кг?

Известно, что "медные" монеты достоинством в 1, 2, 3, 5 коп. весят соответственно 1, 2, 3, 5 г. Среди четырех "медных" монет (по одной каждого достоинства) есть одна бракованная, отличающаяся весом от нормальной. Как с помощью взвешиваний на чашечных весах без гирь определить бракованную монету? <small>Также доступны документы в формате TeX</small>

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

(В хождении были монеты в 1, 3, 5, 10, 20 и 50 коп.)

Лиса Алиса и Кот Базилио  — фальшивомонетчики. Базилио делает монеты тяжелее настоящих, а Алиса  — легче. У Буратино есть 15 одинаковых по внешнему виду монет, но какая-то одна  — фальшивая. Как двумя взвешиваниями на чашечных весах без гирь Буратино может определить, кто сделал фальшивую монету  — Кот Базилио или Лиса Алиса?

Трое туристов должны перебраться с одного берега реки на другой. В их распоряжении старая лодка, которая может выдержать нагрузку всего в 100 кг. Вес одного из туристов 45 кг, второго  — 50 кг, третьего  — 80 кг. Как должны они действовать, чтобы перебраться на другой берег?

Из набора гирек с массами 1, 2, ..., 101 г потерялась гирька массой 19 г. Можно ли оставшиеся 100 гирек разложить на две кучки по 50 гирек в каждой так, чтобы массы обеих кучек были одинаковы?

За один ход разрешается или удваивать число, или стирать его последнюю цифру. Можно ли за несколько ходов получить из числа 458 число 14?

Золотоискатель Джек добыл 9 кг золотого песка. Сможет ли он за три взвешивания отмерить 2 кг песка с помощью чашечных весов: а) с двумя гирями  — 200 г и 50 г; б) с одной гирей 200 г?