CS 99

Summer 2002: HW8 7.22

Solutions

1. A dice-throwing game

Part A: Just one game
%ABCGame
rounds = 0;
haveWin = 0;
msg = [ 'A', 'B', 'C' ];
while ~haveWinner
    rounds = rounds + 1;    
    if ceil( 6*rand ) <= 3
         haveWinner = 1;
    elseif ceil(6*rand) <= 2
        haveWinner = 2;
    elseif ceil(6*rand) == 1
        haveWinner = 3;
    end
end
if rounds > 1
    disp( [ msg( haveWinner ) ' wins in ' num2str( rounds ) ' rounds.' ]);
else
    disp( [ msg( haveWinner ) ' wins in ' num2str( rounds ) ' round.' ]);
end


Part B: Lots of games
%ABCTrials.m
NUMTRIALS = 16384;
rounds = zeros(1, NUMTRIALS);
whoWins = zeros( 1, 3 );
for ii = 1 : NUMTRIALS
        haveWinner = 0;
        while ~haveWinner
            rounds( ii )  = rounds( ii ) + 1;    
            if ceil( 6*rand ) <= 3
                 haveWinner = 1;
            elseif ceil(6*rand) <= 2
                haveWinner = 2;
            elseif ceil(6*rand) == 1
                haveWinner = 3;
            end
        end
        whoWins( haveWinner ) = whoWins( haveWinner ) + 1;
end
fprintf('The estimated number of rounds to win a game using %d trials is %f\n', NUMTRIALS, mean( rounds ) );
fprintf('The estimated probabilities the players win is : ');
disp(num2str( whoWins/NUMTRIALS ));


Part C. Bonus*
Let the probability that A wins be x.
Note that the probability that A wins is equal to the probability he wins in the first round, plus the probability that he wins later.
The probability he wins later is the probability no one wins in the first round times the probability he wins in a later round;
but after the first round, the game in effect recommences, so the probability A will win in a later round is again x.

Ergo,

x = (1/2) + (1/2)(2/3)(5/6) x
x = 9/13.

A similar set of calculations finds that the probability B wins is 3/13, and for C it is 1/13.

The probability no one wins in a given round is 13/18. Hence, the average number of rounds before we see a winner must be 18/13.

2. Runaround arrays*

%Runaround.m

vec = input(’Enter a vector of length < 9: ‘);
ans = vec; %store original values in vec
res = 1;
%make sure no digits are repeated
for jj = 1 : 9
    if sum( vec == jj ) > 1
         res = 0;
        break;
    end
end
%see if vec satisfies other requirements for a runaround array
if res
    currIndx = 0; %(currIndx + 1) is current index in array
    for k = 1 :  length( vec )
%get next index value
currIndx = mod( vec( currIndx + 1 ) + currIndx, length( vec ) );
%change value at present position in vec to 1
vec( currIndx + 1 ) = 1;
    end
    res = (prod( vec ) == 1); %if we miss any elements this will not return 1

end
%display results
if res
disp([ num2str( ans ) ‘ is a runaround array.’]);
end