[Computational Complexity] The Solution to the Mark-Betty Game
- 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:
- If f(n) ≤ O(\sqrt(n)) then Mark has a winning strategy.
- If f(n) ≥ Ω(\sqrt(n log n)) then Betty has a winning strategy.
- My writeup is here. If I fill in more details it may change.
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