number seq?

OK, this is just something I've been doing for fun, hence, not that important. at www.sporkle.com (jn the multiplayer section), players can play a game called rooms. I'm sure some of you have heard of this. It is a two player game, and you start with a blank grid, lets say 5x5. You can draw a line connecting two dots, the line has to be one unit in length (cannot cross over a dot), and cannot be diagonal.

When a player makes a square (which must be 1x1) the square gets the colour of the player. At the end of the game (once all the squares are coloured) the player with the most squares of his/her colour wins.

I want to work out if there is a sequence for the maximum number of turns, taking into account that if a person gets a pointm they get an extra move that turn.

BTW, the lines on the outside have not been drawn from the start

so, here are my numbers (may be incorrect):
1x1=4 turns
2x2=10 turns
3x3=17
4x4=? i got lots of different answers


edit:
I'm pretty sure 4x4=27

Here's a screen shot:

Quote:

---

I want to work out if there is a sequence for the maximum number of turns, taking into account that if a person gets a pointm they get an extra move that turn.

...

3x3=17

---

What is it that you are really trying to calculate? The maximum number of turns, given that both players want to win? Or the maximum number of turns, given that both players want to play as many turns as possible?

I guess the first alternative is quite tricky to calculate. If you are after the second alternative, then for a 3x3 grid, it is easy to find a sequence with more than 17 turns.
Assume first the 12 horizontal lines are taken. Then the players take the 6 vertical lines on the left and right borders. This is a total of 18 turns, without any squares being taken. On turn 19, one of the players will take all of the squares.

I would want as many turns as possible if both players also want as many turns as possible.

If my numbers are wrong, could you please try to correct them, maybe get the first 6.

OK, Acidic. Lets try to do some thinking on your problem:

Quote:

---

1x1=4 turns
2x2=10 turns
3x3=17
4x4=? i got lots of different answers
edit:
I'm pretty sure 4x4=27

---

Since you want the maximum number of turns, given both players want the maximum number of turns, it should be pretty simple.

1x1=4 turns
2x2=11 turns
3x3=19 turns
4x4=33 turns
5x5=46 turns
6x6=67 turns

The idea is to make as many 2x1 fields as possible. After this is accomplished, all squares will be taken during the last turn.

Lineout for the algoritm for most turns, for a NxN system:
1. Fill all horizontal lines: N*(N+1) turns
2. Fill every second vertical line: N*((N div 2)+1) turns
3. Take all the squares: 1 turn

Here div denotes integer division:
N div 2 = N/2 if N even
N div 2 = (N-1)/2 if N odd

Conclusion: The maximum number of turns for a grid of size NxN is:
N even: N*(N+1) + N*(N/2+1) + 1 = N*(3N/2 + 2) + 1
N odd: N*(N+1) + N*(N/2+1/2) + 1 = N*(3N/2 + 3/2) + 1

Checking the formula:
N=1 -> 4 turns
N=2 -> 11 turns
N=3 -> 19 turns
.
.
.
N=100 -> 15201 turns

OK, now you can try to find the formula for the maximum number of turns for a non-square grid, that is, a MxN grid. Should not be much more tricky, probably three cases:
M and N even
M xor N even
M and N odd

Best regards
//Johan