Чичиков и Ноздрев играют в игру. Ноздрев раскладыает 1001 орех по 3 коробочкам. Чичиков называет целое число $%N$% от 1 до 1001. Ноздрев перекладывает несколько орехов в из одной коробочки в другую или в четвертую коробочку(в начале пустую), так, чтобы предъявить Чичикову одну или несколько коробочек, суммарное число орехов в которых равно $%N$% и отдает Чичикову столько мертвых душ, сколько орехов он переложил. Какое наибольшее число душ может гарантировать себе Ноздрев при любых действиях Чичикова?

задан 22 Окт '12 19:21

Условие не очень понятно. Что значит "гарантировать наибольшее число душ"? Что надо делать с переложенными орехами - минимизировать (как я поняла), или максимизировать? Если Ноздрев гарантирует души себе (т.е. считаются не отданные), то надо знать, сколько их было: информация, с точки зрения математики, не нужная.

(22 Окт '12 23:35) DocentI
10|600 символов нужно символов осталось
0

Правильный ответ: $%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

изменен 4 Ноя '12 3:41

10|600 символов нужно символов осталось
0

Первая оценка. Из исходной расстановки, перекладывая ровно 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

Это кошмар, как грубо. На самом деле у нас есть только два вида перекладывания камней: в любую выбранную из максимальной невыбранной и в любую невыбранную из максимальной выбранной. Тогда 30m>=1001 и m>=33, что уже что-то.

(4 Ноя '12 3:25) freopen

А зачем минус ставить? Я же не утверждаю, что это решение. Как оценка это верно.

(4 Ноя '12 10:50) DocentI

Ну еще можно сказать, что ответ больше нуля. Просто как-то совсем бесполезная оценка. Минус убрал.

(4 Ноя '12 17:55) freopen
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×78
×59

задан
22 Окт '12 19:21

показан
1047 раз

обновлен
4 Ноя '12 17:55

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru