1) в итоге все коробки должны иметь разную массу;
2) чем тяжелее коробка, тем меньшее количество шариков в ней должно находиться.
Можно ли это сделать? И если можно, то как?
update
Первый - Дмитрий.Ответ
четверг, 29 января 2015 г.
Расклад
1) в итоге все коробки должны иметь разную массу;
2) чем тяжелее коробка, тем меньшее количество шариков в ней должно находиться.
Можно ли это сделать? И если можно, то как?
Ответ
Подписаться на:
Комментарии к сообщению (Atom)
Невозможно.
ОтветитьУдалитьЧтобы все коробки имели разный вес и разное количество шариков, в самой тяжелой коробке должно быть не более 5 шаров и вес ее должен быть не менее 510 грамм. А максимальный вес пяти шариков - 490 грамм.
Задачу можно и обобщить - есть N шаров с массами от 1 до N грамм (общая масса W=N(N+1)/2 - это еще пригодится), и их надо разложить по K коробкам с выполнением этих условий.
ОтветитьУдалитьНу, во-первых, понятно, что шаров не может быть меньше, чем K(K+1)/2 (иначе принцип Дирихле по количеству шаров в коробке). Во-вторых, чтобы еще учесть и уменьшение массы при увеличении заполнения коробки, N должно быть еще больше.
Формально можно я решал так: пусть X - количество шаров в самой тяжелой коробке. Тогда в следующей в порядке убывания массы по меньшей мере X+1 шар, и так далее, и их сумма не превышает, конечно, N. Так можно определить наибольшее X для данной пары N и K из неравенства KX+K(K-1)/2<=N, X<=N/K-(K-1)/2
Выражение получается, в общем случае, дробное, поэтому надо еще и округлять в меньшую сторону. (для 100-10 max(X)=5, например)
Потом, зная, что в этой коробке X шаров, легко посчитать наибольшую достижимую массу всей коробки (она равна M=N+(N-1)+...(N-X+1)). Соответственно, масса следующей коробки не более M-1, и так далее. Суммируя, получаем наибольшую массу всех коробок SM, которую теоретически можно достигнуть. То есть реальная масса не больше нее: W<=SM. Выражение представляет собой полином уже второго порядка? который я выписывать отдельно не стану (с первым коэффициентом =1), это полином меньше либо равен 0.
Решение этого неравенства - все X между корнями полинома включительно. Причем только целые X. Вместе с предыдущим условием мы получаем все допустимые X.
X, повторюсь, это количество шаров в самой тяжелой коробке.
Это можно считать и вручную, а можно составить программку, и увидеть, что появляются "острова". Допустим, в 10 коробок можно разложить 105 шаров или больше. Но еще есть и "остров" с 95 шарами.
P.S. Хотел добавить картинку с прямой ссылкой, но что-то хостинги тормозят, поэтому таким извратом: http://goo.gl/0Ro8J1
По горизонтали - N, по вертикали - K. Красный цвет - нет решения, белый цвет (и слабо видимая "-1") - при любом раскладе будут коробки с равным количеством шаров. Зеленый цвет - решение есть, число внутри - количество различных X.
P.P.S. Неизвестно, достаточно ли этого, чтобы шары можно было разложить реально. Но алгоритм простой: в коробку №1 кладем допустимое X самых тяжелых шаров. В коробку №2 - (X+1) шар с суммарной массой на 1 меньше, чем №1 (начиная с самых тяжелых, если перебор - убираем последний положенный и начинаем класть самые легкие, пока массу нельзя будет "подравнять" положением одного шара), и так далее.