Results 1 to 5 of 5

Math Help - Dot Game Theory Question

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    35

    Dot Game Theory Question

    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.)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,444
    Thanks
    1863
    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".
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    35
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2009
    Posts
    35
    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.
    Last edited by Turiski; October 30th 2009 at 06:49 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2009
    Posts
    35
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Game Theory: Hotelling game with 3 players
    Posted in the Advanced Applied Math Forum
    Replies: 2
    Last Post: March 26th 2011, 03:08 AM
  2. a game theory question
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: September 12th 2009, 08:06 AM
  3. Another Game Theory question
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: November 24th 2008, 12:11 AM
  4. Game Theory Question
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: November 24th 2008, 12:01 AM
  5. Game Theory Question with strange wording
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: October 16th 2007, 07:07 PM

Search Tags


/mathhelpforum @mathhelpforum