|
Some ideas:
Let's ssuppose our algorithm A starts at the corner, i.e. (1,1,1,...1)
How many paths to win we can create with a corner opening?
For dimention 2x2, we have 3 ways
(1,1)-(1,2) two straight edges
(1,1)-(2,1)
(1,1)-(2,2) one diagonal
For dimeion 3, we have
(1,1,1) (2,1,1) (3,1,1) 3 straight edges
(1,1,1) (1,2,1) (1,3,1)
(1,1,1) (1,1,2) (1,1,3)
(1,1,1) (1,2,2) (1,3,3) 3 semi diagonals on planes
(1,1,1) (2,1,2) (3,1,3)
(1,1,1) (2,2,1) (3,3,1)
(1,1,1) (2,2,2) (3,3,3) 1 full diagonals
For dimention 4, we have
(1,1,1,1) (2 111) (3 ...) (4 ...) 4 straight edges
(1,1,1,1) (1 2 1 1) (.3..) (.4..)
(1,1,1,1) (1 1 2 1) blah
(1,1,1,1) (1 1 1 2) blah
And?
And?
And?
|
The question I want to answer is, given a "string" of length n, say
(pt1, pt2, pt3, ... ptn)
What kind of string is a "winning string"?
Remark:
Note that each pt_i looks like (a1, a2, ... an), that's to say each point is a n-tuple, and a string is a n collection of these n-tuple points.
For instance, a winning string in 3D might look like
((1,1,1), (2,2,2), (3,3,3))
Once we collectively answer that question, we will see that out of ALL the winning strings, which one can player_1 claim in such way that player 2 cannot block.
Again, we'll formalize our terms, build on top of hixhix, I add this one more definition:
a winning string is a collection of points in which, once all points are claimed by one player, he wins.
|
Some intuition:
2D has total of 4 points, Since any 2 points in 2D forms a winning string, total number of winning string will be (4 choose 2) or 6.
3D has total of 27 points, how many winning strings are there?!
4D, 5D?
HAhAH this is already fun!
Cmon play with me here
|
On June 04 2009 08:12 Muirhead wrote:Some google searching shows that this problem has been studied and is very hard. I'm no longer at all certain that draws are impossible for large n. http://en.wikipedia.org/wiki/Hales-Jewett_theorem is an interesting theorem regarding this problem, though a combinatorial line is a little less common than an ordinary tic-tac-toe line. The Hales-Jewett number seems to grow rapidly, which is a very bad sign. It is likely that the problem is complicated enough that a proof is impossible.
For other people working on this, I'll like to emphasize Muirhead's post. Note that OP does not claim to know that answer, only that he played around with the cases n=4 and 5.
@evanthebouncy!
Well, a winning string in one such that for each coordinate the pt_i_n (i is varying, n is fixed) are counting up from 1 to n, counting down from n to 1, or is constant. This is because if you project a winning string to a single axis, it must appear as one of three cases above. Conversely, a string whose projection to every coordinate is as above must be a winning string.
edit: note that we cannot have every coordinate constant. As long as one coordinate is varying it is fine.
edit2: The number of strings in n dimension TTT is 1/2 times (n+2)^n - n^n. This checks with the 3 dimensional case in the OP.
|
On June 04 2009 11:20 datscilly wrote:Show nested quote +On June 04 2009 08:12 Muirhead wrote:Some google searching shows that this problem has been studied and is very hard. I'm no longer at all certain that draws are impossible for large n. http://en.wikipedia.org/wiki/Hales-Jewett_theorem is an interesting theorem regarding this problem, though a combinatorial line is a little less common than an ordinary tic-tac-toe line. The Hales-Jewett number seems to grow rapidly, which is a very bad sign. It is likely that the problem is complicated enough that a proof is impossible. For other people working on this, I'll like to emphasize Muirhead's post. Note that OP does not claim to know that answer, only that he played around with the cases n=4 and 5. @evanthebouncy! Well, a winning string in one such that for each coordinate the pt_i_n (i is varying, n is fixed) are counting up from 1 to n, counting down from n to 1, or is constant. This is because if you project a winning string to a single axis, it must appear as one of three cases above. Conversely, a string whose projection to every coordinate is as above must be a winning string. edit: note that we cannot have every coordinate constant. As long as one coordinate is varying it is fine. edit2: The number of strings in n dimension TTT is 1/2 times (n+2)^n - n^n. This checks with the 3 dimensional case in the OP.
That is correct, I do not know of a solution. I talked with another math-bent friend who believes it is unprovable, but isn't certain.
|
|
|
|
|
|
EPT
