I work at a guffin factory. I manufacture guffins and have an unlimited access to guffin storage. I can fit up to 20 guffins in my bag, get them home from the factory and nobody will chase me.
You see, the factory wants to encourage brave and risky workers. When you are hired, they give you a random (evenly distributed) secret number N from 1 to 20 inclusively. If you ever steal N (or more) guffins a single day, the next day they will proclaim you fired. So, if I steal 20 I would be fired for sure. But even if I get only one, I can be fired if my luck is too low. The factory has a secure invisible x-ray machine, so they will see you stealing anyways.
Today (not a working day), my boss left me a message.
You' re a total wuss, Thomas. You spend five years working for us, and haven't stolen even one guffin. I'm sick of you and want to fire you. However, I had to warn you. The next 20 work-days (two weeks) are your last days at the factory (however, they can end earlier if you act correspondingly).
My plan is to steal 20 guffins once I get to the factory, and leave. A guffin market value now is quite high, so my family won't starve until I find a new job. However, I can see a nice puzzle here.
Having my information (no info on my secret number, and 20 days to quit the job), what is the best (mean) amount of guffins I can steal off my factory? What is the best strategy here?
Answer
New answer
Denote $E(d, k)$ be the expected gain of optimal actions given d remaining days and a knowledge that the limit is at least $k$. In particular, once we know that $k$ is safe, there is no reason to pick any number below $k$. Additionally, looting $20 \geq l \geq k$ guffins should have a $\frac{20-l}{20-k}$ chance of success, resulting in an expectation of $l+\frac{20-l}{20-k}E(d-1,l)$. Hence $E(d,k)$ is the maximum of these choices, and we therefore wish to compute $E(20, 0)$.
I wrote a program to compute the optimal strategy and it attains $110$ guffins on expectation. It does so by taking $10$ guffins on the first night, which succeeds exactly half of the time (if your secret number is at least 11). Then it keeps taking $10$ guffins on all subsequent nights except the last, where it takes $20$ guffins, in which its total loot becomes $210$ guffins.
Strategy table (row = # of days remaining, column = highest known safe number)
[{}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}],
[{20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {20}, {}],
[{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {9, 10}, {9}, {8, 9}, {8}, {8, 7}, {7}, {7}, {8}, {9}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {9}, {9}, {9}, {9}, {9}, {8}, {8}, {9}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {9, 10}, {9}, {9}, {9}, {9}, {9}, {9}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {9, 10}, {9}, {9}, {9}, {9}, {9}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {9, 10}, {9}, {9}, {9}, {9}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {10}, {9, 10}, {9}, {9}, {9}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {9}, {9}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {9}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {9, 10}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {}],
[{10}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}]]Old answer, which assumed that the guffin limit was not fixed.
If you only had one day to work, clearly the best strategy is to steal the maximum number of 20 guffins since you would be fired anyway.
Now, what if you had two days to work? If you stole $k$ guffins, you will be fired with $k/20$ probability, and in the other $1-k/20$ chance, you would be able to steal 20 guffins tomorrow, so your expected value is $k+20(1-k/20)=20$. Oh, I guess it doesn't matter at all what $k$ you pick - your expected value remains at 20 guffins. This can be repeated inductively to conclude that you can't do better than taking 20 guffins and running. Or if you value the job more than, say, a different job, then you should wait until the very last day and taking the 20 guffins. Or if there's any chance of being rehired, try to do that quickly enough so that you can take your 20 guffins again. The sky's the limit! Or rather, 20 guffins is the limit.
No comments:
Post a Comment