Puzzle
3 minute read

Ponder This Challenge - July 2009 - Ending a backgammon game with a double

Ponder This Challenge:

What is the probability that the last move in a backgammon (link resides outside of ibm.com) game will be a double? To make things easier, we assume that all the 15 checkers of each player are at their 1-point (just ready to bear-off); so each player, in its turn, removes (bear-off) two checkers for every non-double throw and four checkers for every double.

Hint: The solution is *not* the trivial 1/6.

07/01: Note that there are two players.

07/21: The game is played till its end, even if the result is already determined. For example, when a player has only one checker left, he still throws the dices and game is defined to end with a double if the dices come up equal.

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

  • Since all the checkers are at 1-point, the players have only one legal move per dice throw - if it is a double they can bear-off four checkers; otherwise they bear-off two. We start with the simpler version of a single player by defining f(n) to be the probability of the last throw being a double when we start with n checkers.

    Clearly: f(1)=f(2)=1/6; f(3)=f(4)=11/36 and f(n)=1/6*f(n-4)+5/6*f(n-2).

    The solution for this recursion formula is f(2n-1)=f(2n)=(2+5*(-1/6)^n)/7.

    The recursion formula for two players in the game is a little more complicated:

    f(n,m)=1/6*f(m,n-4)+5/6*f(m,n-2) (with similar boundary conditions)
    and its solution is f(15,15)=~0.3417.

    Note that for the full game, the answer would be even larger, since there are, for example, situations where one may bear off four checkers with a 6-6 throw and none with 3-4 throw.

    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

  • John T. Robinson (06/30/2009 01:40 AM EDT)
  • Eric Farmer (06/30/2009 02:46 PM EDT)
  • Pataki Gergely (06/30/2009 03:29 PM EDT)
  • Michael Brand (06/30/2009 10:59 PM EDT)
  • Ioan Marius Popdan (07/01/2009 06:27 AM EDT)
  • Henry Bottomley (07/01/2009 08:11 AM EDT)
  • Latchezar Christov (07/01/2009 09:33 AM EDT)
  • Serge Thill (07/01/2009 09:36 AM EDT)
  • James MacAdie (07/01/2009 09:45 AM EDT)
  • Vladimir V. Sedach (07/01/2009 01:06 PM EDT)
  • Martin Thiim (07/01/2009 01:40 PM EDT)
  • Sevag Papazian (07/01/2009 02:01 PM EDT)
  • Mark Perkins (07/01/2009 02:29 PM EDT)
  • Alex Wagner (07/01/2009 04:46 PM EDT)
  • Beryl Schragger (07/01/2009 05:33 PM EDT)
  • Corey Cerovsek (07/01/2009 06:48 PM EDT)
  • Karl D'Souza (07/01/2009 07:24 PM EDT)
  • Reinder Verlinde (07/01/2009 08:01 PM EDT)
  • Andrew Holster (07/01/2009 09:41 PM EDT)
  • Dan Wood (07/01/2009 09:58 PM EDT)
  • Nyles Heise (07/02/2009 12:00 AM EDT)
  • Joe Fendel (07/02/2009 03:36 PM EDT)
  • Dan Dima (07/02/2009 05:06 AM EDT)
  • Bojan Basic (07/02/2009 05:13 AM EDT)
  • Satish Vedantam (07/02/2009 10:50 AM EDT)
  • Or Zuk (07/02/2009 11:51 AM EDT)
  • Mark Mixer (07/02/2009 01:04 PM EDT)
  • Jonathan Campbell (07/02/2009 02:08 PM EDT)
  • Jack Kennedy (07/02/2009 07:03 PM EDT)
  • Reiner (07/02/2009 07:24 PM EDT)
  • Martin (07/02/2009 07:24 PM EDT)
  • James Dow Allen (07/03/2009 02:54 AM EDT)
  • Jochen Hoenicke (07/03/2009 10:47 AM EDT)
  • Ionel Santa (07/03/2009 10:54 AM EDT)
  • Cosmin Munteanu (07/03/2009 01:15 PM EDT)
  • Balakrishnan V (07/03/2009 02:34 PM EDT)
  • Renato Fonseca (07/05/2009 06:53 PM EDT)
  • Ryan Milligan (07/05/2009 11:55 PM EDT)
  • Jason L. (07/06/2009 00:27 AM EDT)
  • Rickard Björklund (07/06/2009 08:23 AM EDT)
  • Razvan Gheorghita (07/06/2009 09:08 AM EDT)
  • Daniel Bitin (07/06/2009 01:13 PM EDT)
  • Kevin Williamson (07/06/2009 02:48 PM EDT)
  • Adam Daire (07/06/2009 08:14 PM EDT)
  • Jeff Blohm (07/07/2009 03:31 AM EDT)
  • Clive Tong (07/07/2009 04:32 AM EDT)
  • Greg Janee (07/09/2009 02:05 AM EDT)
  • John G Fletcher (07/09/2009 02:35 AM EDT)
  • Lukasz Bolikowski (07/09/2009 12:51 PM EDT)
  • Albert Stadler (07/10/2009 09:08 AM EDT)
  • Andrea Andenna (07/11/2009 08:27 PM EDT)
  • Boris Nikolaus (07/12/2009 08:22 AM EDT)
  • Asad Usman (07/13/2009 09:54 AM EDT)
  • Tomek Czajka (07/14/2009 03:51 PM EDT)
  • Jimmy Hu (07/17/2009 03:46 PM EDT)
  • Robert Szafranski (07/19/2009 07:23 PM EDT)
  • Gale Greenlee (07/22/2009 03:33 PM EDT)
  • Satish Kumar K N (07/23/2009 04:23 PM EDT)
  • Antoine Comeau (07/23/2009 08:54 PM EDT)
  • David Friedman (07/24/2009 05:32 PM EDT)
  • Jeremy Cahill (07/29/2009 04:24 AM EDT)
  • Adriana Clerici (07/29/2009 10:08 AM EDT)
  • Ehud Schreiber (07/30/2009 03:51 PM EDT)
  • Andrew Rochon (07/31/2009 04:45 AM EDT)
  • T (07/31/2009 02:20 PM EDT)
  • ravis Craig & Jean-Pascal Harroch (07/31/2009 02:20 PM EDT)

Related posts