Ponder This Challenge - January 2002 - Gambling casino

Ponder This Challenge:

This month's puzzle comes from James Shearer.

To celebrate the new year, you have decided to open a gambling casino.
Because you are a fair-minded person, you will arrange the games
so that your advantage is minimal.
In each game, the gambler will bet one euro coin;
With probability 0.499 the gambler will win (and you, the "house",
will pay him one coin);
With probability 0.501 the gambler will lose (and the "house"
will collect one coin from him).
The outcome of each game is independent of previous games.

You start your casino with k coins in the treasury.

You may have a run of bad luck; with probability 0.499**k,
the first k games will go against you, and the house will go broke.
(That is, its treasury will go to 0 euros.)
Or you may lose k+3 out of the first k+6 games, and still go broke.
And so on.
Part 1:
What is the minimum integer k such that with
probability exceeding 1/2, the house will never go broke?

Part 2:
Use the value of k from part 1.
One bet is placed per hour, starting at the stroke of midnight.
Assuming that the house does go broke, when is this most likely to
happen? (Date and hour.)

Part 3 (off the wall and unrelated):
My cat died last month at the age of seventeen.
We used to enjoy her standing on her hind legs to beg for cream cheese.
Why do we think of her as being futuristic?

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  1) k=174.

  Let p(k) be the probability that the house will never go broke,
  given that the house starts with k coins.
  By convention p(0)=0, and p(k) approaches 1 as k grows to infinity.
  These probabilities satisfy the equation:
  p(k) = 0.499*p(k-1) + 0.501*p(k+1).
  The solution to this equation is p(k)=1-(0.499/0.501)**k.
  We compute that p(173)=0.4994... and p(174)=0.5014...

  2) The house is most likely to go broke at 11PM, February 19, 2003.
  Let k=174, and let q(m) be the probability that the house first goes
  broke at bet number k+2m.
  Consider paths in 2-space (parameterized by time
  and the house's current treasury), starting at (0,k) and moving via steps
  of either (+1,+1) or (+1,-1), corresponding to bets which the house
  wins or loses, respectively.
  Let r(m) be the number of paths from (0,k) to (k+2m-1,1), allowing
  intermediate visits to (t,0) for some time t, 0<t<k+2m-1.
  Let s(m) be the number of paths from (0,k) to (k+2m-1,1), requiring
  an intermediate visit to (t,0).
  In order to first go broke at time k+2m, we need to execute a path
  among those counted by r(m) (but not among those counted by s(m)),
  followed by a step of (+1,-1) corresponding to losing that last euro.
  So we have q(m)=((r(m)-s(m))*(0.501**m)*(0.499**(k+m)).
  Also r(m)=(k+2m-1)!/(k+m)!(m-1)!.
  We can calculate s(m) by the "reflection principle" (see Feller,
  An Introduction to Probability Theory and its Applications, volume I):
  Make a one-to-one transformation on all paths from (0,k), namely
  if a path ever reaches (t,0), reverse all the edges after that point.
  The paths counted by s(m) are transformed precisely into those paths
  from (0,k) to (k+2m-1,-1), so that s(m)=(k+2m-1)!/(k+m-1)!m!.
  Now calculate that
  q(m+1)/q(m)=.501*.499*(k+2m+1)*(k+2m)/(k+m+1)*(m+1).
  When m=4892 or smaller, q(m+1)/q(m)>1.
  When m=4893 or larger, q(m+1)/q(m)<1.
  So q(m) is maximized when m=4893. The first bet takes place at
  midnight on New Years (time = 1), and k+2m = 9960 = 24*(365+50).

  3) Her lifespan (1984-2001) evokes the titles of two futuristic novels,
  George Orwell's "Nineteen Eighty-Four" and
  Arthur C. Clarke's "2001, a Space Odyssey".

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• Part 1 Correct (None)
• Vince Lynch (1.2.2002 @ 10:39 AM EDT)
• Jayavel Sounderpandian (1.2.2002 @ 4:24 PM EDT)
• Ashish Mishra (1.2.2002 @ 9:46 PM EDT)
• Will Brockman (1.3.2002 @ 1:26 PM EDT)
• Ed Sheppard (1.3.2002 @ 2:17 PM EDT)
• Dave Biggar (1.4.2002 @ 8:11 AM EDT)
• Jacques Willekens (1.4.2002 @ 9:06 AM EDT)
• José H. Nieto (1.4.2002 @ 7:13 PM EDT)
• Huafeng Xu (1.6.2002 @ 2:21 PM EDT)
• Shmuel Spiegel (1.8.2002 @ 12:59 AM EDT)
• Ross Millikan (1.8.2002 @ 6:58 PM EDT)
• Alan O'Donnell (1.10.2002 @ 7:02 AM EDT)
• Amrit Pratap (1.10.2002 @ 1:50 PM EDT)
• Bill Schwennicke (1.10.2002 @ 1:50 PM EDT)
• Christopher Howe (1.10.2002 @ 2:00 PM EDT)
• Nagendra (1.10.2002 @ 2:00 PM EDT)
• John G. Fletcher (1.10.2002 @ 2:00 PM EDT)
• Ross George (1.14.2002 @ 9:50 PM EDT)
• Narayanan Rajamani (1.14.2002 @ 9:50 PM EDT)
• Nancy Schwarzkopf (1.14.2002 @ 12:37 PM EDT)
• Virginie Yaich (1.16.2002 @ 3:20 PM EDT)
• David H. Jones (1.22.2002 @9:40 AM EDT)
• Georg Wille (1.22.2002 @ 10:00 PM EDT)
• Philippe Fondanaiche (1.22.2002 @ 10:00 PM EDT)
• Guy Roberts (1.22.2002 @ 10:00 PM EDT)
• Arun Sivaramakrishnan (1.23.2002 @ 10:00 PM EDT)
• Chu-Wee Lim (1.30.2002 @ 1:00 PM EDT)
• Kennedy (1.30.2002 @ 1:00 PM EDT)
• Part 2 Correct (None)
• Vince Lynch (1.2.2002 @ 8:40 PM EDT)
• Ashish Mishra (1.2.2002 @ 9:46 PM EDT)
• Jayavel Sounderpandian (1.3.2002 @ 7:29 PM EDT)
• Jacques Willekens (1.4.2002 @ 9:06 AM EDT)
• Huafeng Xu (1.6.2002 @ 11:58 PM EDT)
• José H. Nieto (1.8.2002 @ 9:23 AM EDT)
• Ed Sheppard (1.9.2002 @ 2:57 AM EDT)
• Bill Schwennicke (1.10.2002 @ 1:50 PM EDT)
• John G. Fletcher (1.10.2002 @ 2:00 PM EDT)
• Nancy Schwarzkopf (1.14.2002 @ 12:37 PM EDT)
• Nagendra (1.16.2002 @ 10:31 PM EDT)
• Arun Sivaramakrishnan (1.23.2002 @ 10:00 PM EDT)
• Philippe Fondanaiche (1.24.2002 @ 10:00 PM EDT)
• Kennedy (2.04.2002 @ 1:00 PM EDT)
• Part 3 Correct (None)
• Daniel Chalk (1.2.2002 @ 3:42 PM EDT)
• Will Brockman (1.3.2002 @ 1:26 PM EDT)
• Jeffrey Nelson (1.3.2002 @ 6:51 PM EDT)
• José H. Nieto (1.4.2002 @ 7:13 PM EDT)
• Alan O'Donnell (1.7.2002 @ 12:32 PM EDT)
• Vince Lynch (1.14.2002 @ 9:40 PM EDT)
• Part 3 Partially Correct (None)
• David H. Jones (1.2.2002 @ 11:24 AM EDT)
• Vince Lynch (1.2.2002 @ 8:40 PM EDT)
• Jesse Burkett (1.10.2002 @ 1:40 PM EDT)
• Graeme McRae (1.22.2002 @ 10:00 PM EDT)
• Guy Roberts (1.22.2002 @ 10:00 PM EDT)