Олимпиадные задачи по теме «Теория алгоритмов» для 8 класса - сложность 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 клетки левой половины покрашены в чёрный цвет, а остальные – в белый. За одну операцию разрешается перекрасить в противоположный цвет все клетки внутри любого прямоугольника. Как за три операции из первоначальной раскраски получить шахматную?
На физическом кружке учитель поставил следующий эксперимент. Он разложил на чашечные весы 16 гирек массами 1, 2, 3, ..., 16 грамм так, что одна из чаш перевесила. Пятнадцать учеников по очереди выходили из класса и забирали с собой по одной гирьке, причем после выхода каждого ученика весы меняли свое положение и перевешивала противоположная чаша весов. Какая гирька могла остаться на весах?
Таня стоит на берегу речки. У неё есть два глиняных кувшина: один на 5 литров, а про второй Таня помнит лишь то, что он вмещает то ли 3, то ли 4 литра. Помогите Тане определить ёмкость второго кувшина. (Заглядывая в кувшин, нельзя понять, сколько в нём воды.)
Фили и Кили играют в шахматы. Кроме шахматной доски у них есть одна ладья, которую они поставили в правый нижний угол, и делают ей ходы по очереди, причем ходить разрешается только вверх или влево (на любое количество клеток). Кто не может сделать хода, тот проиграл. Кили ходит первым. Кто выиграет при правильной игре?
Первоначально на каждом поле доски 1×<i>n</i> стоит шашка. Первым ходом разрешается переставить любую шашку на соседнюю клетку (одну из двух, если шашка не с краю), так что образуется столбик из двух шашек. Далее очередным ходом каждый столбик можно передвинуть в любую сторону на столько клеток, сколько в нём шашек (в пределах доски); если столбик попал на непустую клетку, он ставится на стоящий там столбик и объединяется с ним. Докажите, что за <i>n</i> – 1 ход можно собрать все шашки на одной клетке.
На экране компьютера горит число, которое каждую минуту увеличивается на 102. Начальное значение числа 123. Программист Федя имеет возможность в любой момент изменять порядок цифр числа, находящегося на экране. Может ли он добиться того, чтобы число никогда не стало четырёхзначным?
Известно, что "медные" монеты достоинством в 1, 2, 3, 5 коп. весят соответственно 1, 2, 3, 5 г. Среди четырех "медных" монет (по одной каждого достоинства) есть одна бракованная, отличающаяся весом от нормальной. Как с помощью взвешиваний на чашечных весах без гирь определить бракованную монету? <small>Также доступны документы в формате TeX</small>
Какие восемь монет нужно взять, чтобы с их помощью можно было бы без сдачи заплатить любую сумму от 1 коп. до 1 руб.?
(В хождении были монеты в 1, 3, 5, 10, 20 и 50 коп.)
За один ход разрешается или удваивать число, или стирать его последнюю цифру. Можно ли за несколько ходов получить из числа 458 число 14?
Имеются чашечные весы без гирь и 3 одинаковые по внешнему виду монеты. Одна из монет фальшивая, причём неизвестно, легче она настоящих монет или тяжелее (настоящие монеты одного веса). Сколько надо взвешиваний, чтобы определить фальшивую монету? Решите ту же задачу в случаях, когда имеется 4 монеты и 9 монет.
Имеются чашечные весы без гирь и 3 одинаковые по внешнему виду монеты, одна из которых фальшивая: она легче настоящих (настоящие монеты одного веса). Сколько надо взвешиваний, чтобы определить фальшивую монету? Решите ту же задачу в случаях, когда имеется 4 монеты и 9 монет.
Крестьянину надо перевезти через речку волка, козу и капусту. Лодка вмещает одного человека, а с ним либо волка, либо козу, либо капусту. Если без присмотра оставить козу и волка, волк съест козу. Если без присмотра оставить капусту и козу, коза съест капусту. Как крестьянину перевезти свой груз через речку?
В первой кучке лежит 100 конфет, а во второй — 200 конфет. За ход можно взять любое количество конфет из любой кучки. Выигрывает взявший последнюю. Кто выигрывает при правильной игре?
Белая ладья преследует чёрного слона на доске3×1969 клеток (они ходят по очереди по обычным правилам). Как должна играть ладья, чтобы взять слона? Первый ход делают белые.
Имеются весы с двумя чашами и по одной гире в 1 г, 3 г, 9 г, 27 г и 81 г. Как уравновесить груз в 61 г, положенный на чашу весов?
В одной урне лежат два белых шара, в другой два черных, в третьей - один белый и один черный. На каждой урне висела табличка, указывающее ее содержимое: ББ, ЧЧ, БЧ. Некто перевесил таблички так, что теперь каждая табличка указывает содержимое урны неправильно. Разрешается вынуть шар из любой урны, не заглядывая в нее. Какое наименьшее число извлечений потребуется, чтобы определить состав всех трех урн?
У Вани работает 10 сотрудников. Каждый месяц Ваня повышает зарплату на 1 рубль ровно девятерым (по своему выбору).
Как Ване повышать зарплаты, чтобы сделать их одинаковыми? (Зарплата – целое число рублей.)
Ладья стоит на поле a1 шахматной доски. За ход разрешается сдвинуть ее на любое число клеток вправо или вверх. Выигрывает тот, кто поставит ладью на клетку h8. Кто выигрывает при правильной игре?
Какие веса могут иметь три гири для того, чтобы с их помощью можно было взвесить любое целое число килограммов от 1 до 10 на чашечных весах (гири можно ставить на обе чашки)? Приведите пример.
Нужно узнать пятизначный номер телефона, задавая вопросы, на которые возможен ответ "да" или "нет". За какое наименьшее число вопросов это гарантированно можно сделать (при условии, что на вопросы даются правильные ответы)?
Каждую из трех котлет нужно пожарить на сковороде с двух сторон в течение пяти минут каждую сторону. На сковороде умещается только две котлеты. Можно ли сжарить все три котлеты быстрее, чем за 20 минут (временем на переворачивание и перекладывание котлет пренебрегаем)?
В компанию из N человек пришел журналист. Ему известно, что в этой компании есть человек Z, который знает всех остальных членов компании, но его не знает никто. Журналист может к каждому члену компании обратиться с вопросом: "Знаете ли вы такого-то?" Найдите наименьшее количество вопросов, достаточное для того, чтобы наверняка найти Z. (Все отвечают на вопросы правдиво. Одному человеку можно задавать несколько вопросов.)