Dot Game Theory Question

Turiski · #1 $Old$ October 28th, 2009, 12:35 PM

Imagine a game where you have 4 rows of dots. Each row has 1,3,5,7 dots.

A legal move is a circling or capturing of some kind of any number of consecutive dots on a single row.

If you take the last dot, you lose.

The question: If you can only take from the ends of the rows, the winning moves are pretty simple to figure out. However, if you can take from the middles (which you can according to the game), it's not quite.

However, after studying it for a while, I decided that taking from the center makes no difference in the winning moves list, that is, you cannot take dots from the middle of a (end-only) winning position to form a different (end-only) winning position.

Is this true, and how would you prove it in a way you could probably generalize?

(by the way if it helps, here are some positions that if you leave your opponent in the end-only game, you win:

1, 22, 33, 44, 55, 111, 123, 145, 246, 257, 347, 356, 1122, 1133, 1144, 1155, 1246, 1347, 2222, 2233, 2244, 2345, 3333, 11111, 11123, etc.)

HallsofIvy · #2 $Old$ October 29th, 2009, 08:25 AM

Can I take it that you are not "closing" up the rows? That is, if a row has 6 dots and you take the [b]middle[b] 4, you cannot then take the remaining 2 on a single move because they are not "consecutive".

Turiski · #3 $Old$ October 29th, 2009, 12:02 PM

Yes, that is what I meant.

Some thoughts: My first instinct here is to do something like call the number of dots in the row you will change "n" then for all L<k<n, show that

if
(a1)(a2)(a3)...(ai)(n)(ai+1)...(aA) [A is the size] is a winning position

then
(a1)(a2)(a3)...(ai)(L)(k-L)(ai+1)...(aA) cannot be.

After that I get stumped.

Turiski · #4 $Old$ October 30th, 2009, 07:18 PM

Update: Very Upset. I thought I found a proof, but it failed in the last line. See if this helps.

Winning position is meant to mean, winning position in the end only game.

Assume the opposite: $\exists N$ (N is a winning position) $\exists n_{q},k,l\ (n_q > k > l)$ (n_a is the amount of dots in the a'th row of N) such that

( $\neg \exists n_{j},p$ so that $N$ without $n_q, n_j$ but with $l,k-l$ is a winning position)

This implies $N_0 = N - n_q + l +(k-l)$ (sorry about this notation) is a winning position and so $\forall W\neq N$ (w=winning position) W and N will differ by at least two row-lengths.

For every move on a winning position, it becomes a losing position, and for every losing position there is a counter to revert it to a winning position. So we define $M = N_0 - (k-l) = N + l - n_q$

Notice M differs from N by exactly one row-length. By definition $l<n_q$ , so N cannot be a winning position (in the game if N were to arise and M were a winning position then the player who placed it in N would lose because their opponent could turn it to M by removing $n_q - l$ dots from either end)

This is a contradiction, as N is defined as a winning position, the statement must be false, QED.

This is great except the part in red does not follow. M is not a winning position even in context, it differs from N_0 by a single row-length. It's relationship to N is meaningless in that respect.

Nothing else I tried came this close.

Turiski · #5 $Old$ October 31st, 2009, 07:10 PM

I think figured it out.

The end-only game is precisely equal to a "losers" version of Nim, so the plan for the proof is to show that this game has the same win chart as loser's Nim.

$\forall N^+ \in W^+$ where W+ is the set of all winning positions, $\forall n_q,k,l (n_q>k>l)$ , define

$N^+ = n_1, n_2,..., n_{q-1}, n_q, n_{q+1},..., n_R$

$N = n_1, n_2,..., n_{q-1}, k, k-l, n_{q+1},..., n_R$

s = the nim-sum of all entries in $N^+$
t = the nim-sum of all entries in $N$

Here + is used to represent the nim-sum, and j=k-l (so to clear up confusion with the - sign)

$t = 0 + t$
$t = (s + s) + t$
$t = s + (s + t)$
$t = s + (n_1+n_1) + (n_2+n_2) ... + (j+n_q) + (0+l) ... + (n_R + n_R)$
$t = s + (j + n_q) + l$
$t = s + n_q + (j + l)$

Since $N^+ \in W^+$ and we are otherwise playing Nim, s=0

this implies t=0 when $j+l = n_q$ . This of course never happens, because $k<n_q\ \therefore \ s=0 \rightarrow t\neq 0$

N therefore is a losing position, that is, you cannot make a move in the "middle" of the board to turn a winning position into a different winning position.

Did I think about this right?