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

Expand Messages
• 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.