Питер Пен
Свой человек
Offline
Сообщений: 335
СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117
|
|
� Ответ #3 : Октябрь 19, 2013, 19:32:40 � |
|
"Добро пожаловать на борт А330-300! Извините, что мы без одного кресла при стандартной комплектации!"
Итак, поскольку по условию задачи разница между средним арифметическим значением номеров мест, занимаемых пассажирами по факту, и номеров мест, указанных у них в билетах, для любой группы пассажиров в 100 чел. должна отличаться более чем на 1, то сами суммы этих номеров для такой группы должны отличаться более чем на 100 (1*100 чел.), т.е. min на 101. Очевидно, что какой бы ни была путаница, разница между суммой номеров мест по факту и билетам в отношении всего множества (кол-ва пассажиров) будет равна 0. Эта разница (0) является суммой отрицательных и положительных чисел, количество которых – есть число пассажиров (т.е. все множество). Так как эта задача на экстремум, то ее решению должен удовлетворять ответ, при котором таких чисел (положительных и отрицательных) будет min. Быстрее всего получить нужный результат (т.е. min количество отрицательных и положительных числе) можно при условии, когда имеется max диапазон разницы между отрицательным и положительным числом. Он достигается при (Бn – Ф1) > 202 и при k (величина сдвига) > 1, где Б1, Б2…Бn – места по билетам, а Ф1, Ф2…Фn – места по факту.
Поясню все это на примере.
Допустим, n=101 (т.е. в самолете 101 место) и k=1 (все сдвинулись на 1 место), то (Б1-Ф2)+(Б2-Ф3)…+(Б100-Ф101)=-100, а Б101-Ф1=100. То есть у нас получилось 100 отрицательных разниц (-1) и 1 положительная разница (+100), где 100 чел.*(-1)+1 чел.*100 = 0. Приведенный пример доказывает, что образуется группа из 100 чел., где у каждого разница между номером места по билету (Б) и по факту (Ф) равна 1, а, значит, и разница в их среднем арифметическом значении для этой группы будет также равна 1. Если же группу создать с положительной разницей, т.е. взять 1 чел. с разницей (+100) и 99 чел. с разницей (-1), то общая сумма разницы (а, следовательно, и среднее арифметическое значение) будет еще меньше: 1чел.*(+100)+99чел.*(-1)=1 (среднее арифметическое значение = 0,01 (1/100)). Отсюда следующие выводы. В рассматриваемом множестве не должно быть 100 чел. с отрицательной разницей (Б-Ф) = (-1) – эта разница должна составлять (-99)+(-2), т.е. (-101) или быть еще меньше. Тогда, чтобы смогла также образоваться группа и из 99 отрицательных чисел и 1 положительного числа, необходимо, чтобы это положительное число было бы, как min, = 202 (101+|-101|). А, раз так, то кол-во отрицательных разниц ((Б-Ф) = (-2)) будет больше 100 и тогда положительное число должно быть уже не 202, а 299 (101+|(-2)*99чел.|). В связи с чем, минимальное количество пассажирских мест в самолете должно быть 301 (299 + 2), где 2- это k (величина сдвига).
|