|
Чичиков и Ноздрев играют в игру. Ноздрев раскладыает 1001 орех по 3 коробочкам. Чичиков называет целое число $%N$% от 1 до 1001. Ноздрев перекладывает несколько орехов в из одной коробочки в другую или в четвертую коробочку(в начале пустую), так, чтобы предъявить Чичикову одну или несколько коробочек, суммарное число орехов в которых равно $%N$% и отдает Чичикову столько мертвых душ, сколько орехов он переложил. Какое наибольшее число душ может гарантировать себе Ноздрев при любых действиях Чичикова? задан 22 Окт '12 19:21 
dmg3 |
|
Правильный ответ: $%m=71$%, решение: $%143, 286, 572$%. Пусть нам надо построить число $%k$%. Выберем подмножество коробочек, теперь ответ равен расстоянию от суммы орехов в выбранных коробочках до $%k$%. Очевидно, что для каждого $%k$% есть свой набор коробочек, также очевидно, что набор коробочек не может обслужить больше, чем $%2m+1$% чисел. Кроме того, набор из последней коробочки обслуживает только $%m$% чисел(т.к. числа положительны), т.к. в нем $%0$% элементов, наборы, включающие $%0$% ничем не отличаются от наборов, не включающих $%0$%, наборы, включающие первые $%3$% тоже обсшуживают максимум $%m+1$% число (т.к. числа меньше $%1001$%). Суммируя вышесказанное $%m+6(2m+1)+m+1=7(2m+1)\ge 1001$%, откуда $%m\ge71$%. Теперь разделим числа от 1 до 1001 на соответствующие 8 отрезков, тогда мы должны уметь выбирать коробочки так, чтобы попадать в центр любого некрайнего отрезка (для крайних все очевидно), т.е. нам нужно уметь делать суммы $%(2m+1)\cdot k$% для $%k\in[0,7]$%. Для этой цели отлично подходят числа $%(2m+1), 2(2m+1), 4(2m+1)$%. P.S. Программа, перебирающая все возможные способы раскидать по коробочкам. отвечен 4 Ноя '12 3:36 
freopen |
|
Первая оценка. Из исходной расстановки, перекладывая ровно k орехов, можно получить $%3\cdot 3 = 9$% новых. Вернее, не более 9 (некоторые могут совпадать по составу). Имея 4 коробочки, из них можно выбрать не более $%2^4 - 1 = 15$% наборов (пустой набор нам не подходит). Значит, из заданной раскладки орехов, перекладывая от 1 до $%m$% орехов, можно получить не более $%9\cdot 15 \cdot m$% наборов. Но Чичиков может выбрать 1001 вариант, значит, $%135m \ge 1001$%, откуда $%m\ge 8$%. Теперь надо искать начальную раскладку, которая дает столько разных вариантов. Но это сомнительно, по-моему, оценка переложенных орехов занижена... отвечен 22 Окт '12 23:57 
DocentI Это кошмар, как грубо. На самом деле у нас есть только два вида перекладывания камней: в любую выбранную из максимальной невыбранной и в любую невыбранную из максимальной выбранной. Тогда 30m>=1001 и m>=33, что уже что-то.
(4 Ноя '12 3:25)
freopen
А зачем минус ставить? Я же не утверждаю, что это решение. Как оценка это верно.
(4 Ноя '12 10:50)
DocentI
Ну еще можно сказать, что ответ больше нуля. Просто как-то совсем бесполезная оценка. Минус убрал.
(4 Ноя '12 17:55)
freopen
|
Условие не очень понятно. Что значит "гарантировать наибольшее число душ"? Что надо делать с переложенными орехами - минимизировать (как я поняла), или максимизировать? Если Ноздрев гарантирует души себе (т.е. считаются не отданные), то надо знать, сколько их было: информация, с точки зрения математики, не нужная.