noma wrote:
And TripleM has it.

halyavin wrote:

noma wrote:
And TripleM has it.

So how numbers are connected with the answer? I don't get it.

Can you think of two sentences that are identical (including punctuation, etc) other than their first words; one being 'What' and one being 'If'?

DiMono wrote:
Alright, let me take a shot at this then:

Click here to view the secret text

×As P2 you want to force P1 to traverse an entire side of the grid, and then force P1 to return back the way they came in order to progress. Once they've retraced their steps and gone to the next available cell, you let them continue in one direction, but again not in the other. So using the 3x3 example, a sample game could look like this:

right   allow
down    block
right   allow
down    block
left
left
down    allow
down    allow
right   block
up
right   allow
down    allow
right   block
up
right   allow
down    allow - end

MATH FOLLOWS

For the NxM case, at a minimum they would have to traverse N, with an extra blocked move on each square except the first one, then return along N. That's 3(N-1) or 3N-3 moves to traverse the side, plus 1 more to get to the next available square. Then they'd have to traverse either N or M again in the same way, and so on and so forth.

So for our 3x3 grid, with P1 running a zigzag pattern, we have 6 moves to get back to O, 1 move to move down, 3 moves to get back to O-1, 1 move to get to 1-1, 3 moves to get back to it and 2 moves to finish the maze, which equals 6+1+3+1+3+2=16. Running each row all at once, gives 6 back to O, 1 to move down, 6 back to O-1, 1 to move down, 2 to finish, or 6+1+6+1+2=16 again.

For a more complex (and more relevantly, uneven-sided) 5x4 we have 12 back to O, 1 down, 6 back to O-1, 1 over, 9 back to 1-1, 1 down, 3 back to 1-2, 1 over, 6 back to 2-2, 1 down, 2 to win, which equals 12+1+6+1+9+1+3+1+6+1+2 or 43 in a zigzag. Or, going row by row, 12+1+12+1+12+1+4=43.

So this method always takes the same number of moves no matter which way P1 tries to take it. Knowing that, we can simplify things down a little. We know it takes 3(N-1) moves to traverse each row, plus 1 to move on to the next row, or 3(N-1)+1. We have to do that M-1 times (if there's 3 rows as value M, we need to do 2 full rows this way). That gives us (3(N-1)+1)(M-1) to arrive on the last row. Then we move N-1 more times to get to the end square. So our formula is (3(N-1)+1)(M-1)+N-1. Expanding gives:

  3(N-1)+1)(M-1)+N-1
= (3N-3+1)(M-1)+N-1
= (3N-2)(M-1)+N-1
= 3NM-3N-2M+2+N-1
= 3NM-2N-2M+1
= your formula

How'd I do?

halyavin wrote:

DiMono wrote:
Alright, let me take a shot at this then:

Click here to view the secret text

×As P2 you want to force P1 to traverse an entire side of the grid, and then force P1 to return back the way they came in order to progress. Once they've retraced their steps and gone to the next available cell, you let them continue in one direction, but again not in the other. So using the 3x3 example, a sample game could look like this:

right   allow
down    block
right   allow
down    block
left
left
down    allow
down    allow
right   block
up
right   allow
down    allow
right   block
up
right   allow
down    allow - end

MATH FOLLOWS

For the NxM case, at a minimum they would have to traverse N, with an extra blocked move on each square except the first one, then return along N. That's 3(N-1) or 3N-3 moves to traverse the side, plus 1 more to get to the next available square. Then they'd have to traverse either N or M again in the same way, and so on and so forth.

So for our 3x3 grid, with P1 running a zigzag pattern, we have 6 moves to get back to O, 1 move to move down, 3 moves to get back to O-1, 1 move to get to 1-1, 3 moves to get back to it and 2 moves to finish the maze, which equals 6+1+3+1+3+2=16. Running each row all at once, gives 6 back to O, 1 to move down, 6 back to O-1, 1 to move down, 2 to finish, or 6+1+6+1+2=16 again.

For a more complex (and more relevantly, uneven-sided) 5x4 we have 12 back to O, 1 down, 6 back to O-1, 1 over, 9 back to 1-1, 1 down, 3 back to 1-2, 1 over, 6 back to 2-2, 1 down, 2 to win, which equals 12+1+6+1+9+1+3+1+6+1+2 or 43 in a zigzag. Or, going row by row, 12+1+12+1+12+1+4=43.

So this method always takes the same number of moves no matter which way P1 tries to take it. Knowing that, we can simplify things down a little. We know it takes 3(N-1) moves to traverse each row, plus 1 to move on to the next row, or 3(N-1)+1. We have to do that M-1 times (if there's 3 rows as value M, we need to do 2 full rows this way). That gives us (3(N-1)+1)(M-1) to arrive on the last row. Then we move N-1 more times to get to the end square. So our formula is (3(N-1)+1)(M-1)+N-1. Expanding gives:

  3(N-1)+1)(M-1)+N-1
= (3N-3+1)(M-1)+N-1
= (3N-2)(M-1)+N-1
= 3NM-3N-2M+2+N-1
= 3NM-2N-2M+1
= your formula

How'd I do?

You definitely got the taste how the game should look like in the worst (for the first player) case. But your solution doesn't provide a strategy for all cases yet. What happens if the first player decides to go right, then be blocked down, then go left and down. Could he skip the rest of the first row after that?

halyavin wrote:

Click here to view the secret text

×Let the board be 100x100. Then the first player is forced to retrace one step in my case (right - pass, down - block, left - pass, down - pass) but he don't need to visit the rest of 98 cells in the first row anymore. So he saves a lot of time.

No he doesn't:

Click here to view the secret text

×If he goes right-pass down-block left-pass then he hasn't finished the row yet. He can go down if he wants to, but unless I'm missing something that doesn't mean I have to let him leave the column. He isn't allowed to enter the 99x99 until he has exhausted all squares that are not part of it. If he turns back early and goes down, then he's now in that column until he's exhausted it. Then he's going to have to go back to the top left corner and exhaust the top row again anyway.