Задача про банкира, отмывающего грязные купюры

[Nekrasov]

Представьте себе, дорогой читатель, что вы банкир, занимающийся отмыванием грязных денег, и завтра ждёте важного клиента, которому вы должны выдать круглую или не очень круглую, но заранее вам неизвестную сумму от 1 до 1 000 000 000 у. е. Чтобы не пачкать руки о грязные деньги, вы заранее дали указание своим кассирам заготовить некоторое количество конвертов с деньгами, на которых написаны содержащиеся в них суммы, и собираетесь просто отдать клиенту один или несколько конвертов, в которых и будет содержаться требуемая им сумма. Какое наименьшее количество конвертов необходимо иметь?Конечно, можно просто заготовить конверты со всеми суммами от 1 до 1 000 000 000. Но где взять столько денег на конверты?
1.А какова будет в этом случае полная сумма во всех конвертах? Попробуйте оценить также массу бумаги, предполагая, что использованы не более чем сотенные купюры

Сумму $S$ вычислим с помощью формулы суммы арифметической прогрессии:
$\frac{(10^9+1)\cdot10^9}{2}$ у.е.. Со вторым вопросом у меня затруднения. Правильно ли я понимаю, что использованы 100 купюр ценностью от 1 у.е. до 100 у.е.? Может, это неважно, а важно только то, что ценность купюр не больше 100 у.е.? Не понимаю, как двигаться в обоих случаях дальше. В первом случае мелькнула идея записать сумму $S$ в системе счисления с основанием 100, но возникли сомнения. Пожалуйста, подскажите, как подобраться к оценке массы купюр.

[waxtep]

Nekrasov, а ответ на самый первый вопрос (о наименьшем количестве конвертов) вам понятен?

[Nekrasov]

waxtep, да, но те результаты не применить для решения вопроса с массой

[Someone]

Я Вам подскажу идею, но оптимальное решение ищите сами.
Например, мы можем подготовить $10$ конвертов по $1$ у.е., $9$ конвертов по $10$ у.е., $9$ конвертов по $100$ у.е, …, $9$ конвертов по $100\,000\,000$ у.е., а всего — $82$ конверта.

[manul91]

Someone
А как доказать, что меньше чем 30-ти конвертов не получится? (т.е. что этот метод и даст наименьшее решение).
Как бы интуитивно ясно что так и должно быть, но непонятно как доказать что нельзя еще меньше...

[waxtep]

Nekrasov в сообщении #1456769 писал(а):

waxtep, да, но те результаты не применить для решения вопроса с массой

Хорошо. Для ответа на вопрос, который вас интересует, видимо, понадобится предположить, что все номиналы купюр от $1$ до $100$ у.е. разрешены, поскольку в условии задачи не оговорено обратного. Если какие-то номиналы все же запрещены, потребное количество купюр, конечно, окажется больше: вместо того, чтобы просто взять купюру номиналом $47$ у.е. эту сумму придется как-то сложить из купюр разрешенных номиналов, например $25+10+10+2$ у.е.
Вот в предположении, что доступны все номиналы от $1$ до $100$, можете посчитать количество купюр аналогично тому, как вы посчитали общую сумму?

-- 22.04.2020, 00:49 --

manul91, так а ведь $2^{29}<10^9$ и...

[manul91]

waxtep в сообщении #1456780 писал(а):

manul91, так а ведь $2^{29}<10^9$ и...

Это вроде не доказывает, что каким-то "другим" (неизвестным еще) способом (распределения денег в конвертов) нельзя и еще меньше... Или если и доказывает, мне не понятно почему

[Someone]

manul91

manul91 в сообщении #1456786 писал(а):

Или если и доказывает, мне не понятно почему

А сколько различных сумм, самое большее, можно составить, имея $29$ "монет"? Имея в виду, что число различных сумм, включая $0$, не превосходит числа подмножеств нашего множества "монет"?

[manul91]

Someone в сообщении #1456792 писал(а):

Имея в виду, что число различных сумм, включая $0$, не превосходит числа подмножеств нашего множества "монет"?

Так... Имея $n$ конвертов (с какими-то количествами денег в каждом) - из их подмножеств мы можем образовать не более чем $2^n$ различных сумм... (а возможно меньше различных сумм, если некоторые из этих сумм - при разных подмножеств конвертов - оказываются одинаковыми)...
При данном "методе" - достигается предел - при выборе разных подмножеств конвертов - соответные суммы всегда разные...
С 29-ти конвертов мы получим не более чем $2^{29}$ различных сумм (что меньше чем $10^9$ различных сумм, которые нам нужны)
Что-то я затормозил - спасибо!

[Nekrasov]

waxtep, придумал. Сначала посчитаем все купюры ценностью от 1 у.е. до 99 у.е., в каждой сотне их будет 99 штук, а количество сотен легко подсчитать. Получим

$$\frac{99\cdot10^9}{10^2}=99\cdot10^7$$

купюр. Далее, займёмся сотенными купюрами. В промежутке от 100 у.е. до 199 у.е. содержится 100 сотенных купюр. Таким образом, подсчитаем все сотенные купюры, которые нужны, чтобы составить числа от 100 до $10^9-1$. К ним прибавляем сотенные купюры, составляющие в сумме миллиард.
$10^2\cdot(1+2+3+...+(10^7-1))+10^7=4,9999995\cdot10^{15}$. Допустим, что все купюры одинаковой массы 1 г. Далее, сложив всё это хозяйство, можно оценить массу, если я всё правильно подсчитал. Проверьте меня, пожалуйста, может быть где-то не так рассуждаю.

-- 22.04.2020, 20:10 --

Someone, спасибо, но я интересовался этим вопросом: "Попробуйте оценить также массу бумаги, предполагая, что использованы не более чем сотенные купюры." Я плохо выделил, видимо, в теме вопрос. Вроде бы уже решил, проверьте, если несложно, не наврал ли я где.

[waxtep]

Nekrasov в сообщении #1457122 писал(а):

Проверьте меня, пожалуйста, может быть где-то не так рассуждаю.

Кажется, можно проще, попробуйте: в первых ста конвертах с суммами от $1$ до $100$ у.е. - по одной купюре, в следующих ста конвертах с суммами от $101$ до $200$ - по две и т.д. А с этим же уже очень легко расправиться, аналогично тому, как вы общую денежную сумму посчитали...

[Nekrasov]

waxtep, в самом деле, почему-то не заметил самый простой и естественный способ, сошлось с моими предыдущими расчётами, спасибо за помощь!