The cities of countries $A$ and $B$ are marked on the map, which has the form of a square with vertices at points $(0, 0)$ , $ (0, 1)$ , $(1, 1)$ , $(1, 0)$ of the plane. According to the trade agreement, country $A$ must ensure the delivery of $n$ kg of wheat to $n$ cities of country $B$, located at the points of the square with coordinates $y_1,..., y_n$, $1$ kg each city. Currently, $n$ kg of wheat are distributed among $n$ cities of country $A$, located at the points of the square with coordinates $x_1,... , x_n$, $1$ kg in each city. From each city of country $A$ to each city of the country $A$ any amount of wheat can be transported (of course, not more than $1$ kg). Transportation cost is for $t$ kg of wheat from a city with coordinates $x_i$ to a city with coordinates $y_j$ is equal to $tl_{ij}$, where $l_{ij }$is the length of the segment connecting the points $x_i$ and $y_j$. The government of country A is going to implement the optimal one (i,e. the cheapest) transportation plan. (a) Is it possible to implement the optimal transportation plan so that from each city of country $A$ to transport wheat only to one city of country $B$? (b) Will the response change if country $A$ is to deliver $n+1$ kg of wheat, in city $x_1$ is $2$ kg of wheat, and $2$ kg should be delivered to city $y_1$ (when for other cities the conditions remain the same)?
HIDE: original wording Мiста країн A та B позначенi на мапi, що має вигляд квадрату з вершинами в точках (0, 0), (0, 1), (1, 1), (1, 0) площини. Згiдно торгової угоди, країна A має забез- печити доставку n кг пшеницi в n мiст країни B, що розташованi в точках квадрату з координатами y1, . . . , yn, по 1 кг в кожне мiсто. Наразi n кг пшеницi розподiленi серед n мiст країни A, що розташованi в точках квадрату з координатами x1, . . . , xn, по 1 кг в кожному мiстi. З кожного мiста країни A в кожне мiсто країни B можна перевезти довiльну кiлькiсть пшеницi (звичайно, не бiльше 1 кг). Вартiсть переве- зення t кг пшеницi з мiста з координатами xi в мiсто з координатами yj дорiвнює tlij , де lij – довжина вiдрiзку, що сполучає точки xi та yj . Уряд країни A збирається реалiзувати оптимальний (тобто найдешевший) план перевезення. 1. Чи можна реалiзувати оптимальний план перевезення таким чином, щоби з кожного мiста країни A перевозити пшеницю тiльке в одне мiсто країни B? 2. Чи змiниться вiдповiдь, якщо країна A має забезпечити доставку n + 1 кг пше- ницi, в мiстi x1 знаходиться 2 кг пшеницi, i в мiсто y1 має бути доставлено 2 кг пшеницi (щодо iнших мiст умови лишаються такими ж)?