## [Computational Complexity] I want your intuitions on this, so the less you kn...

Expand Messages
• Let f(n) be a monotone increasing function from N to N. Consider the following game: Let n be a natural number which we thing of as being large. Mark and Betty
Message 1 of 1 , Aug 2, 2010
• 0 Attachment
Let f(n) be a monotone increasing function from N to N. Consider the following game:
Let n be a natural number which we thing of as being large. 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; 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.)
For which f(n) does Mark have a winning strategy? For which f(n) does Betty have a winning strategy? Much is known on this problem. I have written up some notes that I will post on Wednesday. (None of this is my work.)

What are your intuitions and why? If you already know the answers then please do not post. SO, paradoxically, the less you know the more I want you to post. I want to know what the intuitions of someone who does not know the problem are.

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