• TheThreeGoatsII

Goats the second

Under construction

The Approach

I have just applied this approach to your Goats problem and I think it makes the solution obvious and allows a non looping simulator to be written that only relies on simple arithmetic on boolean vectors.

The logic in the form of a type of truth table goes as follows:

The full truth table of all possible outcomes is:

1 0 0
0 1 0
0 0 1

When the contestant makes his choice (first row) he has the following pattern of possible outcomes:

1 0 0

i.e. he has one chance of guessing right and two of guessing wrong so he has a 33% chance of winning the star prize.

After he has made his choice this determines the pattern (second two rows) that passes on to the game show host to be:

0 1 0
0 0 1

Now the host knows which box contains the star prize and is subject to two very important constrains: he cannot open the box the contestant has chosen nor the box containing the star prize. So in his pattern he must now remove a zero from the outcome (column) consistent with the contestant's guess. Doing so leaves the following pattern of possible outcomes which can be passed back to the contestant which he can now choose to accept or stick with his original guess:

0 1 1

and the truth table after the host's choice reduces to:

1 0 0
0 1 1

So now you can see that the pattern he can switch to (the second row) has two chances of being correct (67%) whereas his original guess (the first row) only has a one in three chance. Hence the result people find counter intuitive. Clearly when making his selection in the case where the contestant guesses correctly the host has two rather than just the one box (zero) to choose from but to the contestant the outcome is independent of the host's choice because the outcome is the same if he switches i.e. he loses.

Choosing to switch at random simply yields an average of the one in three and two in three outcomes i.e. one in two or 50%.

I have coded a simulator based on the above logic in basic apl with no requirement for looping and only using very simple arithmetic on boolean vectors. I have attached a copy in a text file in the standard Dyalog font so hopefully if you open it with NoteBook say, and set the font to Dyalog std you should be able to read it. The right argument is simply the number of simulations. To see how it works simply output the result of each line to the screen with the right argument set at 10 say or make the internal variables global rather than local and inspect them.

     Goats 1000000
 33.3 66.7 50.0

The Code

 r←Goats n;c;g;h;s;sr;pv;ng;ns;nsr
⍝Correct door number
 c←(⌈(3÷n)×n?n)⌽¨⊂1 0 0

⍝Contestant's guess
 g←(⌈(3÷n)×n?n)⌽¨⊂1 0 0

⍝Doors that cannot be opened by the host
 h←×c+g

⍝Doors the contestant can switch to if he always switches
 s←h-g

⍝Doors selected if the contestant switches at random
 sr←(s×~pv)+(pv←⌊0.5+(÷n)×n?n)×g

⍝Number of original guesses correct
 ng←(+/3=+/¨c=¨g)

⍝Number of switches correct
 ns←(+/3=+/¨c=¨s)

⍝Number of random switches correct
 nsr←(+/3=+/¨c=¨sr)

⍝Probabilies of for each outcome
 r←1⍕(100÷n)×ng,ns,nsr

The following function does exactly the same thing but is optimized for speed. Following the logic is a bit harder, but it's much faster:

r←Goats2 n;c;g;h;s;sr;pv;ng;ns;nsr
⍝ Improved version

⍝Correct door number
 c←(⌈(3÷n)×n?n)⌽(n,3)⍴1 0 0

⍝Contestant's guess
 g←(⌈(3÷n)×n?n)⌽(n,3)⍴1 0 0

⍝Doors that cannot be opened by the host
 h←×c+g

⍝Doors the contestant can switch to if he always switches
 s←h-g

⍝Doors selected if the contestant switches at random
 pv←⌊0.5+(÷n)×n?n
 sr←(s×[1]~pv)+pv×[1]g

⍝Number of original guesses correct
 ng←(+/3=+/c=g)

⍝Number of switches correct
 ns←(+/3=+/c=s)

⍝Number of random switches correct
 nsr←(+/3=+/c=sr)

⍝Probabilies of for each outcome
 r←1⍕(100÷n)×ng,ns,nsr

Author: GrahamSteer