Welcome to NRICH.

 
Dice rolling game
By Peter Gyarmati on Thursday, December 19, 2002 - 08:59 pm:

A and B players take turns rolling a die. The number shown by the die is always added to their recpective scores. Whoever obtains the first score divisible by 4, wins the game. Given that A player starts the game, what is the probabilty that he will win?

By Joel Kammet on Friday, December 20, 2002 - 07:00 am:

Approximately .569

By Andre Rzym on Friday, December 20, 2002 - 08:13 am:

One way of computing the answer (but tedious) is to firstly observe that at the point of A’s turn, you don’t care about the scores, merely the scores mod 4. So there are really 9 probabilities of interest:

P11 the prob that A wins given A’s score is 1, B’s score is 1
P12 the prob that A wins given A’s score is 1, B’s score is 2
…
P33 the prob that A wins given A’s score is 3, B’s score is 3

Now we can define 9 relationships between these 9 unknowns by considering the outcome of A’s and B’s subsequent throws. Of the 36 possibilities, some will lead to immediate win for A, some will lead to loss for A (because B won) and some will just leave the scores in a different ‘state’. Thus

P11=1/36.(6.1 + 5.0 + 1.P11 + …)

Etc.

If you are willing to solve all 9 equations you get all the P’s from which you can calculate the probability of A winning.

Andre

By Andre Rzym on Friday, December 20, 2002 - 08:48 am:

0.569 looks correct to me.

Andre

By Arun Iyer on Friday, December 20, 2002 - 01:33 pm:

yeap 0.569 is correct

i approximated my previous answer a bit too much....

My approach was :
P(A winning) = P(A winning on the first roll) + P(B not winning on the first roll)*P(A winning on the second roll)+P(B not winning on the second roll)*P(A winning on the third roll)+....

i made a few assumption and tried to approximate the value which gave me at first the answer 179/330...

however,i then implemented the same approach in a C program which gave me ->
(Let n denote the number of terms in the formula above)
for n=1 : P(A winning) = 0.166667
for n=2 : P(A winning) = 0.351852
for n=3 : P(A winning) = 0.459362
for n=4 : P(A winning) = 0.512081
for n=5 : P(A winning) = 0.539746
for n=6 : P(A winning) = 0.554052
for n=7 : P(A winning) = 0.561464
for n=8 : P(A winning) = 0.565304
for n=9 : P(A winning) = 0.567293
for n=10: P(A winning) = 0.568324
for n=11: P(A winning) = 0.568858

As you can see the Probability converges very fast to 0.569 just at the 11th term..

love arun

By Andre Rzym on Friday, December 20, 2002 - 08:13 pm:

OK, well I’m not pretending that this is particularly simple solution, but it does give you the exact solution.

I assume you are OK with the definitions of P11 etc.

Suppose that we had rolled the die, it was now A’s turn and the scores are 1,1 mod 4. Of the 36 possible outcomes (of A rolling and then B rolling), 6 lead to A winning (i.e. A rolls 3 and B rolls any of 1..6), 5 lead to A losing (i.e. A rolls anything but 3 and B rolls 3), 1 leads to new scores of (1,1), 2 lead to scores of (1,2) etc.

So we can write

P11=1/36(6 + P11 + 2.P12 + 2.P13 + 2.P21 + 4.P22 + 4.P23 + 2.P31 + 4.P32 + 4.P33

There are 8 other similar equations. If we solve them simultaneously, we get:

P11 = 0.573
P12 = 0.494
P13 = 0.502
etc.

Finally, we observe that our starting point is scores of (0,0), which, considering the 36 possible outcomes of the first pair of rolls gives us:

P00=1/36(6 + 4.P11 + 4.P12 + 2.P13 + 4.P21 + 4.P22 + 2.P23 + 2.P31 + 2.P32 + 1.P33

Substituting we get the result P00 = 0.569

Andre

By Joel Kammet on Saturday, December 21, 2002 - 05:23 pm:

Thanks Andre. It's reassuring to see that it can be solved with pen & paper, even if it takes a LOT of paper.
But for those who can live with 6 decimal place accuracy (.569537) & prefer to let the electrons do the work, here's my program.

Arun: does yours work pretty much the same way, or did you have a different approach?

#include
double get_prob(int rounds);

main()
{
int rounds;
printf("How many partial sums do you want? > \n");
scanf("%d",&rounds);
get_prob(rounds);
return 0;
}

/* function computes probability that player a's cumulative sum after
n rolls of the die is the first sum that is divisible by 4
by summing terms of the sequence of probabilities of each roll
input n: desired number of rolls of the die
*/

double get_prob(int n)
{
int i,sum,m1next,m2next,m3next,awnext,sumnext;
int awins=1,m1=2,m2=2,m3=1;
double aprob=1.0/6,bprob=1.0;

printf("Probability that A wins on roll\n\t#1:\t%f\n",aprob);
for(i=1;i<n;i++)
{
sum=m1+m2+m3+awins;
m1next=m1+m2+2*m3;
m2next=m2+m3+2*m1;
m3next=2*m1+2*m2+m3;
awnext=m1+2*m2+2*m3;
sumnext=m1next+m2next+m3next+awnext;
/* bprob is probability that b DIDN'T win: */
bprob = bprob * pow(((double)sum-awins)/sum, 2);
aprob=aprob + bprob*((double)awnext/sumnext);
printf("\t#%d:\t%f\n",i+1,aprob);

m1=m1next;
m2=m2next;
m3=m3next;
awins=awnext;
}

return aprob;
}

By Arun Iyer on Saturday, December 21, 2002 - 05:52 pm:

Joel,
your program is way smaller and much more efficient than mine(much much more infact!!).

my program implies the old way of calculating the probability
P(E) = no. of favourable cases/total cases.
(To calculate all favourable cases,i have used 2 recursive functions which makes my program dead slow)

Though i am not exactly sure how your program works.. i mean i am not able to understand the idea behind that for loop part!!

love arun
P.S->
for those who would like to test their computer speed may run my program :)

the program:
#include"stdio.h"
#include"conio.h"
int a[100],sum;
long double favcountA=0,allcountA=0,favcountB=0,allcountB=0;
void permuteA(int n,int k)
{
int i,p,flag;
for(i=1;i<=6;i++)
{
a[n]=i;
if(n<k)
permuteA(n+1,k);
else
{
allcountA++;
flag=1;
sum=0;
for(p=1;p<k;p++)
{
sum=sum+a[p];
if(sum%4==0)
flag=0;
}

sum=0;
if(flag)
{
for(p=1;p<=k;p++)
sum=sum+a[p];
if((sum%4)==0)
{
/*for(p=1;p<=k;p++)
printf("%d ",a[p]);*/
favcountA++;
//printf("\t");
}
}
}
}
}
void permuteB(int n,int k)
{
int i,p,flag;
for(i=1;i<=6;i++)
{
a[n]=i;
if(n<k)
permuteB(n+1,k);
else
{
allcountB++;
flag=1;
sum=0;
for(p=1;p<k;p++)
{
sum=sum+a[p];
if(sum%4==0)
flag=0;
}
sum=0;
if(flag)
{
for(p=1;p<=k;p++)
sum=sum+a[p];
if((sum%4)!=0)
{
/*for(p=1;p<=k;p++)
printf("%d ",a[p]);*/
favcountB++;
//printf("\t");
}
}
}
}
}
void main()
{
clrscr();
int n,i;
long double pA,pB,sumprob=0.166666;
printf("Enter n:");
scanf("%d",&n);
// for(i=2;i<=n;i++)
// {
printf("\nFor A:\n");
permuteA(1,n);
pA=favcountA/allcountA;
printf("\nFavourable cases :%f",favcountA);
printf("\nAll cases :%f\n",allcountA);
printf("P(A)=%f\n",pA);
printf("\nFor B:\n");
permuteB(1,n-1);
pB=favcountB/allcountB;
printf("\nFavourable cases :%f",favcountB);
printf("\nAll cases :%f\n",allcountB);
printf("P(B)=%f\n",pB);
printf("\nP(A)*P(B)=%f",pA*pB);
// sumprob=sumprob+pA*pB;
// }
// printf("Probability : %Lf",sumprob);
getch();
}

remember the program asks you to enter n.
if you enter 2 .. it calculates the value of 2nd term of the formula i gave in my last post and not the sum.

you would have to add the value you get for n=1 to get the probability... (Sorry for this inconvenience but .. if the comments are removed and a few adjustments are made ... the program will also calculate the sum)

i know what y'all are thinking .. i have never been an efficient programmer anyways :)

By Joel Kammet on Saturday, December 21, 2002 - 07:17 pm:

Wow. It's going to take a while to digest all of that! But as you can easily run circles around me in math, your programming is forgiven.:)

As for my program, I actually set out to write it recursively because I wanted to practice recursion, but decided that would really be "bending over backwards". This problem doesn't really want to be solved recursively, since that means refiguring all of the probabilities over and over again.

Anyway, "aprob" is the probability we're looking for. It starts out obviously at 1/6. (bprob starts out at 1 for convenience, so I can multiply it in the loop -- more on that later). The scores m1,m2 and m3 are in mod4 terms. The die can come up 1,2,3,4,5 or 6. 1%4 is 1, 2%4 is 2, 3%4 is 3, 4%4 is 0 (a WINNER), 5%4 is 1, 6%4 is 2. So the initial values of m1, m2 and m3 are 2, 2, and 1 respectively, representing the scores after the first roll.
If you add 1 to any number that is 1%4, the result is 2%4. Add 2 to a number that is 1%4 and the result is 3%4. And so on...
So, on each subsequent roll, since every time the die can come up only 1,2,3,4,5, or 6, the NEXT m1 score will be equal to the sum of the previous roll's m1 score, plus the previous roll's m2 score, plus twice the previous roll's m3 score. Similarly, you can calculate the next roll's m2 score and m3 score, and the number of "awins" cases for the next roll.

Each time through the loop represents the 2nd through the last roll. First it computes the sum of the PREVIOUS roll's cases to be used for the to calculate the probability that nobody has already won. Then it computes the number of cases in terms of %4 scores (that's "m1next, m2next, etc) for the current loop. Then it computes the probability that nobody won already by multiplying the probability that they didn't win 2 rolls ago by the probability that they didn't win on the last roll. (Sorry, my comment about b and "bprob" are misleading. bprob = (5/6)^2 is the probability that NOBODY won on the first round. (5/6)^2*(22/30)^2 is the probability that nobody won the second time, etc.)

Finally, it computes A's CONDITIONAL probability for the current roll by dividing the favorable cases "awnext" by the total cases "sumnext", multiplying by the probability that nobody has won yet [that's the CONDITION], and adds it to A's previous cumulative probability of winning.
Finally, it updates the values of m1,m2,m3, and awins to pass on to the next iteration.

I hope that makes it clear.

Joel

By Arun Iyer on Sunday, December 22, 2002 - 08:28 am:

Joel,
when you say "m1,m2,m3 represent the scores,i think you mean 'm1 represents the number of ways to get 1','m2 represents the number of ways to get 2','m3 represents the number of ways to get 3' after taking the (sum mod 4)"

if what i think is right,then i think i understood your program.Nice idea of calculating the bprob BTW!

love arun

By Joel Kammet on Sunday, December 22, 2002 - 04:19 pm:

Yes, you got it. That's exactly what I meant.