EPTAnswer:+ Show Spoiler +
bout tree fiddy
Math Problem - Page 2
| Forum Index > General Forum |
|
cz
United States3249 Posts
Answer:+ Show Spoiler + | ||
|
outqast
United States287 Posts
On May 29 2009 08:17 hixhix wrote: So let's do an example. First player picks the corner (1, 1, 1). Consider the 2-dimension grid (1, x, y), now there are 3 possible winning positions for player 1. Second player picks (1, 1, 2), then what happens next? I know the strategy for first player to win, but I fail to see how it reduces to 2x2 grid game. I may be misinterpreting a winning strategy, but I think any time when you have n adjacent units together in an n TTT game you win. The way I'm envisioning the problem: Start in dimension 1 (in this case your z) Since in every dimension you can always adjoin two squares together no matter your starting strategy (i.e. you "win" in that dimension). The optimal choice could be a number of things for the sake of argument, suppose you chose (1,2,2) Once you "win" that dimension, by definition you can also win in the next dimension (lets say the x dimension). Suppose the opposing player chooses (1,3,3). You can win the x dimension, by choosing any adjacent square in the x-dimension adjacent to (1,1,1) suppose you chose (2,1,1) You then have a string of (2,1,1), (1,1,1), and (1,2,2). I think this is problem is isomorphic to just playing the (2x2) game over and over again, and asking whether you can win every time. However, I might be misinterpreting a winning strategy. | ||
|
jeppew
Sweden471 Posts
edit: i think you're on the right track though, proof by induction seems to be the correct way to do it. | ||
|
outqast
United States287 Posts
On May 29 2009 09:32 jeppew wrote: but if you think of it as winning in the N=2 game over and over again you miss the that let's say in N=4 you win in the corner, then the next move is your oppononets, thus it's not a string of 2x2 games where you start and can apply the same strategy. edit: i think you're on the right track though, proof by induction seems to be the correct way to do it. I think I may have been a little vague about the last statement. If one views the battle to win each dimension as a repetition of the 2x2 game, then it is isomorphic. Which essentially is the induction proof. | ||
|
hixhix
1156 Posts
On May 29 2009 09:13 outqast wrote: .... Since in every dimension you can always adjoin two squares together no matter your starting strategy (i.e. you "win" in that dimension).... .... This is so wrong. As I said before, the second player can choose to play any where, he's not forced to play within the reduced space as assumed in many posts here. For example, assuming the 4^4 space, the first player chooses (1, 1, 1, 1), then second player chooses (3, 2, 4, 4), those belong to disjoint spaces (there exists no space that contain a valid row (length 4) and contain both points) and from the point of view of the second player, he becomes the "first player" to play in his space. I'm not saying that there is no winning strategy for the first player, I'm saying that the argument has been dicussed so far saying that n-dimension space can be reduced to (n-1)-dimension space is incorrect. | ||
|
outqast
United States287 Posts
On May 29 2009 10:08 hixhix wrote: This is so wrong. As I said before, the second player can choose to play any where, he's not forced to play within the reduced space as assumed in many posts here. For example, assuming the 4^4 space, the first player chooses (1, 1, 1, 1), then second player chooses (3, 2, 4, 4), those belongs two completely different spaces and from the point of view of the second player, he becomes the "first player" to play in his space. I'm not saying that there is no winning strategy for the first player, I'm saying that the argument has been dicussed so far saying that n-dimension space can be reduced to (n-1)-dimension space is incorrect. It is the ability to "win" in that dimension, i.e. adjoin two units together, not the ability to play in the dimension. By the nature of the game, once you have started playing you have "played in all of the dimensions." Note: There are a vast amount of winning strategies from any point in the game. They have just identified one that works. | ||
|
hixhix
1156 Posts
Problem: Given an n-dimension space, a valid point X in this space is represented by n coordinates X(a1, ..., an) where 1 <= ai <= n for all i from 1 to n. A valid row is a set of n points X1, ... Xn where each Xi is a valid point and Xi = X1 + (i-1) * V, V is an n-dimension vector V(v1, v2, ..., vn), vj = 0 or 1 for all j, and there is at least one non-zero vj. Assuming there is an algorithm A that allows the first player to choose points forming a valid row in a (n-1)-dimension space, prove that first player can use A to choose points forming a valid row in an n-dimension space. ... Let's play with a small space (3-dimension), you're the first player and you have the algorithm A, I'm the second player. Can you step by step show me how the first player *use* A to choose a valid row of 3 points. (algorithm A guarantees that you can choose a valid row of size 2 in a 2-dimension space). First player picks the corner (1, 1, 1). Second player (me), picks (1, 1, 2). Now, what's your next move (based on algorithm A & your reduction protocol) ? | ||
|
toopham
United States551 Posts
On May 29 2009 10:40 hixhix wrote: I guess there is a big misunderstanding. Let's formalize the problem and all definitions and so it's easier to discuss. Problem: Given an n-dimension space, a valid point X in this space is represented by n coordinates X(a1, ..., an) where 1 <= ai <= n for all i from 1 to n. A valid row is a set of n points X1, ... Xn where each Xi is a valid point and Xi = X1 + (i-1) * V, V is an n-dimension vector V(v1, v2, ..., vn), vj = 0 or 1 for all j, and there is at least one non-zero vj. Assuming there is an algorithm A that allows the first player to choose points forming a valid row in a (n-1)-dimension space, prove that first player can use A to choose points forming a valid row in an n-dimension space. ... Let's play with a small space (3-dimension), you're the first player and you have the algorithm A, I'm the second player. Can you step by step show me how the first player *use* A to win. (algorithm A guarantees that you can choose a valid row in a 2-dimension space). First player picks the corner (1, 1, 1). Second player (me), picks (1, 1, 2). Now, what's your next move (based on algorithm A & your reduction protocol) ? Calling each dimension x,y, and z So you picked (1,1,2) which is the z dimension, Thus I will use my A algorithm on dimension x and y at point (1,2,1) Thus I have 2. You are force to go (1,3,1) or else I will win. Now I will use my A algorithm on dimension y and z so I go (1,2,2) You are force to go (1,3,3) to stop me from forming a diagonal on the y and z dimension. Now I go (1,2,3) and I win. I have (1,2,1) ( 1,2,2) and (1,2,3) By using my A algorithm I control where you move next because You are force to go there to stop me. Thus I basically control your every move after your first move. | ||
|
hixhix
1156 Posts
On May 29 2009 10:57 toopham wrote: Calling each dimension x,y, and z So you picked (1,1,2) which is the z dimension, Thus I will use my A algorithm on dimension x and y at point (1,2,1) Thus I have 2. You are force to go (1,3,1) or else I will win. Now I will use my A algorithm on dimension y and z so I go (1,2,2) You are force to go (1,3,3) to stop me from forming a diagonal on the y and z dimension. Now I go (1,2,3) and I win. I have (1,2,1) ( 1,2,2) and (1,2,3) By using my A algorithm I control where you move next because You are force to go there to stop me. Thus I basically control your every move after your first move. First, in the reduced space, it's only 2x2, if you just said xy- at (1, 2, 1), it's 2-dimension space of size 3x3. Please specify what the reduced space is. Anyway, you can ignore that because the example was the intention, the second player chooses the point in the same space with the first player. How about this: First player: (1, 1, 1) Second player: (1, 2, 2) And when you reduce to the trivial case, please specify 2-dimension space of size 2x2 . | ||
|
toopham
United States551 Posts
On May 29 2009 11:11 hixhix wrote: First, in the reduced space, it's only 2x2, if you just said xy- at (1, 2, 1), it's 2-dimension space of size 3x3. Please specify what the reduced space is. Anyway, you can ignore that because the example was the intention, the second player chooses the point in the same space with the first player. How about this: First player: (1, 1, 1) Second player: (1, 2, 2) And when you reduce to the trivial case, please specify 2-dimension space of size 2x2 . For the first example my winning diagonal was in the 3x3 of the y and z plane with x=1. your move (1,2,2) stopped me from winning in the y and z 3x3. So now I will just do the same strategy but I will use it on the x and y plane with z=1. IF I go (2,1,1) i create a row of 2. The reduced space is the 2x2 of the x and z or x and y. Either one works, you pick. But I will go (2,2,1) So that it's obvious the reduced space is x and y. You are forced to go (3,3,1) to stop me So I go (1,2,1) Now you go (1,3,1) to stop me from winning. Now I go (3,2,1) to win I have (2,2,1) (1,2,1) and (3,2,1) | ||
|
hixhix
1156 Posts
Also, there is no guarantee that a valid row in a (n-1)-dimension space can lead to a valid row in n-dimension space. For example, assuming the following is a 2-dimension cut from a 4-dimension space o o x o o x o o x o o o o o o o "x x x" is a valid row in the 2-dimension space of size 3 but it can't lead to a valid row in 2-dimension of size 4. Anyway, I guess we cant agree, let's relax. | ||
|
mmp
United States2130 Posts
+ Show Spoiler + This problem hinges on whether or not it is possible for the game to draw. Case 1: A draw is possible for all n. Case 2: A draw is possible for some n. Case 3: A draw is impossible. Credit to Muirhead for intuition regarding the third case: + Show Spoiler + Assume that Ben (who plays second) has a winning strategy. Alyssa plays first in any location, and subsequently will play out Ben's strategy as though she were second to play. Any time Alyssa's strategy would require a move in a place she already owns, she simply takes another arbitrarily since she already owns the location mandated by her strategy. By deferring the initiative Alyssa steals Ben's strategy, thus forming a contradiction. By this contradiction Ben cannot have a winning strategy if a draw is impossible. A subtle point: Alyssa's first move does not jeopardize the strategy she stole from Ben, since it does not lend Ben any stronger of a strategy. Alyssa loses no options by making this move, although her opponent is weakened. Intuition says that case 3 is reality, but a proof is still necessary. Can you think of a clean or elegant way of showing that a completely filled n-TTT board must contain an n-in-a-row? (I am trying to prove this myself at the moment). | ||
|
opsayo
591 Posts
On May 29 2009 07:29 Macavenger wrote: + Show Spoiler + This is probably going to be worded fairly poorly, because I'm kinda bad at formal mathematical proofs, but here goes anyway: Proof by induction: Assume that there exists a winning strategy for (n-1)-TTT for the first player. This means that the first player can force a string of length n-1 in n-1 dimensions, creating the immediate threat of a length n string in the (n-1)th dimension, which his opponent must immediately block or he will lose the game. The player can then apply this strategy in each of the (n-1)th dimensions making up the nth dimension. Eventually by filling up the nth dimension with the (n-1) winning strategy, he will be able to force a win in the nth dimension, as the opponent will be unable to block him from winning both in the (n-1)th (n-1)th dimension, and in the nth dimension simultaneously. There is a winning strategy for n=2, as detailed in the original post: Taking any corner on the first move creates 3 possibilities to win on the next move, only 1 of which can be blocked by the opponent. Since a winning strategy exists for n=2, and we have shown that a winning strategy for n-1 implies a winning strategy for n, there is a winning strategy for all n. QED. I disagree with this, maybe this is the right approach, but as I see how it is worded, I don't think this is a conclusive proof. Let's say we have a winning strategy in the n-1 dimension, that means we have a string of n-1 length in an n dimensioned TTT game. However, it is now the second players turn to make a move, and can immediately "corner" off the n-1 length string (since all the strings are only 1 dimensional), thus negating the n-1 length string which would have won in an n-1 TTT game, but is now blocked in an n dimensioned game. edit: Let's say you're in the very first n-1th x n-1th dimension, trying to force an n-1 string. Since you have assumed in the induction step that you can indeed do this, you force a string of n-1. However, he goes second and blocks it, while you start the next iteration in the next n-1th x n-1th dimension. You go first, but you went first in the first iteration as well, and makes no difference. In order to succeed, you need to force two threatening strings simultaneously. That is in order to succeed in the n-1 dimension TTT game, you are forcing two n-2 dimensional strings. To win in an n-dimensioned game you need to force two n-1 strings simultaneously, which I don't think you can do with this approach. This is also why I don't think all cases are simply analogous to the base case(s). In a 1 dimensional game, your first move forces a win, but before you've won, you have threatened with 1 possible win condition. In a 2 dimensional game, your first move threatens 3 possible win conditions. In a 3 dimensional game, it takes a few moves (do it in your head), but your final win condition comes out to threatening only 2 win conditions. I imagine following this step, the rest of them threaten only 2 simultaneous conditions. On May 29 2009 10:24 outqast wrote: It is the ability to "win" in that dimension, i.e. adjoin two units together, not the ability to play in the dimension. By the nature of the game, once you have started playing you have "played in all of the dimensions." Note: There are a vast amount of winning strategies from any point in the game. They have just identified one that works. You are missing their point. Winning in a smaller dimension successfully does not ensure that win condition will remain viable following your opponent's turn. If you successfully connect 2 in a 2x2 dimension, your opponent can immediately block it in a 3x3 dimensioned game, leaving your entire win condition from the 2x2 game useless. | ||
|
opsayo
591 Posts
| ||
|
Wr3k
Canada2533 Posts
 Macavenger seems to have it down. I'm not sure that can be considered an actual proof though. It's been a while since I did any kind of discrete mathematics. | ||
|
Muirhead
United States556 Posts
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. | ||
|
opsayo
591 Posts
And since the win condition is always a 1-dimensional string, pursuing a win condition does not necessarily open up n dimensional (possibly much less) more possible strategies. | ||
|
Mykill
Canada3402 Posts
From what I'm seeing there's no math needed to answer this question. im sure theres a formula but if you play Tic-Tac-Toe well you automatically know that first gets to win. The larger the grid the more options for the person to connect to their previous spots. but the more = harder to connect the n amount Also the game will end in ties often since the second person will put pieces in places where connecting the n amount is impossible. hence the answer: there is no set strategy to win. the game will end in tie like normal tic-tac-toe if the second person is smart. (wow that was hardddddd) edit: proper punctuation  | ||
|
evanthebouncy!
United States12796 Posts
On May 29 2009 10:08 hixhix wrote: This is so wrong. As I said before, the second player can choose to play any where, he's not forced to play within the reduced space as assumed in many posts here. For example, assuming the 4^4 space, the first player chooses (1, 1, 1, 1), then second player chooses (3, 2, 4, 4), those belong to disjoint spaces (there exists no space that contain a valid row (length 4) and contain both points) and from the point of view of the second player, he becomes the "first player" to play in his space. I'm not saying that there is no winning strategy for the first player, I'm saying that the argument has been dicussed so far saying that n-dimension space can be reduced to (n-1)-dimension space is incorrect. I think hixhix is right. Because to "block" a winning tuple, all you need is to interrupt one of it's elements, so player 2 could've filled up your other dementions to a point where you no longer have a sure win on those n-1 dimention space anymore. | ||
|
outqast
United States287 Posts
On June 04 2009 07:30 opsayo wrote: I disagree with this, maybe this is the right approach, but as I see how it is worded, I don't think this is a conclusive proof. Let's say we have a winning strategy in the n-1 dimension, that means we have a string of n-1 length in an n dimensioned TTT game. However, it is now the second players turn to make a move, and can immediately "corner" off the n-1 length string (since all the strings are only 1 dimensional), thus negating the n-1 length string which would have won in an n-1 TTT game, but is now blocked in an n dimensioned game. edit: Let's say you're in the very first n-1th x n-1th dimension, trying to force an n-1 string. Since you have assumed in the induction step that you can indeed do this, you force a string of n-1. However, he goes second and blocks it, while you start the next iteration in the next n-1th x n-1th dimension. You go first, but you went first in the first iteration as well, and makes no difference. In order to succeed, you need to force two threatening strings simultaneously. That is in order to succeed in the n-1 dimension TTT game, you are forcing two n-2 dimensional strings. To win in an n-dimensioned game you need to force two n-1 strings simultaneously, which I don't think you can do with this approach. This is also why I don't think all cases are simply analogous to the base case(s). In a 1 dimensional game, your first move forces a win, but before you've won, you have threatened with 1 possible win condition. In a 2 dimensional game, your first move threatens 3 possible win conditions. In a 3 dimensional game, it takes a few moves (do it in your head), but your final win condition comes out to threatening only 2 win conditions. I imagine following this step, the rest of them threaten only 2 simultaneous conditions. You are missing their point. Winning in a smaller dimension successfully does not ensure that win condition will remain viable following your opponent's turn. If you successfully connect 2 in a 2x2 dimension, your opponent can immediately block it in a 3x3 dimensioned game, leaving your entire win condition from the 2x2 game useless. I think I am confused about a winning strategy. Is a winning strategy an nx1 string in a single dimension because I just interpreted it as you just have to have n boxes that are touching in some way. If it is by my definition, then my logic holds. Otherwise, I have no idea what is going on. I don't think the problem is not well articulated... | ||
| ||
