|
РЕШЕНИЕ ПЕРВОГО ВАРИАНТА ЗАДАЧИ Ф2857 (наш ответ – меньше, чем в "Кванте" №10 за прошлый год).
Рассмотрим сначала более простой случай – 4 путешественника с 3 велосипедами. Все путешественники и велосипеды должны прибыть в Борискино одновременно (иначе время, затраченное на перемещение всей группы, можно уменьшить). Время перемещения всей группы от Анискина до Борискина равно сумме времени (время первого путешественника плюс время второго путешественника плюс время третьего путешественника плюс время четвертого путешественника), деленной на четыре (складываются четыре равных слагаемых и полученная сумма делится на четыре – результат равен каждому одному слагаемому). Если на участке длиной n км на любой его части x путешественников будут перемещаться со скоростью 20 км/ч (1/3 км/мин), у путешественников – со скоростью 15 км/ч (1/4 км/мин) и z путешественников – со скоростью 5 км/ч (1/12 км/мин), то сумма времени на преодоление этого участка будет равна 3xn+4yn+12zn минут. Если все путешественники на этом участке будут перемещаться только вперед, то x+y+z=4; если некоторые путешественники будут перемещаться и назад (перемещаться с отрицательной скоростью), то х+у+z>4 (одни и те же путешественники тогда будут учтены более одного раза).
Если на каком-то участке длиной n км один путешественник будет идти пешком и трое ехать со скоростью 1/3 км/мин, то сумма времени будет равна 12n+3·3n=21n минут; если двое будут ехать со скоростью 1/4 км/мин и двое – со скоростью 1/3 км/мин, то сумма времени будет равна 2·4n+2·3n=14n минут. Каждый путешественник может проехать 20 км со скоростью 1/3 км/мин и 20 км – со скоростью 1/4 км/мин. График одного из таких возможных алгоритмов передвижения путешественников и велосипедов от Анискина до Борискина будет состоять из двух равных треугольников (первая цифра индекса вершин треугольников – количество 20-километровых участков, проеханных к этой вершине со скоростью 1/3 км/мин, вторая цифра – количество 20-километровых участков, проеханных со скоростью 1/4 км/мин) А00А10А01 и А10А01А11, составляющих параллелограмм А00А10А11А01. Координаты вершин (абсцисса –минуты, ордината – километры): А00(0;0(Анискино)), А10(60;20), А01(80;20), А11(140;40(Борискино)). Стороны треугольников со скоростью 1/3 км/мин (в скобках, как в "Кванте" №10, указано количество путешественников и велосипедов): А00А10(2/2) и А01А11(2/2). Стороны треугольников со скоростью 1/4 км/мин: А00А01(2/1) и А10А11(2/1). Сторона треугольников со скоростью 0 км/мин (горизонтальная): А10А01(0/1).
Сумма времени на преодоление участка длиной n км в первом варианте задачи не может быть меньше 4·3n+6·4n=36n минут (например, если хотя бы один из путешественников будет идти пешком, то даже при использовании 9 велосипедов эта сумма будет не меньше 12n+9·3n=39n минут). Такая минимальная сумма времени на преодоление всего расстояния от Анискина до Борискина (36·40=1440минут=24часа) достижима. (Заметим, что, если бы количество путешественников было бы не четным (как в рассматриваемых случаях – 4, 10), а нечетным (например, 3 путешественника с 2 велосипедами), то аналогичная минимальная сумма времени на преодоление всего расстояния от Анискина до Борискина была бы недостижима – хотя бы одному путешественнику пришлось бы часть пути идти пешком.) Пусть каждый путешественник проедет х км со скоростью 1/4 км/мин и 40–х км со скоростью 1/3 км/мин , а каждый велосипед проедет по 40 км. Составим уравнение по сумме проеханных расстояний: 10х/2+10(40–х)=7·40 ; х=24км (то есть 3/5 расстояния от Анискина до Борискина). Можно, например, разбить всё расстояние от Анискина до Борискина на 5 участков по 8 км , и каждый 8-километровый участок 6 путешественников проедут со скоростью 1/4 км/мин и 4 путешественника – со скоростью 1/3 км/мин , а каждый путешественник проедет три 8-километровых участка со скоростью 1/4 км/мин и два 8-километровых участка со скоростью 1/3 км/мин. 40 км вся группа преодолеет за 3·8·4+2·8·3=36·40/10=144 минуты, то есть за 2 часа 24 минуты.
ЗАМЕЧАНИЕ К РЕШЕНИЮ
Можно проиллюстрировать один из таких возможных алгоритмов передвижения путешественников и велосипедов графиком, состоящим из равных треугольников (первая цифра индекса вершин треугольников – количество 8-километровых участков, проеханных к этой вершине со скоростью 1/3 км/мин, вторая цифра – количество 8-километровых участков, проеханных со скоростью 1/4 км/мин) А00А10А01, А10А01А11, А01А11А02, А11А02А12, А11А21А12, А21А12А22, А12А22А13, А22А13А23, составляющих равные параллелограммы А00А10А12А02 и А11А21А23А13. Координаты вершин: А00(0;0(Анискино)), А10(24;8), А01(32;8), А11(56;16), А02(64;16), А21(80;24), А12(88;24), А22(112;32), А13(124;32), А23(144;40(Борискино)). Стороны треугольников со скоростью 1/3 км/мин : А00А10(4/4), А01А11(4/4), А11А21(2/2), А02А12(2/2), А12А22(4/4), А13А23(4/4). Стороны треугольников со скоростью 1/4 км/мин : А00А01(6/3), А10А11(4/2), А01А02(2/1), А11А12(6/3), А21А22(2/1), А12А13(4/2), А22А23(6/3). Стороны треугольников со скоростью 0 км/мин (горизонтальные): А10А01(0/2), А11А02(0/1), А21А12(0/1), А22А13(0/2).
А в движущейся (со скоростью 1/4 км/мин из Анискина в Борискино) системе отсчета путешественники будут перемещаться из начального пункта (прямая А00А02) в промежуточный пункт (прямая А10А13) и в конечный пункт (прямая А21А23), а велосипеды, когда на них нет седоков, будут перемещаться в обратном направлении (прямо как в Зазеркалье!).
РЕШЕНИЕ ВТОРОГО ВАРИАНТА ЗАДАЧИ
Рассмотрим сначала более простой случай – три путешественника с одним велосипедом. Если на каком-то участке длиной n км два путешественника будут идти пешком и один ехать со скоростью 1/3 км/мин, то сумма времени будет равна 2·12n+3n=27n минут; если один будет идти и двое ехать со скоростью 1/4 км/мин, то сумма времени будет равна 12n+2·4n=20n минут; но если разделить участок на три части так, что только на крайних частях будут идти по одному пешеходу, а по центральной части (длиной m км) сначала два путешественника проедут со скоростью 1/4 км/мин, затем один из них вернется с отрицательной скоростью –1/3 км/мин к началу центральной части и потом проедет вперед еще раз с подошедшим пешком к началу центральной части третьим путешественником, то сумма времени на центральной части будет равна только 4·4m+3m=19m минут. График одного из таких возможных алгоритмов передвижения путешественников и велосипедов от Анискина до Борискина будет состоять из двух равных треугольников (первая цифра индекса вершин треугольников – количество участков, проеханных к этой вершине со скоростью 1/4 км/мин, вторая цифра – количество участков, пройденных со скоростью 1/12 км/мин) А00А10А01 и А10А01А11, составляющих параллелограмм А00А10А11А01. Стороны треугольников со скоростью 1/4 км/мин: А00А10(2/2) и А01А11(2/2). Стороны треугольников со скоростью 1/12 км/мин: А00А01(1/0) и А10А11(1/0). Сторона треугольников с отрицательной скоростью –1/3 км/мин: А10А01(1/1).
График одного из возможных алгоритмов передвижения путешественников и велосипедов во втором варианте задачи будет состоять из равных треугольников (первая цифра индекса вершин треугольников – количество участков, проеханных к этой вершине со скоростью 1/4 км/мин, вторая цифра – количество участков, пройденных со скоростью 1/12 км/мин) А00А10А01, А10А01А11, А01А11А02, А11А02А12, А11А21А12, А21А12А22, А12А22А13, А22А13АА23, А22А32А23, А32А23А33, А23А33А24, А33А24А34, составляющих равные параллелограммы А00А10А12А02, А11А21А23А13, А22А32А34А24. Стороны треугольников со скоростью 1/12 км/мин: А00А01(4/0), А01А02(1/0), А10А11(3/0), А11А12(4/0), А12А13(2/0), А21А22(2/0), А22А23(4/0), А23А24(3/0), А32А33(1/0), А33А34(4/0). Стороны треугольников со скоростью 1/4 км/мин: А00А10(6/3), А01А11(6/3), А02А12(2/1), А11А21(4/2), А12А22(6/3), А13А23(4/2), А22А32(2/1), А23А33(6/3), А24А34(6/3). Стороны треугольников с отрицательной скоростью –1/3 км/ч: А10А01(3/3), А11А02(1/1), А21А12(2/2), А22А13(2/2), А32А23(1/1), А33А24(3/3).
Будем считать, что три путешественника совсем не будут идти пешком, а каждый из семи остальных путешественников проедет х км со скоростью 1/4 км/мин (а остальные 40–х км пройдет со скоростью 1/12 км/мин). Тогда каждый из трех не слезающих с велосипеда путешественников проедет 7х/3 км со скоростью 1/4 км/мин и 7х/3–40 км назад с отрицательной скоростью –1/3 км/мин. Приравнивая время, затраченное путешественником из одной группы и путешественником из другой группы, получим, что х=16+32/73 км. 40 км вся группа преодолеет за 4+52/73 часа (примерно за 4 часа 43 минуты).
ЗАМЕЧАНИЕ К РЕШЕНИЮ
Здесь также можно проиллюстрировать решение в движущейся (со скоростью 5 км/ч из Анискина в Борискино) системе отсчета: путешественники перемещаются из начального пункта (прямая А00А02) в первый промежуточный пункт (прямая А10А13), во второй промежуточный пункт (прямая А21А24) и в конечный пункт (прямая А32А34).
ЗАМЕЧАНИЯ К ЗАДАЧЕ
1. Можно исследовать и другие варианты задачи. ( – Можно. А зачем? – А вот зачем!!! (Штирлиц — Мюллеру, в анекдоте). ) Интересный (третий) вариант задачи получится, если исправных велосипедов больше 10 и все их надо переправить в Борискино. Например, если велосипедов 11, то можно каждому путешественнику пройти пешком назад 4 км: первому путешественнику – от отметки 4 км, второму – от отметки 8 км, ... , десятому – от отметки 40 км (промежуточные пункты, на которые перемещаются велосипеды, находятся на отметках 4, 8, 12, ... , 36 км); сумма времени на преодоление участка длиной n км тогда будет равна 11·3n+12n=45n минут. Можно также каждой паре путешественников проехать назад 8 км с отрицательной скоростью –1/4 км/мин : первому и второму – от отметки 8 км, третьему и четвертому – от отметки 16 км, ... , девятому и десятому – от отметки 40 км (промежуточные пункты, на которые перемещаются велосипеды, находятся на отметках 8, 16, 24 и 32 км); сумма времени на преодоление участка длиной n км тогда будет равна 12·3n+2·4n=44n минут. Как видим, в этом варианте задачи так же, как и в первом, пешком идти невыгодно.
2. Во всех трех вариантах задачи алгоритм построения графика возможного передвижения путешественников и велосипедов, по существу, один и тот же:
Проведем из начала отсчета прямую с минимальной (для данного варианта задачи) скоростью перемещения путешественников (в первом и втором вариантах) или велосипедов (в третьем варианте) (А00А02 (со скоростью 1/4 км/мин) в первом варианте; А00А02 (со скоростью 1/12 км/мин) во втором варианте; совпадающую с осью t (со скоростью 0 км/мин) в третьем варианте).
Параллельно этой прямой далее будем последовательно проводить через точки на оси l на одинаковом произвольном расстоянии новые прямые (А10А13 и А21А23 в первом варианте; А10А13, А21А24, А32А34 во втором варианте) (в рассмотренных движущихся системах отсчета эти прямые соответствуют промежуточным и конечным пунктам).
До тех пор, пока все путешественники и велосипеды не встретятся снова в одной точке, будем в каждой точке пересечения графика с этими параллельными прямыми повторять следующие действия:
сначала, если сзади (на предыдущей прямой) еще остались отставшие путешественники (в первом и втором вариантах) или велосипеды (в третьем варианте), проведем к ним отрезки (со скоростью 0 км/мин в первом варианте; –1/3 км/мин во втором варианте; –1/4 км/мин в третьем варианте) – так, чтобы подтянуть как можно больше отставших (используем "жадный" алгоритм);
потом, если из точки графика, где остановились путешественники и велосипеды, еще можно переправить кого-нибудь вперед (на следующую прямую), проведем отрезок (с указанием как можно большего количества путешественников (в первом и втором вариантах) или велосипедов (в третьем варианте) ) со скоростью 1/3 км/мин в первом и третьем вариантах и 1/4 км/мин во втором варианте – до пересечения со следующей прямой.
Когда все путешественники и велосипеды встретятся в одной точке графика (А23 в первом варианте; А34 во втором варианте), изменим масштаб так, чтобы ордината этой точки была равна расстоянию от Анискина до Борискина (40 км); теперь, с помощью уравнений, можно определить абсциссы и ординаты всех вершин графика (А01, А02, А10, ...).
|
