Waste less time on Facebook — follow Brilliant.
×

A Beautiful Problem

For some \(m\in\mathbb N\), there are \(2^m\) positive real numbers written on a board product of which is \(1\). At each step, we can choose two numbers \(a,b\) and replace both by \(a+b\). Prove that after \(2^{m-1}m\) steps the sum of all numbers on board will be at least \(4^m\).

Note by Jubayer Nirjhor
2 years, 2 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

How does this work? I'm confused by the #WishfulThinking tag. Is the question correct?

The sum of all the numbers is invariant and equal to \( 2^m \) and can never be \( 4^m \)

. Also, the number of numbers on the boards decreases by one every step. So after \( 2^m -1 \) steps, there should only be \( 1 \) number left on the board, after which no moves are possible. So you can't have \( 2^{m-1}*m \) moves since \( 2^{m-1}*m > 2^{m} -1 \) for \( m \geq 2 \) Siddhartha Srivastava · 2 years, 2 months ago

Log in to reply

@Siddhartha Srivastava We replace "both" of \(a,b\) by \(a+b\) so \((a,b)\) changes to \((a+b,a+b)\). Thus the number of terms remains same. Jubayer Nirjhor · 2 years, 2 months ago

Log in to reply

@Jubayer Nirjhor Ah. Okay. The question is still ambiguously worded though. A better wording would be " we replace each of \( a,b \) with \( (a+b) \)"

Anyways, the problem seems easy. Just apply the "step" to the two largest numbers which has a sum of \( \geq 2 \). Each "step" doubles the sum of the numbers. Initial sum = \( a+b \), final sum \( = 2(a+b) \). Applying it \( 2^{m-1}m \) times, the sum of those two numbers is now \( \geq 2^{2^{m-1}m} \). which is obviously greater than \( 2^{2m} \) Siddhartha Srivastava · 2 years, 2 months ago

Log in to reply

@Siddhartha Srivastava Not so fast! If initial terms are \(a_1,...,a_{2^m}\) then initial sum is \(a_1+\cdots+a_{2^m}\), while the sum after applying the step is \(2a_1+2a_2+a_3+\cdots+a_{2^m}\). So the sum is not doubled. Jubayer Nirjhor · 2 years, 2 months ago

Log in to reply

@Jubayer Nirjhor Sorry. I wasn't clear. I meant the sum of the largest two numbers when I said the sum will be doubled.

My solution was to just ignore the other numbers. Take only the two largest numbers. Their sum has to \( \geq 2 \). Now, one step doubles the sum of these two numbers. Applying the step \( 2^{m-1}*m \) times we see that the sum of these two numbers is now \( \geq 2^{2^{m-1}m} \). The sum of the numbers we ignored is \( \geq 0 \). so doesn't matter. Clearly, the sum of all the numbers is now \( 2^{2^{m-1}m} \) which is clearly greater than \( 2^{2m} \). Siddhartha Srivastava · 2 years, 2 months ago

Log in to reply

@Siddhartha Srivastava You don't decide which numbers to choose. The statement holds for any order. Jubayer Nirjhor · 2 years, 2 months ago

Log in to reply

@Jubayer Nirjhor Any order? No it doesn't. Take the case where \( m = 2 \). Take \( x_1, x_2, 2-x_1,2-x_2 \). Sum of these \( 2^2 \) numbers is \( 2^2 \)

Apply the step 4 times on \( x_1, x_2 \). Then the four numbers are \( 4(x_1+x_2),4(x_1+x_2), 2-x_1, 2-x_2 \).

Sum of these numbers is \( 4 + 7(x_1+x_2) \). If we take \( x_1,x_2 \) arbitrarily small, it will not be greater than \( 16 \). Siddhartha Srivastava · 2 years, 2 months ago

Log in to reply

@Siddhartha Srivastava Sorry. A change has been made. The initial product of the numbers is \(1\). No restriction on the sum. Jubayer Nirjhor · 2 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...