Optimization

[polerno]

Hey guys, I have the following question.
Imagine there is a certain amount of money which should be split among 100 brothers. The first brother gets 1/100 of the money, the second brother gets 2/100 of what remains after his first brother takes his share, the third brother gets 3/100 of what remains after his first and second brothers get their share and so on. Question is, who gets the most and how much? Could you solve this without brute force? I am sure you can get a general formula for how much n-th brother gets and then just differentiate it and equalize to 0 to get the max. However, I cannot find the general formula. Thank you in advance.

 

[lev888]

This is not an optimization problem. Optimization involves a function whose max or min you are trying to find. Don't see a function here.
You have a sum of a sequence: 1/100 + 2/100 + 3/100 + ... + k/100. You need to find k, such that the sum is less than or equal to 1 but for k+1 it's greater than 1. kth brother obviously gets the most. k+1 and the rest get 0. Nice way to split the money
1/100 + 2/100 + 3/100 + ... + k/100 = 1/100 * (1+2+3+...+k) =
Can you continue?

 

[polerno]

This is not an optimization problem. Optimization involves a function whose max or min you are trying to find. Don't see a function here.
You have a sum of a sequence: 1/100 + 2/100 + 3/100 + ... + k/100. You need to find k, such that the sum is less than or equal to 1 but for k+1 it's greater than 1. kth brother obviously gets the most. k+1 and the rest get 0. Nice way to split the money
1/100 + 2/100 + 3/100 + ... + k/100 = 1/100 * (1+2+3+...+k) =
Can you continue?

Hey, thanks for the answer. I think you misunderstood the task. The task says that the first brother gets 1/100, the second brother gets 2/100 of what remains after the first brother already took his share (that is (1-1/100)*(2/100), third gets 3/100 of what remains after the first two take their share that is (1-(1/100+1-1/100)*(2/100))*3/100 and so on.

 

[Harry_the_cat]

This is not an optimization problem. Optimization involves a function whose max or min you are trying to find. Don't see a function here.
You have a sum of a sequence: 1/100 + 2/100 + 3/100 + ... + k/100. You need to find k, such that the sum is less than or equal to 1 but for k+1 it's greater than 1. kth brother obviously gets the most. k+1 and the rest get 0. Nice way to split the money
1/100 + 2/100 + 3/100 + ... + k/100 = 1/100 * (1+2+3+...+k) =
Can you continue?

I think you have misinterpreted the problem lev888.
The first brother gets 1/100 of the money, the second brother gets 2/100 of what remains after his first brother takes his share,

 

[lev888]

I think you have misinterpreted the problem lev888.
The first brother gets 1/100 of the money, the second brother gets 2/100 of what remains after his first brother takes his share,

Thanks, you're right - missed the "what remains" part. Still doesn't look like optimization to me.

 

[lev888]

Found a solution online. The idea is to
1. Find the expression for how much n-th brother gets
2. Find the ratio between 2 consecutive brothers
3. The amount increases while the ratio is greater than 1. Find the last n before the ratio becomes less than 1.

 

[Dr.Peterson]

Hey guys, I have the following question.
Imagine there is a certain amount of money which should be split among 100 brothers. The first brother gets 1/100 of the money, the second brother gets 2/100 of what remains after his first brother takes his share, the third brother gets 3/100 of what remains after his first and second brothers get their share and so on. Question is, who gets the most and how much? Could you solve this without brute force? I am sure you can get a general formula for how much n-th brother gets and then just differentiate it and equalize to 0 to get the max. However, I cannot find the general formula. Thank you in advance.

You're looking for the maximum of a discrete function; so differentiation won't be applicable. But you may be able to do the discrete analogue of that.

You can easily find an expression for the amount remaining after the nth brother, and use that to find the amount each gets; this will involve factorials. Then you'll want to compare two successive brothers, either finding the difference (and looking for when that becomes negative), or finding the ratio (and looking for when that goes below 1).