My next topic is a complicated game of tic-tac-toe, with the cool twist that its played in an infinite triangle, and its a game not between two wits but between a humble mathematician and the ultimate opponent, mathematics itself (dah dah dah! [foreboding musical number] Okay, bit of an anticlimax, sorry). A-a-a-ny-who, back to what I was saying, the subject matter this time round is a problem in which a certain rule is applied a number of times to a set of naughts and crosses, the problem being to determine the end result without working out the next line in the sequence.
The sequence in question begins with a row of any number of X's and O's. The next line is then constructed with one less of these, each being the result of the two above them. If a symbol's genesis is two parents of the same denomination, the child is an O (i.e. O + O --> O, X + X --> O). If the parents are different, the child is an X (i.e. O + X --> X, X + O --> X). Each new line is thus produced until the last, with one child, is reached. Thus a typical arrangement might be any of the following:
OOX XOXXO XOOXXOXOXOOXO
OX XXOX XOXOXXXXXOXX
X OXX XXXXOOOOXXO
XO OOOXOOOXOX
X OOXXOOXXX
OXOXOXOO
XXXXXXO
OOOOOX
OOOOX
OOOX
OOX
OX
X
The question of what the end result will be for a given first row can be overcome with a little logical reasoning and an extra dose of cunning. Firstly, we can take a look at what will happen with an initial row of three. Here are the eight possibilities:
XXX XXO XOX XOO OXX OXO OOX OOO
OO OX XX XO XO XX OX OO
O X O X X O X O
As you can see, if the two outer symbols are the same, the result is an O, and otherwise it is an X. This is because if they are the same they will react in the same way with the centre parent, producing two children that are the same and those will then produce an O. If they are different, they will react differently with the centre and by the same reasoning produce an X. So wherever there appears a row of three, the child two rows down will be exactly as if the two outer parents of the triplet directly parented the child. Now we can look at the arrangement with five in the first row. Let's pick an arbritary arrangement:
\XO\X/XO/
\XX/\OX/
\O/X\X/
"I think I'll stop there." Only because this is all we need. You'll notice I have marked in two overlapping sets of three. Here the two outer parents of a set of three are determined by the two outer parents and the centre parent of a set of five. By the same reasoning as for the set of three, we can show that the end result of a set of five will depend only on the outer symbols as parents. In the same way we can split a set of nine up as a set of five over the top of a set of five, and a set of thirteen will be a set of seven over a set of seven and so on for all odd numbers of the form 1 + 4k (where k is a positive integer). If the set begins with an even number of the form 2(2k + 1), we only need to work out the two outer children of the next line, and then the end result will be clear. For an odd number of the form 3 + 4k, an arrangement can be found that will end with something like this:
\XOXO\OXX/OXOO/
In this way two parents can be determined by inspecting the child of the first symbol and the symbol one place to the right of the middle, and the child of the last symbol, and the symbol one place to the left of the middle. Now, for the case of a set of even number of the form 4(k + 1), the outer parents of the row down, and the child of the two symbols on the right of the middle line, and the child of the two symbols on the left of the middle line, and then the end result can be achieved as above.
No comments:
Post a Comment