gapeevadaria25
Рассмотрите сумму S=2^10*3+2^9*3^2+2^8*3^3+...+2*3^10. Ее можно иначе представить иначе S=2*3^10*((2/3)^9+(2/3)^8+(2/3)^7+...+1). Аналогично предыдущей задаче покажите, что это минимальная сумма. Рассмотрим упорядоченную по степеням (убывающим) двойки. Она начинается с 2^10*3^k. Тогда в ней есть слагаемое вида 3*2^n. Покажем, что сумму можно уменьшить, заменив эти слагаемые на 2^10*3 и 2^n*3^k. Действительно, 2^10*3^k+3*2^n -(2^n*3^k+2^10*3)= =2^n*3*(2^(10-n)*3^(k-1)+1-3^(k-1)-2^(10-n))= =2^n*3*(2^(10-n)-1)*(3^(k-1)-1)>=0. Далее действуем с 2^9*3^p. Например, для произвольной суммы S_1=2^10*3^7+2^9*3^5+2^8*3^4+2^7*3^6+2^6*3^2+2^5*3^3+ +2^4*3^10+2^3*3+2^2*3^8+2*3^9 Выбираем 2^10*3^7 и 2^3*3. Заменяем их на 2^10*3 и 2^3*3^7. S_2=2^10*3+2^9*3^5+2^8*3^4+2^7*3^6+2^6*3^2+2^5*3^3+2^4*3^10+ +2^3*3^7+2^2*3^8+2*3^9<S_1. Выбираем 2^9*3^5 и 2^6*3^2. Заменяем их на 2^9*3^2 и 2^6*3^5. S_3=2^10*3+2^9*3^2+2^8*3^4+2^7*3^6+2^6*3^5+2^5*3^3+2^4*3^10+ +2^3*3^7+2^2*3^8+2*3^9<S_2<S_1. Выбираем 2^8*3^4 и 2^5*3^3. Заменяем их на 2^8*3^3 и 2^5*3^4. И т.д.
Answers & Comments
Ее можно иначе представить иначе
S=2*3^10*((2/3)^9+(2/3)^8+(2/3)^7+...+1).
Аналогично предыдущей задаче покажите, что это минимальная сумма.
Рассмотрим упорядоченную по степеням (убывающим) двойки.
Она начинается с 2^10*3^k. Тогда в ней есть слагаемое вида 3*2^n.
Покажем, что сумму можно уменьшить, заменив эти слагаемые на 2^10*3 и 2^n*3^k.
Действительно,
2^10*3^k+3*2^n -(2^n*3^k+2^10*3)=
=2^n*3*(2^(10-n)*3^(k-1)+1-3^(k-1)-2^(10-n))=
=2^n*3*(2^(10-n)-1)*(3^(k-1)-1)>=0.
Далее действуем с 2^9*3^p.
Например, для произвольной суммы
S_1=2^10*3^7+2^9*3^5+2^8*3^4+2^7*3^6+2^6*3^2+2^5*3^3+
+2^4*3^10+2^3*3+2^2*3^8+2*3^9
Выбираем 2^10*3^7 и 2^3*3. Заменяем их на 2^10*3 и 2^3*3^7.
S_2=2^10*3+2^9*3^5+2^8*3^4+2^7*3^6+2^6*3^2+2^5*3^3+2^4*3^10+
+2^3*3^7+2^2*3^8+2*3^9<S_1.
Выбираем 2^9*3^5 и 2^6*3^2. Заменяем их на 2^9*3^2 и 2^6*3^5.
S_3=2^10*3+2^9*3^2+2^8*3^4+2^7*3^6+2^6*3^5+2^5*3^3+2^4*3^10+
+2^3*3^7+2^2*3^8+2*3^9<S_2<S_1.
Выбираем 2^8*3^4 и 2^5*3^3. Заменяем их на 2^8*3^3 и 2^5*3^4.
И т.д.