Interview Question optimisation and probability I got this question during an interview which is quite interesting I think, I am in a museum, there are 100 rooms (numbered from 1 to 100) in this museum and each room has a picture in it. I go visit each room in the increasing order, but I can't go back in a room that I have already visited. When I am in a room I can steal the picture, earn his value and I have to go out of the museum (meaning that I only can steal one picture and when I am in the room 100 I am forced to steal the picture) or I can leave the picture here and move to the other room. What is your strategy in order to optimize the money you will earn.
Hint : I have assume that the price of the picture follows a uniform distribution from 1 to to 100. Enjoy
 A: If the pictures were valued continuously uniformly from $0$ to $100$, then you could take the approach:


*

*If you are in the last room, take the picture. It has an expected value of $50$. Call this $E_{100}$

*If you are in an earlier room, take the picture if its value is greater than the expected value of moving to the next room.  So if the expected value of the being in the next room is $E_{n+1}$ then the probability of taking the picture in room $n$ is $\frac{100-E_{n+1}}{100}$ and its conditional expected value would be  $\frac{100+E_{n+1}}{2}$, so the expected value of being in room $n$ would be  $E_{n}=\dfrac{100^2+ E_{n+1}^2}{200}.$


So you can calculate the expected value recursively.  If you did, the expected value of being in the first room seems to be  about $98.12$.
But your question seems to suggest the values are discrete integers from $1$ to $100$.  So it gets a little more complicated.


*

*If you are in the last room, take the picture. It has an expected value of $50.5$. Call this $D_{100}$

*If you are in an earlier room, take the picture if its value is greater than the expected value of moving to the next room.  So if the expected value of the being in the next room is $D_{n+1}$ then the probability of taking the picture in room $n$ is $\frac{100-\lfloor D_{n+1}\rfloor}{100}$ and its conditional expected value would be  $\frac{100+\lfloor D_{n+1}\rfloor+1}{2}$, so the expected value of being in room $n$ would be  $D_{n}=\dfrac{10100+ \lfloor D_{n+1}\rfloor(2D_{n+1}-\lfloor D_{n+1}\rfloor-1)}{200}.$


This time the expected value of being in the first room seems to be about $98.61$.
