|
|
Re: Recursion Problem
Posted:
Nov 17, 2011 9:52 AM
|
|
On Nov 17, 4:13 am, William Elliot <ma...@rdrop.com> wrote:
> > Suppose we have a container of M&Ms.
> > Each year, I add some amount of M&Ms to my container.
>
> Including possibly zero M&M's?
No: the input each year is always positive...
>
> > For year i, let's call the input A_i. The input will be known for each
> > year (think of it as a given data value).
> > Each year, I take the *same* amount of M&M's out, which I'll denote as
> > B (think of this as a parameter).
> > So the net amount of M&Ms in yr i that I add to my container = F_i =
> > A_i - B
>
> That's a rather risque expression: So the net amount of M&Ms in your eye
> that I add to my container = F_i = A_i - B.
I think I missed a joke, but that's OK. Anyhow, yes the net amt of
M&Ms = A_i-B (realizing that when we say "add to the container", that
A_i-B could be negative)>
>
> > The question is this:
> > "If I know the influxes for each year and start out with no deficit
> > what is the maximum fixed amount of M&Ms (i.e. the maximum value for
> > B) I can take out so at the end of n years, I will have no deficit?"
>
> min{ a1, a2,.. a_n }
>
I assume the A's are capital. I know this is not the answer though, as
I can construct a counter-example (in fact "to" problem given is one
such CE)
> > Not an easy problem, and I don't think it probably has a "nice"
> > solution, but just thought I would see if anyone had a better thought.
>
> It's made messy by the results depending not only
> on the values of the a's but also on their order.
YES! You can take that same toy problem, rearrange them and get a
different answer. One thing I believe is true is that Average(A_i) is
an upper bound on the value of the soln for B.
|
|
