2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Расположить денежную сумму по конвертам
Сообщение22.04.2013, 12:20 
Аватара пользователя
Как расположить по $n$ конвертам сумму в $F_{n+3}-2$ рублей так, чтобы любую меньшую сумму также можно было бы уплатить, не вскрывая конвертов?

Интуиция подсказывает, что в конверт под номером $k$ нужно положить $k+1$-ое число Фибоначчи.
Как это лучше доказывать? По индукции?
А единственный ли это способ? Можно ли доказать его единственность?

 
 
 
 Re: Расположить денежную сумму по конвертам
Сообщение22.04.2013, 16:21 
Доказывать, действительно, по индукции.

Способ, конечно же, не единственный.
Например, для 7 конвертов, можно как у Вас: 1+2+3+5+8+13+21, а можно один конверт оставить пустым и обойтись шестью. Например так: 1+2+3+7+13+27. (Есть и много других способов разложить 53 рубля всего лишь по 6 конвертам, с выполнением условия задачи.)

 
 
 
 Re: Расположить денежную сумму по конвертам
Сообщение22.04.2013, 16:26 
Аватара пользователя
Доказательство там элементарное, например вот (абзац "Обоснование").
По поводу единственности...
Предлагаю такое разбиение: Для некоторого $p$ верно $2^p \leq  (F_{n+3}-2)< 2^{p+1}$, тогда разложим деньги по конвертам так: $1, 2, 4, 8, \dots, 2^{p-1}$, и ещё в один положим все деньги, что остались. Потребуется всего $p+1$ конвертов. Так как $p = n \cdot \log_{2}{\varphi} + o(n) = 0.7 n + o(n)< n$, то конвертов нам хватит за глаза. ($\varphi$ - золотое сечение, примерно 1.6, что меньше 2).

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group