Торговля без денег
Каждый из семи островов A, B, C, D, E, F, G производит и потребляет все или некоторые из 2023 товаров. Будем обозначать через dij \geq 0 потребность острова i в товаре j, а через sij \geq 0 объем производства островом i товара j, где i \in {A, B, C, D, E, F, G}, j \in {1,..., 2023}. Величины dij и sij предопределены и неизменны. Между островами возможен обмен, но денег в экономике нет. Будем называть остров i счастливым, если для любого товара j его потребление на острове i не меньше, чем dij.
а) (3 балла) Предположим, что существует волшебник, который может свободно перераспределять произведенные товары между островами. Запишите условие на dij, sij, при котором волшебник может сделать так, чтобы каждый остров был счастливым. Докажите, что 1) если волшебник может каждый остров сделать счастливым, то это условие должно быть выполнено (ваше условие является необходимым), а также что 2) если ваше условие оказалось выполнено, то волшебник может сделать каждый остров счастливым (Ваше условие является достаточным).
б) (6 баллов) Теперь предположим, что волшебника нет, но острова могут обмениваться друг с другом. Каждый остров в рамках любой сделки с другим островом готов отдать свои товары только в обмен на такое же суммарное количество товаров (например, 5 яблок и 2 груши он готов обменять на 3 банана и 4 апельсина, 5 + 2 = 3 + 4). Запишите условие на dij, sij, при котором острова смогут устроить торговлю (последовательность обменов) так, чтобы каждый остров был в итоге счастливым. Докажите, что это условие является необходимым и достаточным.
в) (3 балла) Наконец, предположим, что каждый остров i в рамках любой сделки с другим островом готов отдать свои товары только в обмен на такое же суммарное количество товаров, в которых сам нуждается, то есть таких товаров j, что dij > sij. Является ли достаточным условие, которое вы получили в качестве ответа в пункте б), для того, чтобы острова смогли устроить торговлю так, чтобы каждый остров в итоге был счастливым?
а) Поскольку волшебник может свободно перераспределять все произведенные
товары, необходимо всего лишь, чтобы суммарно на всех островах оказалось произведено как минимум такое количество товаров каждого вида, в котором испытывают
потребность все острова суммарно. Иными словами, для всех j \in {1, 2,..., 2023} должно
быть выполнено неравенство:
s_{Aj} + s_{Bj} + \dots + s_{Gj} \geq d_{Aj} + d_{Bj} + \dots + d_{Gj}
В противном случае найдется такой товар, что суммарный объем его производства меньше суммарной потребности в нем, а значит удовлетворить потребности всех
островов в этом товаре путем перераспределения не удастся. Стало быть, это условие
действительно является необходимым.
Если 2023 неравенства выполнены, то волшебник может собрать все произведенные товары со всех островов и выдать острову i dij единиц товара j, тем самым закрыв его потребность в данном товаре. Это верно для всех i и для всех j, коль скоро суммарные потребности островов в каждом товаре не больше, чем суммарный объем производства каждого товара, а значит и достаточное условие выполнено. Остатки можно
распределить произвольным образом.
б) 2023 неравенства из предыдущего пункта все так же должны выполняться, потому что в противном случае хотя бы по одному товару суммарная потребность всех
островов превышала суммарный запас ресурсов, а значит потребности всех островов
в нем не смогли бы быть удовлетворены. Однако, одного этого условия теперь недостаточно.
Заметим, что в результате любого обмена суммарное количество товаров, которым
обладает участвующий в обмене остров, не изменяется, потому что обмен предполагает передачу и получение одинакового количества товаров. Стало быть, если после
обмена некоторый остров стал счастливым, то суммарный объем всех товаров в наличии у этого острова должен быть не меньше суммарной потребности этого острова
во всех товарах –– в противном случае острову не хватит товаров для удовлетворения
потребности в одном из ресурсов. Значит, чтобы все острова удовлетворили свои потребности во всех товарах, необходимо, чтобы для всех i \in {A, B, C, D, E, F, G} были
выполнены 7 неравенств:
s_{i1} + s_{i2} + \dots + s_{i2023} \geq d_{i1} + d_{i2} + \dots + d_{i2023}
Таким образом, получили систему из 2030 неравенств:
s_{Aj} + s_{Bj} + \dots + s_{Gj} \geq d_{Aj} + d_{Bj} + \dots + d_{Gj}
s_{i1} + s_{i2} + \dots + s_{i2023} \geq d_{i1} + d_{i2} + \dots + d_{i2023}
Докажем, что эта система и является искомым необходимым и достаточным условием.
Если не выполнено одно из первых 2023 неравенств, то потребность в некотором
товаре как минимум для одного из островов не сможет быть удовлетворена из-за
недопроизводства. Если не выполнено одно из последних 7 неравенств, то некоторому острову не хватит запаса ресурсов для покрытия своих нужд путем обмена. Таким
образом, приведенные 2030 неравенств являются необходимым условием.
Проверим достаточность. Пусть все 2030 неравенств выполнены. Алгоритм обменов, который позволит сделать все острова счастливыми, может быть таким. Рассмотрим остров A. Пусть у него не хватает нескольких товаров (если остров A не испытывает недостатка ни в одном из товаров, перейдем к острову B). Рассмотрим произвольный из недостающих товаров k. Из предположения следует, что в сумме у всех
остальных островов точно есть излишек товара k, способный покрыть дефицит острова A в нем. Кроме того, из предположения следует, что у острова A точно есть излишек
других товаров в объеме не меньшем, чем дефицит товара k. Это означает, что остров A может последовательно обменяться с другими островами так, чтобы покрыть
свой дефицит в товаре k, отдавая при этом товар, которого на острове A в излишке.
Проделаем эту же операцию со всеми остальными товарами, в которых у острова A наблюдается дефицит. После этого дефицит острова A будет закрыт. При этом у других
островов не возникает дополнительного дефицита ни по какому товару. Проделаем
эти же шаги для всех оставшихся островов, имеющих дефицит в некоторых товарах.
После этого все острова окажутся счастливыми.
в) Нет, это условие не является достаточным. Предположим, что острова C, D, E, F, G
не производят ни одного товара и не нуждаются ни в одном товаре (для них dij = sij =
0). Предположим, что остров A производит единицу первого товара и ничего больше,
а также не нуждается в потреблении ни одного товара. Наконец, предположим, что
остров B нуждается только в единице первого товара и производит только единицу
второго товара. Формально, среди всех dij только dB1 = 1, и все остальные равны нулю,
а среди всех sij только sA1 = sB2 = 1, и все остальные равны нулю. Тогда единственным нуждающимся островом оказывается остров B, чью потребность может закрыть
лишь остров A, который, однако, не заинтересован в этом, потому что он уже счастливый. Тем не менее, в условиях пункта б) обмен бы состоялся, поскольку остров A мог бы обменять единицу первого товара на единицу второго товара от острова B,
и все острова оказались бы счастливыми.