Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the following recurrence relation, for a function $D(x,n)$, where x is a positive real number and n is a positive integer:

$$ D(x,1) = x $$

$$ D(x,n) = \min_{k=1..n-1}{D(xk/n,k)} \ \ \ \ [n>1] $$

This formula can be interpreted as describing a process of dividing a value of x to n people: if there is a single person ($n=1$), then he gets all of the value x, and if there are more people, they divide x in a proportional way.

By induction on n, it is possible to prove that:

$$ D(x,n) = x/n $$

PROOF: For $n=1$, this is given. Assume it is true for $1, 2, ... n-1$. Then:

$$ D(x,n) = \min_{k=1..n-1}{D(xk/n,k)} = \min_{k=1..n-1}{x/n} = x/n $$

Now consider a slight modification of the formula:

$$ E(x,1) = x $$

$$ E(x,2) = x/2 $$

$$ E(x,n) = \min_{k=2..n-1}{E(x(k-1)/n,k)} \ \ \ \ [n>2] $$

The modified version models division with loss - in each division process, we lose some value: we give to $k$ people, only $(k-1)/n$ of the original value. What is the solution to this formula?

share|improve this question
add comment

1 Answer

up vote -1 down vote accepted

By induction on n, it is possible to prove that, for $n \geq 2$:

$$ E(x,n) = x/n(n-1) $$

PROOF: For $n=2$, this is given. Assume it is true for $2, ... n-1$. Then:

$$ E(x,n) = \min_{k=2..n-1}{E(x(k-1)/n,k)} = \min_{k=2..n-1}{x/nk} = x/n(n-1) $$

This is interesting - even a small loss in the division process, leads to a large reduction of the value each person gets, from $O(1/n)$ to $O(1/n^2)$.

share|improve this answer
    
Why do you ask the question to answer it? Is there something else that you are getting at? –  Calvin Lin Jun 10 '13 at 5:22
    
In the hope of finding other people working on similar problems (mathematics of fair division). –  Erel Segal Halevi Jun 10 '13 at 6:05
    
Here is the actual question that I couldn't solve: math.stackexchange.com/questions/416734/… –  Erel Segal Halevi Jun 12 '13 at 9:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.