МАЛЫЙ МЕХМАТ МГУ

Занятие 18. Жадный алгоритм

1.	У продавца имеется набор n гирек весом a₁, a₂, ..., a_n. Известно, что вес первой гирьки равен 1, а вес каждой следующей не превосходит суммарного веса предыдущих. Докажите, что с помощью своих гирек продавец может взвесить любой вес от 1 до a₁ + a₂ + ... + a_n.
2.	Два игрока по очереди проводят диагонали в правильном 111-угольнике. После каждого своего хода игрок платит противнику число рублей равное количеству пересечённых диагоналей. Кто из игроков может заведомо не остаться в проигрыше?
3.	В компьютерном классе имеется 50 компьютеров, которые нужно объединить в локальную сеть, затратив при этом как можно меньше провода (по суммарной длине). Системный администратор прелагает действовать следующим образом. Сначала соединит каждые два компьютера проводом, а затем будет перебирать все провода по длине — от самого длинного к самому короткому — и удалять очередной провод, если это не приводит к распаду сети. а) Докажите, что получится сеть с минимальной суммарной длиной проводов. б) Завхоз заявил, что после такой процедуры останется много обрезков, и что нужно действовать по-другому: выбирать на каждом шаге два самых близких компьютера и соединять их проводом, если между ними еще нет связи; затем следующие два, и так далее. Верно ли, что и в этом случае получится сеть с минимальной длиной проводов?
4.	Есть набор гирек 1, 2, 3, ... , N г и чашечные весы. Двое играющих по очереди кладут на весы по одной гирьке из набора, каждый на свою чашу. Выигрывает тот, после чьего хода установится равновесие. Может ли кто-нибудь из игроков всегда выигрывать независимо от игры противника?
5.	На плоскости дан набор из 200 векторов. Двое по очереди берут себе по одному вектору, пока они не кончатся. Выигрывает тот, у кого длина суммы векторов окажется больше. Кто выигрывает при правильной игре?
6.	Имеется аудитория и список заявок на занятия в этой аудитории (в заявке содержится время начала и окончания предполагаемого занятия, эти интервалы времени вообще говоря перекрываются). Требуется составить расписание занятий так, чтобы было удовлетворено наибольшее число заявок. Как это проще всего сделать?
7.	Дано n точек на координатной прямой. Нужно покрыть их наименьшим возможным количеством отрезков длины 1.

Пусть есть какая-то монетная система (например, в России используется система, состоящая из 1, 5, 10, 50 копеек) и требуется выплатить некую сумму этими монетами, выдав при этом наименьшее количество монет.

Жадный алгоритм выплаты определим так: чтобы выплатить N копеек, выдадим монету самого большого достоинства, не превосходящего N, а затем остаток (если он ненулевой) выплатим, применив для него жадный алгоритм.
Монетную систему назовём удобной, если выплата согласно жадному алгоритму является оптимальной по количеству выданных монет.

8.	а) Докажите, что система монет 1, p, p²,..., pⁿ является удобной для натурального p, большего 1. б) Докажите, что российская монетная система является удобной. в) Приведите пример неудобной монетной системы.