Optimal Apple Eating Strategy

106 Views Asked by At

You hate apples. As a result, you have angered the apple king and are being punished. You will have to eat $n$ apples before the apple king is willing to let you leave. The apples are marked from $1$ to $n$ and you have to eat them sequentially starting with $1$ and ending with $n$.

For every apple you eat, you do not know how long it is going to take you to eat it or how much weight it is going to add to your stomach until you have actually eaten the apple. Let $a_i$ denote how long it takes you to eat apple $i$ and $b_i$ denote how much weight apple $i$ is going to add to your stomach. You learn the true value of $a_i$ and $b_i$ as soon as you finish eating apple $i$. Once you start eating an apple, you have to finish it before you can do anything else. $a_i$s are i.i.d. with CDF $F$ while $b_i$s are i.i.d. with CDF $G$. $F$ and $G$ are known to you.

Apple king is a merciful king, each time after you finish eating an apple, he allows you a chance to have a digestion break. You can rest for as long as you want. If you choose not to rest, you can move directly onto the next apple. Let $r_i$ denote the duration of your rest after finish eating apple $i$. The more apples you have in your stomach, the worse you feel. For every apple you eat without taking a digestion break, you will feel pain at a faster rate. For example, if you choose to eat apple $2$ right after apple $1$, the pain for apple $1$ is $b_1$ while the pain for apple $2$ is $b_1+b_2$. If you choose to rest for $r_1$ before eating apple $2$, the pain for apple $2$ is $b_1+b_2-r_1$. So the pain for eating apple $k$ is $\sum_{i=1}^{k} b_i-\sum_{i=1}^{k-1} r_i$. Pain is non-negative, so the maximum $r_i$ you can pick every time resets pain to zero.

Your objective is to get out as fast as you can with minimum discomfort. That is you are trying to minimize $(\sum_{i=1}^{n} a_i+\sum_{i=1}^{n-1} r_i)+\sum_{k=1}^{n}(\sum_{i=1}^{k} b_i-\sum_{i=1}^{k-1} r_i)$ by choosing each $r_i$.

What is your optimal strategy here and why?

There is also an extension of the problem where the objective function becomes $\alpha(\sum_{i=1}^{n} a_i+\sum_{i=1}^{n-1} r_i)+\beta\sum_{k=1}^{n}(\sum_{i=1}^{k} b_i-\sum_{i=1}^{k-1} r_i)$. $α$ and $β$ are known and both greater than $0$.