2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ @A.S. I do not think this is a "best or nothing" problem $\endgroup$
    – Henry
    Commented Dec 10, 2015 at 1:08
  • $\begingroup$ @Henry You are correct - I didn't pay enough attention. Another significant difference from the secretary assumed (in your solution - appropriately given the hint) independence of picture prices. $\endgroup$
    – A.S.
    Commented Dec 10, 2015 at 1:44
  • $\begingroup$ Assuming user164118 will find their answer (or rather NAN) deleted soon enough, and to avoid disturbing the mods for conversion to a comment, I'll just place it here: «The problem is also in the classic book "Fifty challenging problems in probability" by F. Mosteller». $\endgroup$
    – MickG
    Commented Dec 10, 2015 at 15:34
  • $\begingroup$ Don't steal! Why rob others of their enjoyment of the picture? $\endgroup$
    – paw88789
    Commented Dec 10, 2015 at 15:37

1 Answer 1

Reset to default
3
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ Congratulations Henry, I had this question, in a bank interview and manage to get the close formula but with some indications and starting with simple examples. They also ask why if i put two people in this museum they will pick two different pictures $\endgroup$
    – ashu24
    Commented Dec 10, 2015 at 3:09
  • $\begingroup$ @Henry, I agree with your reasoning, the two bullets. But in your argument, for this question, one should take the picture in the first room since it is close to the maximum 100 value ? this feels counter-intuitive. a little confused about "conditional expected value" and "expected value". $\endgroup$
    – lzstat
    Commented Dec 10, 2015 at 15:21
  • $\begingroup$ No: I am saying the expected value of being in the first room (i.e. breaking into the museum) is over $98$. You take the picture in the first room only if it is worth more than the expected value of the being in the second room (also over $98$, so the probability you take the first picture is lower than $2\%$) $\endgroup$
    – Henry
    Commented Dec 10, 2015 at 16:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .