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.
I know nada about this problem, and little about any math related to it. Here are my initial perceptions:
ReplyDelete- Hmm. If f(x) = 1, then Mark clearly wins by starting on (x,x) and going either vertically or horizontally depending on the response.
- Suppose f(1) = 2, f(2) = 2, and f(3) = 2. Mark can't seem to win quickly, but he can appear to make "progress" by playing in the corner and forcing Betty to block him from accumulating too many on lines 1, 2, and 3. The nature of this progress is that he's restricting Betty's future choices on the lines where he accumulates more Ms, and it'll allow him to get a head start when playing in the other direction on later lines.
It seems like it's pretty tough for Mark to win, all in all. Thinking about how fast he seems to be making "progress" in my above example, if I had to guess, I would say that Mark can win when f(n) averages below 0.25n + 1 or so. I certainly don't think he could win if f(n) averages near 0.5n. (Of course, the average can't be the whole story; if f(n) starts out very low Mark may win regardless of f(n)'s later behavior.)
An increasing function from N to N? Is that a typo or do I not understand something?
ReplyDeleteMy intuition is that this problem will have some connection to VDW numbers and/or 3-free sets.
ReplyDeleteGeoff, I believe that means that F maps natural numbers to other natural numbers.
ReplyDeleteI've never heard of this problem and have thought for less than thirty seconds. That said, I think the optimal f(n) goes to infinity, but slowly (inverse iterated exponentiation?).
ReplyDelete@Geoff: perhaps one is meant to interpret "increasing" in the weak sense, that is, "nondecreasing".
ReplyDeleteFirst guess is that a randomized strategy will win with f(n)=o(root(n)). Although on a 3-dimensional "board" f may be significantly larger.
ReplyDeleteNever heard of this problem. Hard to get solid intuition.
ReplyDeleteMy "insights" after the proverbial 30 seconds of thinking:
If f(n) = 1 (i.e. VERY slowly growing function) it seems clear Mark can always win. Just start almost anywhere, if Betty blocks one direction he can easily get n/2 + 1 in the other direction.
It seems for anything more e.g f(n) = n it would be hard for Mark to have a winning strategy (or at least to PROVE that Mark has a winning strategy). Just my intuition.
Not so sure about f(n) = log(n) and the like ...
I look forward to the no doubt counter-intuitive denouement.
Clarifications: N is the naturals.
ReplyDeleteI did indeed mean that f is non-decreasing.
Anon who thinks it has something to do
with 3-free sets or VDW- is that your
mathematical intutition or your intuition about GASARCH? While I intended this to be about math intuition, I can't complain if you think in other terms.
My intuition was that there is some constant k such that, if f(n) > k, then neither player can win. And, if f(n) <= k I guess it would depend on n... Since you mention that "much is known on this problem", that suggests that much is unknown, and there is no simple answer, right?
ReplyDeleteThere are some asymptotic results known:
ReplyDeleteif f(n) \le O(g(n)) then Mark wins.
If f(n) \ge Omega(h(n)) then Betty wins
but g(n) << h(n) so there is still a gap.
I think that this game is about position.
ReplyDeleteI know that f(n) is never bigger than n/2, and I think that the space of Mark's strategies gets smaller as f(n)→n/2. I think that the size of the space of strategies gets to 0 before f(n) gets to n/2. I am interested to know if this limit can be parameterized accurately by n.
Completely off-the-cuff, I'd guess f(n) = O(1) is always attainable, f(n) = little-omega(log(n)) is not attainable. No insight about the in-between.
ReplyDeleteTo be sure, my confidence here is roughly zero.
Oh boy ... I have neither training nor familiarity with this problem, beyond common-sense and board-games.
ReplyDeleteMy first intuition is that this problem likely has an algorithmically deep "GO-like" aspect to it.
Thus, if we start with a bare board, then f(n) ~ (n)^(1/2) would not be surprising ... but we would expect that the strategy for saturating this bound is hard for Mark/Betty to find.
However, if the initial board had a sparse sprinkling of randomly-placed M's and B's, or if there were an error process associated with placing M's and B's, or if the board had hexagons instead of squares, (etc.) then it would not be surprising if the answer were completely different.
In short, this might be a question that is really about algorithms, that is disguised as a question about combinatorics and geometry.
Know nothing about this problem.
ReplyDeleteMy intuition is that f(n)
is of the order sqrt(n)
I suspect Betty's optimal strategy will be always placing her piece along Mark's best row or column, where best is max(|Mark pieces| - |Betty Pieces|). To improve, Mark needs to to create a fork, where one piece increases the length of two equal quality rows/columns (as happens with his first move: Betty can add to the column or row, and Mark lengthens the other).
ReplyDeleteBut if Mark is building towards having a row/column of equal score intersect, Betty will (always?) have a chance to block the intersection while the row/column are both constructed. Thus I suspect you need at least 2 parallel rows/columns, such that the new addition has two intersection points. It may be that later in the game the number of parallel rows required increases.
Thus each additional piece Mark places on his best row requires recursive construction of 2 rows and 1 column (or 1 and 2) all of the same length (possibly more?). The first is 2x3, assuming that trend follows the next piece requires 5x7, then 12x17, 29x41, 70x99, or w(i) = w(i-1)+l(i-1), l(i)=2*w(i-1)+l(i-1). I haven't bothered turning that into a nonrecursive equation, but eyeballing the numbers it seems to grow exponentially, so I'd expect f(n) to be proportional to c^(b/n), where a shot in the dark is c=2,b=1. That's all just intuition, I haven't tried proving that any of it.
No nontrivial intuition about the answer, but I wanted to remark the game reminds me of Conway's "Angel Problem". In this case, f(n) represents some extra "power" which Betty has. I wonder whether the game would be equivalent to Mark only needing n/2, but Betty being allowed to make extra moves in some specific way depending on f(n).
ReplyDeleteI will say log n and sqrt n, i.e., with f(n)=log n it is likely the first player has a winning strategy and with sqrt(n) it is unlikely. Of course, I don't have a proof.
ReplyDeleteFirst, looking at linear functions, the upper bound is clearly n/2+1. For the 0 function, I am pretty sure that any distribution of checkers will feature such a row and column, just by the pigeonhole principle. n/4 isn't winable if you fix it as requiring a row, but clearly you get more power by allowing rows or columns.
ReplyDeleteThinking in terms of strategies, Mark gets to increment both a row and a column, while Betty gets to balance on only one of those rows and columns (but of course also on another one). Intuitively I would guess that n/4 isn't winable by Mark for large enough n.
So, as a guess, linear functions below a point are Mark-winable, above a point are Betty winable.
Would not at all be surprised to be wrong.
My intuition would suggest that "keeping things like random" should be possible for each player, despite the other's effort. In other words, f\in\Theta(\sqrt{n\log n}) should be the best possible for Mark.
ReplyDeleteI know nothing about this problem but like it. My thinking is much along the lines of Seth's (n/4 being some natural bound, or perhaps the limit of a certain kind of bounding technique). Also had the same thoughts as Paul's first paragraph about optimal strategy.
ReplyDeleteIt seems to me that Mark has a winning strategy for f(n) = O(log n),
ReplyDeletesince he can force Betty to block his M's if he insist to put them on the same row, meanwhile increase the number of M's by 1 on half of the columns, recusively it would be a log n factor.
On the other hand, I have bad intuition for Betty to win. My guess is f(n) = \Omega(n), although the precise constant is hard to tell, right now I'll guess n/4.
Knowing nothing about this problem, thinking for 15 seconds, and avoiding reading any of the other comments, I guessed f(n) \in \Theta(\sqrt n), based on the standard deviation of a randomized approach. It seems this is probably not right, because it doesn't analogize well to other dimensions: in 1 dim, f(n)=1 is clearly a win for Mark.
ReplyDeleteafter thinking for five minutes, my intuition tells me that Mark can always win with f(n)<=log_2(n). Betty should win otherwise.
ReplyDeleteWell, there is no winning strategy for f(n) = n/2.
ReplyDeleteFor n = 1, Mark wins.
n =2 , Mark wins.
n = 3, Betty wins because getting any row or column is equivalent to winning tictactoe (actually, even harder since Mark cannot with diagonals). Betty can just play tictactoe and force Mark to lose (i.e force a win for her).
So there is no strategy for f(n) = n/2
With no thought at all, I would guess that O(log n) is winnable for Mark, and omega(n) is winnable for Betty. After looking at other responses, I agree that omega(sqrt(n)) is probably winnable for Betty too.
ReplyDelete