13
$\begingroup$

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?

$\endgroup$
  • 11
    $\begingroup$ What kind of bizarre job has 20 workdays in two weeks? $\endgroup$ – user2357112 Jul 15 '18 at 3:26
  • 4
    $\begingroup$ Does this mean that there's an opening at the Guffin company? I've been dying to get in there. $\endgroup$ – Chowzen Jul 15 '18 at 11:57
  • $\begingroup$ @Chowzen Not if I get in first! $\endgroup$ – PotatoLatte Jul 15 '18 at 22:05
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The induction you're glossing over doesn't actually work. $\endgroup$ – user2357112 Jul 15 '18 at 3:16
  • $\begingroup$ I misread the question thinking that the guffin limit could change every day $\endgroup$ – phenomist Jul 15 '18 at 3:29
  • $\begingroup$ @phenomist This looks like a correct answer, but I cannot be sure of the program I haven't seen. If you still have it - could you attach a 20x20 table of the D? Thus I could check the calculation (at least briefly) and, maybe, spot some other patterns in the common strategy. $\endgroup$ – Thomas Blue Jul 17 '18 at 12:45
6
$\begingroup$

I think you can get the expectation value up to

105.05 $110$ guffins (thanks to Umbozz for the suggestion)

Strategy

Let's say you decide to steal $X$ guffins everyday until you are fired. Then you will either be fired after the first day (probability $\frac{X}{20}$) or you will be fired after $20$ days, ( probability $ 1 - \frac{X}{20}$ ).

Hence the expected number of guffins you get is $X \left( \frac{X}{20} \right) + 20X\left(1- \frac{X}{20} \right) = 20X - \frac{19}{20} X^2$. This function takes its maximum value at $X = \frac{200}{19}$ which is slightly closer to $11$ than $10$.

With $11$, the expected number of guffins is $105.05$.

As Umbozz pointed out in the comments, you can steal $20$ guffins on the last day instead of $X$ so this increases your expectation to $18X - \frac{18}{20}X^2 + 20$. This function takes its maximum at $X=10$ at which point the value is $110$,

$\endgroup$
  • 3
    $\begingroup$ does this include stealing 20 on the last day, since he would get fired anyway? also, the first X are guaranteed, so if i understand correctly it should be X+(18X + 20)(1−X/20). this function has its max at x=10, y=110 $\endgroup$ – Umbozz Jul 15 '18 at 1:50
0
$\begingroup$

For optimization, if you reach it, you always have to steal 20 on day 20.

My intuitive strategy would be to start at one and increment by one each day.

I am aware that this is not the optimal strategy, i simply added it as an answer because it was my intuitive approach and i figured others might think of the same.

The maximum possible earning would be 210, the minimal 1.

So the chance that you reach day 2 is 0.95, since the chance to get caught on day 1 was 5%. The expected value that day is 1.9
The chance to reach day 3 is 0.9, the expected value is 2.7. Continuing like this and you would reach an expected value of 77 on day 20.

However, since you are sure to earn 20 on the last day, it would be clever to stop gambling once the expected value from the following runs drops below 20. At that point continuing to steal the same number until the last day comes fairly close to hexonimos answer.

stopping at each number yields
at 1: (0.95 * (1 * 18 + 20)) + 1 = 37.1
at 2: (0.90 * (2 * 17 + 20)) + 1 + (0.95 * 2) = 51.5
at 3: (0.85 * (3 * 16 + 20)) + 1 + (0.95 * 2) + (0.9 * 3) = 63.4
...
This approach peaks at 93.5 for 9 and 10

So the strategy would be to start at 1 and steal 1 more every day until day 9 or 10, then keep stealing 9 or 10 until day 20, when you steal 20.

While it has a lower expected value than hexonimos answer, this approach has the benefit of higher outcomes in certain ranges of your assigned number: If your number is between 4 and 10, you will reach higher values than just stealing 10/11 from the start, which might be get you a total of 10/11.

While a higher expected total value might be the core question, this approach offers a certain insurance against medium bad luck, which might be relevant since you describe a scenario in which a human gambles.

$\endgroup$
  • $\begingroup$ Also, this offers the worst case scenario for secret=1, and it lowers your EV, so calling it "insurance" does sound a lot like the insurance on a blackjack table. $\endgroup$ – Bass Jul 15 '18 at 10:33
  • $\begingroup$ yeah i know, thats why i said against medium bad luck, if your number is between 4 and 10. i simply submitted this despite having a lower expected return because it was my intuitive approach, and i figured others would think of the same. $\endgroup$ – Umbozz Jul 15 '18 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.