Programming and Computer Science in Java:
Homework #11:  More Random Numbers
    David Kosbie, 2002-2003
See Course Home Page

Due Date:  Mon, Mar 24, 2003

Reminder:  There is a quiz on Mon, Mar 24, covering Methods, Doubles, Math Methods, Strings, and Randoms.

Question 1:  Write a Java program which determines the probability (output as a percentage) of rolling two six-sided dice twice and coming up with the same sum on both rolls.  So, rolling 2,3 and then 1,4 would be a success, as they both sum to 5.  Your program should take the number of trials (ie, experiments) to run as the sole input.  If you can, explain this result using mathematics.

Question 2:  The NCAA basketball tournament includes 64 teams ranked #1 through #64.  Say that when a team ranked r1 plays a team ranked r2, the odds that the first team wins are:

r2 / (r1 + r2)

Naturally, then, the odds that the second team wins are:

r1 / (r1 + r2)

So, if the team ranked #3 played the team ranked #13, the odds that the first team wins are 13/(3 + 13), or 13/16, and the odds that the second team wins are 3/(3 + 13), or 3/16.

With 64 teams, in the first round, the pairings are:

Notice that the sum of the rankings of each pairing are always 65.  This is always true in the first round of a 64-team tournament.

Now, say that all the favored teams actually win the first round.  Now, in the second round, we have 32 remaining teams, and the pairings are:

Notice that the sum of the rankings of each pairing here are always 33 (which is 32+1).

Again, assuming all the favored teams always win, then the sum of the rankings in each pairing in the third round would be 17 (16+1), in the fourth round would be 9 (8+1), in the fifth round would be 5 (4+1), and in the sixth and final round would be 3 (2+1).

But what do we do if there is an upset?  That is, if a team with a lower ranking defeats a team with a higher ranking?  In that case, the winning team assumes the seed of the defeated team, at least for the purposes of selecting the next opponent.  So if a team ranked #12 defeats a team ranked #5, then in the next round the team ranked #12 would play whoever the team ranked #5 would have played.  Note, though, that the team is still ranked #12 when computing the odds of it winning its next game. 

Now, write a Java program which reads in a team ranking in the range [1,64].  Your program will print out the worst-case odds, as a percentage, that that team will win the tournament.  To compute these odds, take the product of the odds for that team winning every game it plays (how do you determine those odds?  By the method described above.).  As for the opponents, assume that in all other games, the favored team always wins.

Thus, if the input is 57, meaning we are dealing with the team ranked #57, then its first game will be against team 8 (because their sum must be 65), and the (slim) odds of winning the first game are:

8 / (8 + 57)

If they win, who do they play next?  Because this was an upset (they defeated a team with a higher ranking), they play the team that team (that is, the team ranked #8) would have played next.  In the second round, with 32 teams remaining, the sum must be 33, so the opponent would be team 25, and the odds of winning this second game are:

25 / (25 + 57)

If they win that game, who do they play next?  Even though this was an upset, they are being seeded as though they are #8 now, and this is already higher than #25, so they continue being seeded as though they are #8 now.  So their next game, with 16 teams remaining, is against the team summing to 17, which is team #9, and the odds of winning this third game are:

9 / (9 + 57)

If they win that game, they remain effectively #8, and their next game, with 8 teams remaining, is against the team summing to 9, which is team #1 (yikes), and the (very remote) odds of winning this fourth game are:

1 / (1 + 57)

If they win that game, they now have defeated a team ranked higher than #8, so they assume this new seed (#1) for determining their opponent.  Now, with 4 teams remaining, their next game is against the team summing to 5, which is team #4, and the odds of winning this fifth game are:

4 / (4 + 57)

Finally, if they win this game, they remain effectively #1, and their next and final game, with only 2 teams remaining, is against the team summing to 3, which is team #2, and the odds of winning this sixth and final game are:

2 / (2 + 57).

So, the final answer is the product of these six odds, or:

8 / (8 + 57) * 25 / (25 + 57) * 9 / (9 + 57) * 1 / (1 + 57) * 4 / (4 + 57) * 2 / (2 + 57).

These are very, very small odds indeed.

After you write your program, include a comment in the program where you consider if this is a vaguely accurate method for estimating the likelihood of a team winning the tournament based on its seeding.  If you think not, then come up with a better method (and explain why it's better), and include a separate program demonstrating that method.

Good luck!

DK


See Course Home Page