Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] The Solution to the Mark-Betty Game

Expand Messages
  • GASARCH
    RECALL from my last post the following game: Let f(n) be a non-decreasing function from naturals to naturals. Consider the following game: Let n be a large
    Message 1 of 1 , Aug 3, 2010
    • 0 Attachment
      RECALL from my last post the following game:

      Let f(n) be a non-decreasing function from naturals to naturals. Consider the following game:
      Let n be a large natural number. Mark and Betty alternate (Mark goes first) putting M's and B's on an n by n checkerboard. No square can have two markers on it. They play until all squares are covered; hence the game will end after n2 moves. If at the end there is some row or column A where the number of M's in A is at least n/2 + f(n) then Mark wins! If not then Betty wins! (NOTE- the M's in A do not have to be adjacent.)
      I asked for your intuitions on when Mark or Betty have a winning strategy. Here are the answers and a pointer to my writeup of it. NONE of this is my work- it is all the work of J.Beck (the reference is in the writeup). Here are the results:
      1. If f(n) ≤ O(\sqrt(n)) then Mark has a winning strategy.
      2. If f(n) ≥ Ω(\sqrt(n log n)) then Betty has a winning strategy.
      3. My writeup is here. If I fill in more details it may change.
      (NOTE- html's sqrt sign is pathetic. Here is what square root of n looks like: √ n. The sqrt sign has no top! That's why I use `sqrt')

      My writeup of the first result is complete. I included more detail then you usually get in a math paper. I do not know if this is good or bad; however, I really wanted to check it all for myself. My writeup of the second result is much sketchier; however, it is essentially Beck's proof.

      Beck has a book on games of this nature entitled Combinatorial Games: Tic Tac Toe Theory. Will children buy it thinking it is about tic-tac-toe? Maybe Bill Gates' kids: the book costs $146.00 new and $107.00 used.

      --
      Posted By GASARCH to Computational Complexity at 8/04/2010 12:09:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.