As stated in the problem, the game of fifteen is equivalent to random
tic-tac-toe except in the winning conditions. The transformation is
equivalent to numbering the tic-tac-toe board as a magic square. There
are eight combinations of three numbers from the set one through nine
which add to 15, precisely matching the lines in the magic square and the
tic-tac-toe game.
While the games actually end as soon as somebody gets a winning triple,
if carried out to fill the board, there would be 9! = 362880 possible games.
Games that end before the eighth move are more likely end states than others,
since there is more than one of the 9! full-board games corresponding to this
position. However, the final answer will be in the form N/9!, where N is an
integer.
I will analyze the results by looking at the full-board tic-tac-toe games,
and determining the number of Fifteen games which lead to each, including
(for those final states which have winning triples for both players) how
many games lead to wins for each player.
For any given final board, such as:
BAA
AAB
BBA
There are 5! ways of arranging A's moves, and 4! independent ways of
arranging B's moves. Thus, there are 5!*4! = 120*24 = 2880 games of
Fifteen which correspond to this filled tic-tac-toe board. In addition,
there are up to 8 rotations and reflections of each board, which multiply
this number further (to 23040 games for the board above).
There are 3 full tic-tac-toe boards (distinct to rotations and reflections)
which contain no winning line for either player. These are:
BAA
AAB (8 rot/ref)
BBA
ABA
BBA (4 rot/ref)
AAB
BAB
ABA (4 rot/ref)
ABA
These give 16*2880 = 46080 games of Fifteen in which neither player gets a
winning triple, and as a result B wins.
There are several full tic-tac-toe boards where only one player gets a
winning line. These are wins for A:
AAA
BBA (4)
BBA
AAA
BAB (4)
BAB
BAB
AAA (1)
BAB
AAA
BAB (8)
BBA
AAB
BAA (4)
BBA
AAB
BAB (4)
BAA
AAB
AAB (4)
BBA
AAB
BAB (8)
ABA
ABA
BAB (1)
ABA
AAA
ABB (8)
BAB
AAA
ABB (8)
BBA
ABB
AAA (8)
BAB
(Total 62)
And these for B:
BAA
ABA (4)
BAB
BAA
BBA (8)
AAB
(Total 12)
This gives 62*2880 = 178560 games of Fifteen that win for A, and
12*2880 = 34560 games for B.
These filled tic-tac-toe boards contain winning lines for both players.
There can only be one line for each player, since two crossing lines for A,
in any configuration, prevent B from getting a line, and B doesn't get
enough plays to make two lines.
AAA
BBB (8)
AAB
AAA
BBB (4)
ABA
AAA
BAA (8)
BBB
AAA
ABA (4)
BBB
BAA
AAA (8)
BBB
ABA
AAA (4)
BBB
(Total 36)
This gives 36*2880 = 103680 games that may lead to a win for either A or B.
Each set of 2880 has the same number of A wins and B wins, since only the
order that the 6 numbers in the two winning lines occur matters.
When the first three moves for A are the winning line (12/120), A wins.
When the fifth move for A is part of the winning line, B wins (72/120).
When the last of the winning line is A's 4th move (24/120), A wins unless
B's winning line occurs in his first three moves (6/24). (So A wins this
way 18/120 times and B wins this way 6/120 times.)
Thus, A's overall chances of winning these cases is 30/120, or 1/4.
So, A wins 25920 of these cases and B wins 77760 of them.
This gives us a total of 178560 + 25920 = 204480 cases where A wins, and
46080 + 34560 + 77760 = 158400 of the 362880 total cases.
Bet on A.
Joseph DeVincentis
----------------------------------------------------------
Hi, Ed.
Concerning the problem proposed by Sudipta Das, it seems that, among the
255168 possible matches:
- 131184 times the match stops because A getts three balls totalling 15;
- 77904 times the match stops because B getss three balls totalling 15;
- 46080 times no one gets a winning triple.
Thus player A wins 51.41%
Ciao, Claudio Baiocchi.