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

Кружок 8 класса

Руководитель Варвара Алексеевна Косоротова
2010/2011 учебный год

Занятие 19. Сельская жизнь и оптимальное управление

В библиотеке села Гадюкино ввели правило: всякий, кто хочет войти, перед входом должен записать на зелёной доске число людей, уже находящихся внутри. При уходе же каждый должен записать на коричневой доске число людей, оставшихся после этого в библиотеке. Единственная входная дверь (на ней обе доски и висят) так узка, что в проёме двоим не разминуться. Сельская библиотекарша тётя Клава, приходя утром, стирает всё с обеих досок и по правилу пишет ноль на зелёной доске. Докажите, что вечером, когда она закрывает библиотеку и пишет ноль на коричневой, на досках остаётся один и тот же набор чисел.

Решение

Решение. Заметим, что тетя Клава, и приходя в библиотеку раньше всех, и уходя из нее позже всех, пишет на соответствующей доске одно и то же число 0. Если кто-то из посетителей приходит, а затем уходит до того, как кто-нибудь еще придет или уйдет, то он тоже пишет на обеих досках одно и то же число. Если же, скажем, пришел Петя, потом пришел Вася, потом ушел Петя, и только потом ушел Вася, они вместе написали одну и ту же пару чисел на досках. Например, можно попросить их поменяться временами выхода; тогда число, которое должен был написать Петя, напишет Вася, и наоборот. Используя этот прием, можно упорядочить посещения так, чтобы сначала все посетители по очереди приходили, а потом уходили в обратном порядке (то есть пришедший раньше уйдет позже, и наоборот). В этом случае каждый посетитель будет писать на обеих досках одно и то же число.

2.

В селе Гадюкино стояла жара, и народ решил призвать дождь с помощью установок, построенных изобретателем дядей Васей. По расчётам, для вызова дождя все n установок должны одновременно работать в течение часа. Однако необходимых для работы высоковольтных розеток в селе ровно n, и к каждой розетке может быть подключено только одно устройство. Стоимость S потраченного одной установкой электричества рассчитывается по формуле S = ClPt, где t — время работы в часах, P — мощность в ваттах, l — расстояние от розетки до электростанции в метрах, C = 0,1 руб./(Вт·ч·м) — постоянная Чубайса. Помогите определить, какую установку к какой розетке надо подключить, чтобы вызвать дождь с наименьшей платой за электричество. Мощности установок и расстояния от розеток до электростанции считаются известными и, вообще говоря, различными.

а): Решите задачу для n = 2.
b): Пользуясь предыдущим пунктом, решите задачу для произвольного натурального n > 1. Для этого представьте себе, что установки уже как-то подключены, и подумайте, как сделать плату меньше.

Решение

Решение.

a) Пусть P₁ и P₂ — мощности установок, l₁ и l₂ — расстояния от розеток до станции, P₁ ≥ P₂, l₁ ≥ l₂. Есть всего два способа подключения установок к розеткам. При первом способе стоимость использования установок составит C(P₁l₁ + P₂l₂)t, а при втором — C(P₁l₂ + P₂l₁)t. Множители C и t = 1 ч — фиксированные величины, они одинаковы при обоих способах подключения. Поэтому достаточно сравнить между собой числа P₁l₁ + P₂l₂ и P₁l₂ + P₂l₁. Их разность P₁l₁ + P₂l₂ - P₁l₂ - P₂l₁ = (P₁ - P₂)(l₁ - l₂) положительна (так как каждый из сомножителей положителен по предположению). Это значит, что второй способ подключения — более экономный. Значит, более мощную установку надо подключать к розетке, менее удаленной от электростанции, а менее мощную — к более удаленной.

b) Для начала подключим установки как-нибудь. Если самая мощная установка подключена не к самой близкой розетке, то поменяем ее местами с той, которая подключена к самой близкой розетке. При этом изменится только плата за эти две установки, причём, согасно пункту а, она уменьшится. Дальше, если вторая по мощности установка подключена не ко второй по близости розетке, то аналогично можно поменять ее местами со второй по близости установкой и снова уменьшить плату. Продолжая действовать подобным образом, можно добиться того, что чем мощнее установка, тем ближе она к электростанции. И к этому расположению можно прийти из любого другого вышеуказанным способом с уменьшением платы. Значит, это и есть нужный нам способ подключения.

3.

В селе Гадюкино собрали небывало огромный урожай белокочанной и цветой капусты. Механизатор дядя Коля хочет отвезти часть на продажу в областной центр. По объёму в кузов грузовика влезает 20 т кочанной или 5 т цветной капусты, но при массе груза более 10 т машина ездить не может. На областном рынке 1 кг кочанной капусты покупают за 20 рублей, а 1 кг цветной — за 60 рублей Сколько какого вида нужно грузить дяде Коле, чтобы за одну машину капусты получить как можно больше денег?

Ответ Решение

Ответ. Надо грузить 6²/₃ т кочанной и 3¹/₃ т цветной капусты.

Решение.

У нас есть два ограничения: по весу и по объёму. Допутим, в машине уже что-то есть. Если и вес, и объём позволяют, догрузим любой капусты, от этого стоимость товара увеличится. Предположим, что мы набрали 10 т груза, но остался незанятый объём. Вытащим, скажем, 1 кг кочанной капусты и заменим на 1 кг цветной. Вес останется тем же, занятый объём увеличится, но прирастёт и стоимость. Поэтому будем заменять кочанную капусту цветной и дальше, пока не заполним весь объём грузового отсека. Если же вес груза изначально был меньше 10 т, но весь объём занят, вытащим 1 кг цветной капусты и заменим на 5 кг кочанной: от этого вырастет вес, но вырастет и стоимость. Эти соображения показывают, что стоимость товара максимальна тогда, когда полностью используются и грузоподъемность, и грузовместимость машины.

Погрузим в машину x т кочанной капусты. Тогда цветной капусты можно погрузить еще (10 - x) т. Теперь подберем число x так, чтобы погруженная капуста занимала весь отведенный объем. Пусть объем грузового отсека грузовика равен V м³. Это объем, занимаемый 20 т кочанной капусты или 5 т цветной капусты. Значит, 1 т кочанной капусты занимает объем ^V/₂₀ м³, а 1 т цветной — ^V/₅ м³. Значит, вся погруженная капуста имеет объем x· ^V/₂₀ + (10 − x)· ^V/₅ = V м³. Поделив обе части этого уравнения на ненулевой объем V, без труда найдем из него, что x = 6²/₃, y = 3¹/₃.

4.

На Гадюкинской Кольцевой Дороге имеется несколько бензозаправок. Бензина на одной заправке может не хватить на то, чтобы доехать до другой, но суммарный объём горючего на всех заправках достаточен для проезда по всей Дороге. Докажите, что механизатор дядя Коля может объехать всю Дорогу на грузовике, стартуя от одной из заправок (эту заправку дядя Коля выбирает сам) и заправляясь по пути. Предполагается, что на первой заправке дядя Коля может залить в бак не больше бензина, чем есть на этой заправке (а до этого бензина в баке нет). Расход топлива на километр пути считать постоянным, бак достаточно большой.

Решение

Решение. Для простоты введём на дороге одностороннее движение. Действительно, смысла ехать в обе стороны нет, так как бензина может впритык хватать лишь на одностороннее движение. Заметим, что всегда есть такая заправка А, от которой можно доехать до следующей заправки В (иначе на всех заправках в сумме не хватит топлива, чтобы объехать всю дорогу). Тогда поехать от A к B, заправиться в B и поехать дальше — всё равно что получить на заправке A весь бензин, что был на A и B вместе взятых, и поехать дальше мимо B. Значит, можно считать, что заправку B закрыли, а весь бензин из неё переместили на заправку A. К оставшимся заправкам применим те же соображения и закроем ещё какую-нибудь заправку. Так будем делать до тех пор, пока не останется одна-единственная заправка. На ней окажется бензин со всех ранее закрытых заправок (и с нее самой), а значит, его хватит на то, чтобы объехать всю дорогу.

5.

Гадюкинский лингвист и уфолог Тиглат Паласарыч выяснил, что в плутонианском языке всего четыре звука: Ы, Э, У и Ц, причём звук Ц — особый. Сказанный сам по себе, он означает некоторое слово, но если его пропустить или сказать лишний раз в другом слове, то полученное слово не будет отличаться от исходного. Кроме того, многие плутонианцы любят вместо УУУУУУУ, ЫЫЫЫЫЫЫ и ЭЭЭЭЭЭЭ говорить Ц, вместо УУУЫ — ЫУ, вместо ЭЭЫ — ЫЭ, вместо УЭ — ЭУ, так что если в слове заменить менее любимое сочетание на более любимое или наоборот, новое слово не будет отличаться от старого. На Плутоне 500 жителей. Могут ли они носить разные имена? Имя состоит из одного слова, но произвольного числа букв.

Решение

Решение. Возьмём какое-нибудь слово, выкинем из него все звуки Ц и рассмотрим самый последний звук Ы в нём. Если он стоит не в конце слова, то после него стоит то ли У, то ли Э. Заменяя сочетание ЫУ на УУУЫ или сочетание ЫЭ на ЭЭЫ, мы не изменяем слово, но передвигаем звук Ы ближе к концу слова. Будем двигать его дальше до самого конца. Точно так же можно сдвинуть в конец слова и остальные звуки Ы. Если звуков Ы окажется не менее семи, каждые семь подряд стоящих заменим на Ц и выкинем. Далее заменами ЭУ на УЭ мы можем собрать все звуки Э в начале слова. Выходит, каждое слово можно привести к виду ЭЭ…ЭЭУУ…УЫЫ…ЫЫ, где звуков каждого вида от нуля до шести, ведь каждые семь подряд идущих можно заменить на Ц и выкинуть. (Если звуков Э, У, Ы вообще не осталось, то считаем, что слово состоит из одного звука Ц.) Слов такого вида не более 7³ = 343 < 500, поэтому 500 различных имён на Плутоне нет.

6.

В селе Гадюкино собрались проводить конференцию «Ораторы об ораторах», где каждый участник должен был выступить с докладом о трёх других участниках. По плану, с утра все сидят в зале Дома Культуры. Докладчики по очереди выходят из зала на сцену, выступают, а затем сразу уезжают из села. Тем самым каждый участник слушает тех и только тех, кто читал до него. Оргкомитет конференции знает, о ком чей доклад, и определяет очерёдность выступлений.

а): Докажите, что оргкомитет может составить программу конференции так, что каждый участник послушает не более трёх докладов о себе.
b): Можно ли составить программу так, чтобы каждый выслушал не более двух докладов о себе?

Решение

Решение.

а) Составим программу хоть как-нибудь. Если каждый выслушивает не более трёх докладов о себе, то задача решена. Предположим, что Вася послушает о себе хотя бы четыре доклада. Переставим его в самое начало. Тогда Вася не услышит доклады о себе, зато расскажет о трёх участниках, заведомо присутствующих на момент доклада. Продолжим переставлять тех, кто услышит о себе слишком много. Что важно, при наших перестановках мы уменьшаем количество упоминаний о тех, кто находится в зале, хотя бы на единицу. Бесконечно так продолжаться не может, поскольку каждый докладчик упоминает не более трёх сидящих в зале. Значит, когда-нибудь нам станет некого переставлять. В этот момент мы и получим искомую программу.

b) Не всегда. Пусть, например, докладчиков семеро. Усадим их за круглый стол и попросим каждого прочесть доклад о трёх докладчиках, сидящих справа от него. Тогда о каждом будет прочитано три доклада, и последний по времени докладчик услышит о себе три раза.

7.

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

а): Докажите, что все празднования можно провести не более, чем за неделю.
b): Всегда ли хватит шести дней для Праздника?

Решение

Решение.

а) Отправим всех гадюкинцев на конференцию из предыдущей задачи, и пусть каждый прочтёт доклад о тех, в чьем саду он побывал. Составим программу, и сразу после выступления каждого докладчика будем назначать день, в который он будет отмечать Праздник Яблока. Гадюкинец не может праздновать в один день с теми, от кого он слышал доклад о себе (то есть с теми, кто побывал в его саду); это накладывает запрет не более чем на три дня из семи. Не может он праздновать и с теми, о ком он сам рассказывает (то есть с теми, в чьем саду он побывал); это запрещает ещё не более трёх дней. Как бы то ни было, остаётся хотя бы один день, на который пока запретов нет. Вот пусть в этот день он и празднует.

b) Не всегда. Воспользуйтесь примером из задачи 6b.

8.

Гадюкинский лингвист и уфолог Тиглат Паласарыч заметил, что в немалом количестве инопланетных языков никакое слово не может быть началом другого слова. Чтобы понять, насколько это правило плохое, для всех таких языков лингвист вычислил значение выражения

`a`₁	`a`₂	+ ... +	`a`_K	,
`N`	`N`²	+ ... +	`N`^K	,

где N — число букв в алфавите, K — наибольшая возможная длина слова, a_s — количество s-буквенных слов в языке (s = 1, 2, 3, ..., K). Докажите, что для каждого языка Тиглат Паласарыч получил число, не превосходящее единицы.

Решение

Решение.

Рассмотрим какое-нибудь слово **…**a длины K, а также все слова, отличающиеся от него только последней буквой. Всего таких слов не более N. Заменим все эти слова на слово **…**, получающееся отрезанием последней буквы. Тогда K-буквенных слов в языке станет меньше, и по-прежнему никакое слово не окажется началом другого. Поскольку никакое слово и раньше не было началом другого слова, слово **…** будет новым (K - 1)-буквенным словом (ведь с него начинались те слова, которые мы заменили на него). В результате этой операции число a_K уменьшится не более чем на N, а число a_K-1 увеличится на 1. При этом значение выражения, которое вычислил лингвист, может только увеличиться. Действительно,

a₁

+ ... +

a_{K - 2}

a_{K - 1} + 1

a_K - N

a₁

+ ... +

a_{K - 2}

a_{K - 1}

a_K

N

a₁

+ ... +

a_{K - 2}

a_{K - 1}

a_K

N

N^{K - 2}

N^{K - 1}

N^K

N

N^{K - 2}

N^{K - 1}

N^K

N

N^{K - 2}

N^{K - 1}

N^K

То есть если количество K-буквенных слов уменьшилось ровно на N, значение выражения останется неизменным. А если оно уменьшилось не так сильно, то значение выражения возрастет (убедитесь в этом самостоятельно, используя приведенное выше равенство).

Продолжим убирать из языка K-буквенные слова, заменяя их на (K - 1)-буквенные. Потом точно так же поступим с (K - 1)-буквенными словами, и так далее. Будем делать так до тех пор, пока не останутся только слова из одной буквы. А в этом случае a₁ = N, K = 1, и значение интересующего нас выражения окажется в точности равным 1. А раз на каждом шаге его значение не уменьшалось, то оно и первоначально не превосходило единицы.