1) в итоге все коробки должны иметь разную массу;
2) чем тяжелее коробка, тем меньшее количество шариков в ней должно находиться.
Можно ли это сделать? И если можно, то как?
update
Первый - Дмитрий.Ответ
Нельзя.
Предположим, что выполнить условия можно. Сумма масс всех шариков равна 5050. Масса самой тяжёлой коробки должна быть больше, чем среднее арифметическое масс всех коробок, то есть больше, чем 505 (веса коробок не учитываем). Так как шарика с массой более 100 грамм нет, то в самой тяжёлой коробке должно быть не меньше 6 шариков. Следовательно, общее количество шариков должно быть не меньше, чем 6+7+8+...+15=105. Но это противоречит условию - в наборе всего 100 шариков.
Предположим, что выполнить условия можно. Сумма масс всех шариков равна 5050. Масса самой тяжёлой коробки должна быть больше, чем среднее арифметическое масс всех коробок, то есть больше, чем 505 (веса коробок не учитываем). Так как шарика с массой более 100 грамм нет, то в самой тяжёлой коробке должно быть не меньше 6 шариков. Следовательно, общее количество шариков должно быть не меньше, чем 6+7+8+...+15=105. Но это противоречит условию - в наборе всего 100 шариков.
Невозможно.
ОтветитьУдалитьЧтобы все коробки имели разный вес и разное количество шариков, в самой тяжелой коробке должно быть не более 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 (начиная с самых тяжелых, если перебор - убираем последний положенный и начинаем класть самые легкие, пока массу нельзя будет "подравнять" положением одного шара), и так далее.