Tic tac toe
Probability
Level
5
What is the number of ways a tic tac toe game can be ended with a draw?
Note : Either 'O' or 'X' can start first.
The answer is 32.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
<?php
//treat 0 as 'O' and 1 as 'X' in this case (or vice versa, doesnt really matter)
$arr = array(0,1);
do{
$newarr = array();
foreach($arr as $a){
if(substr_count($a,'0')<5){
$newarr[] = $a.'0';
}
if(substr_count($a,'1')<5){
$newarr[] = $a.'1';
}
}
$arr = $newarr;
} while(strlen($arr[0])<9);
echo '<pre>'.print_r($arr,true).'</pre>'; //prints all possible combinations of strings length 9 with no more than five 0's or 1's in any game
$c = 0;
foreach($arr as $a){
if(
($a[0]==$a[1] && $a[0]==$a[2]) || //across top
($a[3]==$a[4] && $a[3]==$a[5]) || //across middle
($a[6]==$a[7] && $a[6]==$a[8]) || //across bottom
($a[0]==$a[3] && $a[0]==$a[6]) || //down left
($a[1]==$a[4] && $a[1]==$a[7]) || //down middle
($a[2]==$a[5] && $a[2]==$a[8]) || //down right
($a[0]==$a[4] && $a[0]==$a[8]) || //diag down
($a[6]==$a[4] && $a[6]==$a[2]) //diag up
){
//ignore if we find 3 in a row of any kind
continue;
}
$c++;
echo $a.'<br>'; //prints each unique string with no winners
}
echo 'answer: '.$c; //prints 32
?>