Ponder This Challenge - February 2007 - When to discard a random number?

Ponder This Challenge:

Puzzle for February 2007.

Consider the following two person game. Each player receives a random number uniformly distributed between 0 and 1. Each player can choose to discard his number and receive a new random number between 0 and 1. This choice is made without knowing the other players number or whether the other player chose to replace his number. What strategy should a player follow to ensure he will win at least 50% of the time?

REVISED, 2/5/07 -- After each player has had an opportunity to replace his number the numbers are compared and the player with the higher number wins.

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

  Answer:

  A player will ensure he wins at least 50% of the time by choosing to receive a new number when his original number is less than (sqrt(5)-1)/2 = .6180+.

  It should be clear that we need only consider strategies of the form, choose a new number if the original number is < x otherwise keep the original number. Suppose player A uses threshold x and player B uses threshold y. Then it can be shown that the probability, p, that A will win is
  p=.5*(1+x-y-x*y+y*y+x*y*y-x*x*y) for x <= y
  p=.5*(1+x-y-x*x+x*y+x*y*y-x*x*y) for x >= y
  or
  p=.5+.5*(x-y)*(1-y-x*y) for x <= y
  p=.5+.5*(x-y)*(1-x-x*y) for x >= y
  Suppose A chooses x=(sqrt(5)-1)/2. Note x*x+x=1.
  Now if y > x then x*y+y > 1 so (x-y) < 0 and (1-y-x*y) < 0 so
  (x-y)*(1-y-x*y) > 0 which implies p > .5.
  Also if y < x then x*y+x < 1 so (x-y) > 0 and (1-x-x*y) > 0
  so (x-y)*(1-x-x*y) > 0 which implies p > .5.

  So if A chooses x = (sqrt(5)-1)/2 he will win more than 50% of the time unless B chooses y = (sqrt(5)-1)/2 also in which case he will win exactly 50% of the time.

  ---

  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

• V. Balakrishnan (02.02.2007 @12:15:36PM EST)
• Joseph DeVincentis (02.02.2007 @12:58:38PM EST)
• John T. Robinson (02.02.2007 @02:26:33PM EST)
• Dan Dima (02.02.2007 @04:50:10PM EST)
• Dan Stronger (02.03.2007 @05:31:24AM EST)
• Frank Yang (02.03.2007 @10:56:08AM EST)
• Arthur Breitman (02.03.2007 @02:11:46PM EST)
• Chris Danielian (02.03.2007 @02:54:49PM EST)
• Tom Gutman (02.03.2007 @03:23:36PM EST)
• Joshua Green (02.03.2007 @09:18:51PM EST)
• Michael Brand (02.04.2007 @12:53:11AM EST)
• Xiancho Xie (02.04.2007 @11:23:50AM EST)
• Eric Cope (02.04.2007 @03:33:03PM EST)
• Christian Blatter (02.04.2007 @09:29:17PM EST)
• Chris Messer (02.04.2007 @09:56:02PM EST)
• James Dow Allen (02.05.2007 @01:33:34AM EST)
• Jayavel Sounderpandian (02.05.2007 @04:12:17AM EST)
• Gary Gerkin (02.05.2007 @07:16:48AM EST)
• Andreas Eisele (02.06.2007 @09:18:32 AM EST)
• Ramon A Casanova (02.06.2007 @11:56:34 AM EST)
• Dharmadeep Muppalla (02.06.2007 @12:31:11 PM EST)
• David Friedman (02.06.2007 @02:33:54 PM EST)
• Dion Harmon (02.07.2007 @01:51:45 AM EST)
• Austin Shapiro (02.07.2007 @01:02:45 PM EST)
• John Hubenschmidt (02.07.2007 @03:34:48 PM EST)
• Alvaro Martinez Echevarria (02.08.2007 @06:13:11 AM EST)
• Eric Farmer (02.08.2007 @08:15:59 AM EST)
• Jiri Navratil (02.08.2007 @02:53:47 PM EST)
• Nyles Heise (02.08.2007 @05:17:47 PM EST)
• Mark Pilloff (02.08.2007 @06:23:09 PM EST)
• Henry (02.08.2007 @07.15.56 PM EST)
• Adriano Batista (02.08.2007 @09:07:22 PM EST)
• Brian Tung (02.09.2007 @12:32:36 AM EST)
• Igor Krivokon (02.09.2007 @05:00:47 AM EST)
• Marcus Hedbring (02.09.2007 @09:28:07 AM EST)
• Jihan Kim (02.09.2007 @01:07:41 PM EST)
• Yurun Liu (02.09.2007 @03:04:57 PM EST)
• Ed Sheppard (02.10.2007 @01:30:22 PM EST)
• Celia Anteneodo (02.10.2007 @06:40:41 PM EST)
• Vincent Lynch Doncaster (02.10.2007 @07:14:27 PM EST)
• Joe Riel (02.11.2007 @02:54:52 PM EST)
• ariel flat (02.12.2007 @02:46:29 AM EST)
• Rob Berger (02.12.2007 @11:16:49 PM EST)
• Bart DeVylder (02.13.2007 @09:21:25 AM EST)
• John Fletcher (02.14.2007 @12:52:47 AM EST)
• Dan Mihailescu (02.15.2007 @12:34:01 PM EST)
• Fabio Chalub (02.15.2007 @01:10:00 PM EST)
• Teodora Baeva (02.16.2007 @05:29:30 AM EST)
• Luke Pebody (02.16.2007 @04:16:17 PM EST)
• Greg Jane (02.18.2007 @12:18:47 AM EST)
• Giorgio Antonelli (02.18.2007 @09:25:21 PM EST)
• Yoav Raz (02.20.2007 @04:02:00 AM EST)
• David McQuillan (02.20.2007 @05:28:51 AM EST)
• Lukasz Bolikowski (02.20.2007 @02:05:31 PM EST)
• Abhisek Ukil (02.21.2007 @03:54:32 AM EST)
• ansrivas (02.22.2007 @11:37:45 AM EST)
• Andrea Andenna (02.24.2007 @03:52:56 AM EST)
• jncarrapa (02.25.2007 @09:09:15 PM EST)
• Timothy Ozimek (02.25.2007 @09:51:57 PM EST)
• Phil Muhm (02.26.2007 @11:17:27 AM EST)
• Jesse Blosser (02.26.2007 @09:09:19 PM EST)
• Joaquim Neves Carrapa (02.27.2007 @05:44:34 AM EST)
• Du Yang (02.27.2007 @06:52:02 AM EST)
• Amos Guler (02.27.2007 @10:26:11 AM EST)
• Vinoad Senguttuvan (02.27.2007 @12:48:08 PM EST)
• Reiner Martin (02.27.2007 @07:13:07 PM EST)
• Ben North (02.28.2007 @10:33:39 AM EST)
• Gale Greenlee (03.02.2007 @10:08:28 AM EST)