ECE 1011 - Summer 2003
HOMEWORK #3 - The Monty Hall Problem
(Last Modified: 04 Nov 2010 )
In this assignment, you will simulate one of the classic probability and statistics problems loosely taken from the old TV game show "Let's Make a Deal" hosted by Monty Hall. In this simplified version of the game, the contestant is presented with three doors and informed that behind one of the doors is a wonderful prize (a new car) while behind the other two is a lousy price (a goat). The contestant is allowed to choose one of the doors. Then Monty opens one of the remaining doors and reveals one of the two goats. The contestant now knows that of the two remaining doors one hides the other goat while the other has the car. Monty now gives the contestant the option to stick with the door they originally chose or to switch their selection to the other door. After the contestant makes their decision, the doors are opened and the contestant gets whatever is behind the door they finally settled on.
The question you will try to answer with this program is whether the contestant can improve their odds by switching doors after the first door is opened by Monty. In particular, does switching doors improve their odds of winning, decrease their odds of winning, or leave their odds of winning unchanged?
BTW: "Winning" is defined as getting the car, not the goat.
You could solve for the probabilities explicitly - and for this problem it is quite straightforward - but another way to answer the question is to write a computer program that simulates the game where you randomly make every possible decision (subject to the constraints of the games rules). You then tabulate what percentage of the time the contestant won when they switched and what percentage of the time they won when they didn't switch and compare the results.
Your program should prompt the user for the number of times that the game should be played. In order for the results of the simulation to approach the theoretical probabilities, you will want to let the user enter a rather large number, say 100,000 or even several million (though it will converge to the correct results for a much smaller number than this). You need to decide what variable types to use and inform the user of any resulting constraints on their choice.
Consistent with the Top-Down (divide and conquer) approach, break this problem into smaller components. Let's work the first few levels (keeping in mind that there are many ways to do this and you are in no way required to use the one below).
Initial Decomposition Outline:
Get the total number of games to be played.
Play a single game, noting whether the player switched and whether the player won.
Continue playing games until the required number have been played.
Calculate the probability of winning if you always switch your selection.
Display the results.
Clearly, the key step is being able to play a single game (Item 1.1), so let's break that down further:
Randomly place the CAR behind one of the doors.
Place GOATS behind the other two doors.
Let the user pick any of the three doors as "their" door.
Reveal one of the "other" doors so as to reveal one of the goats.
Give the user the opportunity to change from "their" door to the "remaining" door.
Reveal whether their final door has the CAR or the other GOAT.
One of the goals of this assignment is to utilize modularity - so you are expected to write your main and your more complicated functions so that they are very short and very readable. For instance, your main might look something like this:
int main(void)
{
long int game, games;
int WillSwitch, Winner;
long int Switched, SwitchedAndWon, StayedAndWon;
games = GetNumberOfGamesToPlay();
Switched = SwitchedAndWon = StayedAndWon = 0;
for(game = 0; game < games; game++)
{
WillSwitch = rand_int(0,1);
Winner = PlayMontyHall(WillSwitch);
if(WillSwitch)
{
Switched++;
if(Winner)
SwitchedAndWon++;
}
else
{
if(Winner)
StayedAndWon++;
}
}
DisplayResults(games, Switched, SwitchedAndWon, StayedAndWon);
return(0);
}
You can probably figure out what the above code does, and what each of the invoked functions needs to do, in the above program even though not a single comment has yet been added. Furthermore, notice that main() has been completely written (though there is always the chance that it will need to be revised later) even though there are four key functions that have not been written. But now the remaining tasks are very clear - write those four functions! And the I/O has already been defined for them. So now each of those functions could be assigned to a different team who could go off and develop those functions in parallel as their own specific subproblems. Three of those probably do not need to be broken down any further, but the second iteration of our Decomposition Outline above shows that the PlayMontyHall() function should probably be further broken down, in a fashion similar to how main() was done, until you get to simple, easy to implement tasks.