Agnishom's original writeup:

An ant climbs down an ant-hill, going right or left as he moves down. In each cave, there are a number of sugar cubes available as indicated in the diagram.

Naturally, every ant wants to find the path from the top hill to one of the bottom hill along which he could collect the maximal number of sugar cubes.

Proofreader's edits:

An ant is climbing down an ant-hill, going right or left at each level. In each circular cave, there are a number of sugar cubes available as indicated by the numbers in the circle.

Naturally, every ant wants to find the downward path along which they could collect the maximal number of sugar cubes.

at every step, going to the cave that has the larger of the two sugar cubes will eventually give the largest number of sugar cubes he could possibly get.

Calvin's edits:

An ant climbing down an ant-hill can choose to go either down and to the right or down and to the left at each level until it reaches the bottom of the hill. And at each junction, the ant collects a number of sugar grains indicated by the numbers in the circle.

Being greedy, this ant believes that if it always moves down towards the larger of the two values directly below, it will be able to collect the largest number of sugar grains overall. **With the hill as shown above, is this greedy strategy optimal for collecting sugar?**

## Comments

Sort by:

TopNewestYesterday, you suspected that I had a "trick" up my sleeve... well, that was my trick (in the case \(n=3\)) ;) – Otto Bretscher · 1 year, 10 months ago

Log in to reply

– Pi Han Goh · 1 year, 10 months ago

haha! I thought you had ANOTHER trick up your sleeves! I was persistent in solving it my way but it's over 4 pages long and the equations are enormous so I gave up half way through.Log in to reply

Great observation! It's easy to see why this would be true. Let \(T_n(f(x))\) be the Taylor polynomial of \(f(x)\) at \(x=0\).

If \(T_n(f(x))=T_n(g(x))\) for two functions, then \(T_{n+1}(\ln(x+1)f(x))=T_{n+1}(\ln(x+1)g(x))\); since \(\ln(x+1)\) does not have a constant term, the degree gets "pushed up". This in turn implies that \(T_{n+1}((x+1)^{f(x)})=T_{n+1}((x+1)^{g(x)})\), by exponentiation.

Now \(T_1(x+1)=T_1\left((x+1)^{x+1}\right)\), by inspection ; applying the above observation \(n-1\) times, we find that \(T_n\left(^n(x+1)\right)=T_{n}\left(^{n+1}(x+1)\right)\) and therefore \(T_n\left(^n(x+1)\right)=T_{n}\left(^m(x+1)\right)\) for all \(m\geq{n}\) .

Let \(D_n(f(x))\) be the nth derivative of \(f(x)\) at \(x=0\). Since \(D_n\) is determined by \(T_n\), we have \(D_n\left(^n(x+1)\right)=D_{n}\left(^m(x+1)\right)\) for all \(m\geq{n}\) .

In particular, \(D_3\left(^7(x+1)\right)=D_{3}\left(^3(x+1)\right)=9\), as we saw in Pi Han Goh's earlier problem. – Otto Bretscher · 1 year, 10 months ago

Log in to reply

You take the words out of my mouth. Haha, just kidding. Nice! I didn't thought it was that simple. THANKYOU – Pi Han Goh · 1 year, 10 months ago

Log in to reply

Using our earlier work, the only "new" computation you need is \(T_3\left(\ln(x+1)(x+1)^{(x+1)^{x+1}}\right)=x+\frac{x^2}{2}+\frac{5x^3}{6}\) . You realize that this is the same as \(T_3\left(\ln(x+1)(x+1)^{x+1}\right)\) ... done!

Thank you so much for the fruitful cooperation! I will use these kinds of problems in the Final Exam in Calculus at Harvard this summer... I will let you know about the results ;) – Otto Bretscher · 1 year, 10 months ago

Log in to reply

@Pi Han Goh so it would be fine right?? If I do the same. – Aditya Kumar · 1 year, 8 months ago

Log in to reply

Pi Han Goh please send me a message with an answer to my geometric problem please. – Fawzy Hamdy · 1 year, 10 months ago

Log in to reply