[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1298.0. "Guess the number game with two players" by TRACE::GILBERT (Ownership Obligates) Fri Sep 21 1990 11:21

    A 'guess the number' contest on the radio inspired the following problem.

    A number� from 1 thru 10 is randomly chosen�, and two players take turns
    guessing the number.  After a guess, the players are told whether the guess
    is too high, is too low, or is correct.  The player who first guesses the
    number wins.

    The problem is this: What is the first player's optimal strategy?
    And what is his expectation of winning?

					- Gilbert

� An integer number, either 1,2.3,4,5,6,7,8,9, or 10.
� The ten numbers have equal probabilities of being chosen.
T.RTitleUserPersonal
Name		DateLines
1298.1Solution hidden behind form feed:CHOVAX::YOUNGCooper Bullet-Proof Vests, Inc.Fri Sep 21 1990 14:2113
    
    
    The first player should guess either 1 or 10.
    
    Reasoning:
    
    	1 or 10 has the same chance of being right as any other number and
    	has the advantage that, if wrong, it reveals NO information to your 
    	opponent.  Since any information ("higher or lower") revealed by an
    	incorrect guess can be acted on by your opponent before you, you
    	should try to reveal as little information as possible.
    
    --  Barry
1298.2Probability of Player 1 WinningVAXRT::BRIDGEWATERBlasting out of the past.Fri Sep 21 1990 15:2019
    If both players play optimally, the probability of player 1 winning
    is:

    

    1/2

    Guess #    Probability of Player 1 winning on this guess
    --------------------------------------------------------
      1         (1/10)
      2         (9/10)*(8/9)*(1/8)
      3         (9/10)*(8/9)*(7/8)*(6/7)*(1/6)
      4         (9/10)*(8/9)*(7/8)*(6/7)*(5/6)*(4/5)*(1/4)
      5         (9/10)*(8/9)*(7/8)*(6/7)*(5/6)*(4/5)*(3/4)*(2/3)*(1/2)
    
      Each of the above probabilities is equal to 1/10.  Summing them
      gives the total probability of player 1 winning, 1/2.

      - Don
1298.3TRACE::GILBERTOwnership ObligatesFri Sep 21 1990 15:3913
Let the number of numbers be n.  If n is even, it's a fair game
(expectation=1/2), and choosing any number yields an optimal strategy.
If n is odd, an optimal strategy is to choose any odd ordinal number
(the first, third, fifth, etc), and this yields an expectation of (n+1)/(2n).

Now, ...

Assume that the players *must* choose some reasonable number; for example,
if the number is known to be > 3 and < 7, the player must choose 4, 5, or 6.
Is it possible to randomly choose the initial number (i.e., with a non-uniform
probability distribution) so that the *second* player gets the advantage?

					- Gilbert
1298.4Proof of previous.CADSYS::COOPERTopher CooperFri Sep 21 1990 18:3756
RE: .3 (Gilbert)

>Let the number of numbers be n.  If n is even, it's a fair game
>(expectation=1/2), and choosing any number yields an optimal strategy.
>If n is odd, an optimal strategy is to choose any odd ordinal number
>(the first, third, fifth, etc), and this yields an expectation of (n+1)/(2n).

    Since you got it in before I did, let me present the proof which you
    "left as an exercise".

    Assume that N is even and the statement is true for all smaller N.
    Call the winning number W.

    Choose a as the initial choice.

    There are three possibilities: 1) W = a (prob=1/N) 2) W < a (prob =
    (a-1)/N) and 3) W > a (prob = (N-a)/N).

    If a is even, then the segment below a is of odd length, so if W is
    there the second player has the advantage with a probability of
    a/(2a-2) of winning.  This means that the first player has a chance
    of (a-2)/(2a-2) of winning if W < a.  The segment above a is of even
    length so the probability of the first player winning under those
    conditions is simply 1/2.  Total probability of the first player
    winning is then:

	 a-2   a-1   1   1   N-a
	---- * --- + - + - * --- = 1/2
	2a-2    N    N   2    N

    If a is odd, then it works out to:

	1   a-1   1   N-a+1   N-a
	- * --- + - + ----- * --- = 1/2
	2    N    N   2N-2a    N

    If N is odd and a is even, both segments remaining after a has been
    selected are odd, so:

	 a-2   a-1   1   N-a+1   N-a   N-1
	---- * --- + - + ----- * --- = --- < 1/2
	2a-2    N    N   2N-2a    N    2N

    If N is odd and a is odd, both segments remaining afterr a has been
    selected are even, so:

	1   a-1   1   1   N-a	N+1
	- * --- + - + - * --- = --- > 1/2
	2    N    N   2    N	2N

    Base cases:  If N is 1, the first player wins with probability (N+1)/2N
    = (1+1)/(2*1) = 1.  If N is 2, the first player has 1 chance in 2 of
    picking the correct choice (it was not actually necessary to use this
    base case -- it just was simple and more comfortable).

				    Topher
1298.5TRACE::GILBERTOwnership ObligatesMon Sep 24 1990 11:3117
Rewording the problem in .3:

Assume that the players *must* choose some reasonable number; for example,
if the number is known to be > 3 and < 7, the player must choose 4, 5, or 6.
Is it possible to choose the initial number with a non-uniform probability
distribution (which is known to both players) so that the *second* player
gets the advantage?


re .1

> 1 or 10 has the same chance of being right as any other number and
> has the advantage that, if wrong, it reveals NO information to your
> opponent.

Actually, it may reveal that "the answer is not 1" or "... not 10". And
reply .4 shows that this is important.