Nice problem; was a bit like this problem that I submitted to Canada/USA Mathcamp for their qualifying quiz, only a bit tougher to solve and much tougher to draw. I really suck at drawing hexagons...

Me too, I got k=5. I'll post a solution in 30 minutes, since I can't access imgur right now. EDIT: whoever posted a comment before me deleted it. So is $k=5$ definitely wrong? EDIT2: nevermind, he reposted a comment.

I got k = 5 by coloring every third tile black, such that no two blacks were adjacent.. EDIT: darnit, did not see that white-white-black-white-white works...Definitely 6.

Ambiguity questions: Do we assume that B's goal is to stop A from winning, so we are assuming B is playing optimally to stop A? (This is never stated) Does each player have to make a move each turn? ("may" implies having the option of not moving?) Is it a hexagonal grid as in a honeycomb? By consecutive cells in a straight line do they necessarily mean along one of the three main directions?

I actually thought about all of those but figured the obvious interpretation was right. I thought it was fairly clear that the problem meant "for some k, can A win however B plays" though.

Hmm the only one of these that I was actually concerned about was the second one (and am still somewhat concerned about)

I suck even more at drawing hexagons on the computer, so I won't post a solution, but I got $6$ as well. For those who got $5$, would you mind posting what you have? (remember that you are looking for the minimum such that A cannot win, not the maximum such that he can...) @pi37: I'm fairly sure it doesn't matter; I assumed they didn't have to move, which implies the result if they do

I got 6. there's a pretty short strategy that can give 5.

Can someone post the strategy for 5? I spent hours trying to figure out one and eventually assumed that 5 was impossible. EDIT: I am asking this because I can't understand yours.

I did already. Check my solution

I wouldn't mind playing the game with somebody who thinks $A$ can win when $k=5$. However, I do not know how to play someone online...

I'll play you (and win). Wanna bet some money?

Where do we play? I'm serious, I'm willing to play someone. EDIT: crap, I realized there was a hole in my coloring argument. Frick. $k=6$ is probably right.

We can assign a coordinate system and play over some random aops forum or email or whatev

On phone so this is ugly. Obviously we can get ....... ...cccc B has to take a c in the middle or we're done. Then get ....c.. ...cccc B still has to take a c in the middle. Then get ....cc. ...cccc Or its reflection. B still has to take a c in the middle. If its the left one do ...ccc. ...cccc And A wins next turn. Otherwise do ...ccc. ..ccc.c And A wins next turn.

The answer can be no minimum. A and B will work together to help A win. You just look at a straight line. A puts 2, B removes the one at the very beginning, A puts 2 on the same line in the same direction, B removes the beginningmost counter, and this keeps going on. Hence there is no minimum. I didn't actually write that in the solution, but I did write that if B wasn't playing optimally, then there would be no minimum, so my final statement said, "Assuming B is playing optimally, k=6."

jeff10 wrote: The answer can be no minimum. A and B will work together to help A win. You just look at a straight line. A puts 2, B removes the one at the very beginning, A puts 2 on the same line in the same direction, B removes the beginningmost counter, and this keeps going on. Hence there is no minimum. I didn't actually write that in the solution, but I did write that if B wasn't playing optimally, then there would be no minimum, so my final statement said, "Assuming B is playing optimally, k=6." That's what I did!

That's also what I did. The problem in my opinion should have been more clear. I just said no minimum.

So many people thought the answer was $k=5$... ...including me. Ugh. I see the hole in my proof now. I had hoped that I'd get 20 or so overall...

We assume that on each move, $A$ and $B$ must both perform one of their designated moves, they may not pass. We also interpret the problem as finding the minimum such value of $k$ so that $A$ may not $\textbf{guarantee}$ a win. Also, define a turn as a pair of moves, where $A$ moves first and then $B$ moves. First, we will show that $B$ can always prevent $A$ from getting 6 cells in a line, all filled with coins. Here is $B$'s strategy. After $A$ moves first, there will be 2 coins somewhere on the infinite board. $B$ then randomly selects one of these coins, removes it from the grid, and then colors the entire infinite grid as shown below, with the center of one of the large hexagons being the cell that $B$ just removed a coin from. https://www.dropbox.com/s/u7xnvafbcvwulmc/FullColoring.JPG Let $S$ be the set of shaded cells in the above image. We prove by induction on the number of turns that for any positive integer $n$, after $n$ turns of the game have been completed, $B$ can guarantee that the only cells that $A$ has a coin on belong to $S$. Our base case after 1 turn has been completed, which is trivial based on the definition of the coloring. Now, let $k$ be a positive integer, and assume that after $k$ turns have been completed, all of the cells which have a coin on it belongs to $S$. On $A$'s move in the $k + 1$ turn, $A$ can either place both of his coins in cells that belong to $S$, in which case we are done, or place one coin in a cell that belongs to $S$ and the other in a cell that doesn't. In the first case, $B$ can just remove a random coin, and in the second case, $B$ can remove the cell that $A$ placed that was not in $S$, so the induction is complete. Note that the longest streak of cells that all line on a line and that all belong to $S$ is 2, so $B$ can guarantee that $A$ can get a streak of length at most 5 of cells that all lie on a line and contain a coin, by placing a coin in-between 2 of these length 2 streaks of cells that belong to $S$. Now, we prove that this upper bound of 5 is in fact attainable. That is, $A$ can guarantee that he can get 5 cells, all filled with coins and that all lie on a line. Here is $A$'s strategy. First, he places 2 coins somewhere on the board, $B$ will then remove 1, and then $A$ will create a triangle like formation, as shown below. https://www.dropbox.com/s/4y1sxtr55ro2djy/1pic.JPG $B$ will then remove one of these coins, and then no matter what coin $B$ remove, $A$ will then always be able to create a formation of two adjacent segments of 2 adjacent cells filled with coins, or a quadrilateral configuration as shown below. https://www.dropbox.com/s/l5vj6iwjpimxh75/2pic.JPG Now, we break up into two cases, depending on which coin $B$ removes now. The first case is where $B$ removes a coin in such a way that we get a triangular configuration again, as shown below. https://www.dropbox.com/s/4deaye1599jxoga/3pic.JPG Once we have this triangular configuration, $A$ will then place his coins so that we get two adjacent segments of consecutive cells with coins in them, one of length 3, and one of length 2, as shown below, which we will always be able to do. https://www.dropbox.com/s/rhpwrq7d5yy0ncr/4pic.JPG Now, $B$ must remove a coin from the segment of length 3, or else $A$ would be able to achieve 5 the next turn. If he removes a coin at either of the endpoints of the segment, then $A$ will have a quadrilateral configuration again, so he can than reach a configuration of two adjacent segments of length 3 as shown below. https://www.dropbox.com/s/vfnvbi6hoqxn3qh/5pic.JPG Then $B$ can remove a coin from at most one of these segments, so then the next turn, $A$ will be able to achieve 5, so we can assume that once $B$ removes a coin from the configuration with two adjacent segments, one of length 3 and one of length 2, he removes the coin in the middle of the segment of length 3, so that $A$ then has a configuration like the one shown below. https://www.dropbox.com/s/fd256gmtbnn5nnu/6pic.JPG Once here, $A$ should then place his coins so that one coin bridges the two segments of length 2, and then adds another coin in some cell adjacent to the cell that he just added a coin to, to get a configuration similar to the one shown below. https://www.dropbox.com/s/tcq26qgv1icykk2/7pic.JPG If $B$ does not remove the coin that bridged those 2 segments, then the next turn $A$ will be able to achieve 5 because he would then have at least one segment of length 3, thus, we may assume that $B$ removes the coin in this bridging cell. Then $A$ should place a coin in this bridging cell and place the other coin in some empty cell adjacent to this bridging cell. Then by the same argument, $B$ must remove the bridging cell again, so after doing this for all possible direction, it should be $A$'s turn and he should have a configuration like the one below. https://www.dropbox.com/s/oyrr88r6u6f28u2/8pic.JPG Then $A$ should use the same procedure on the current half open large hexagon he has now, and use the same idea of a bridging cell in the center of this hexagon, as shown below. https://www.dropbox.com/s/3tjna7ud6j315i5/9pic.JPG After $A$ is finished with this procedure in every possible direction again, it should be $A$'s turn and he should be looking at a configuration like the one below: https://www.dropbox.com/s/nghki77mwzv90bk/10pic.JPG Then, $A$ should use a cell where two of the segment of length 2 of the large hexagon just formed as a bridging cell again, as shown below: https://www.dropbox.com/s/wug4hr32i32d0ua/11pic.JPG After $A$ is finished with this procedure in all possible direction, it should be $A$'s turn and he should be looking at a configuration like the one below: https://www.dropbox.com/s/b82l3l87ijr6sbs/12pic.JPG Then, $A$ will have an empty cell in between two segments of length 2, both on the same line, and if $A$ just puts a coin here, then $A$ will achieve 5, so he is done, as shown below: https://www.dropbox.com/s/t0p75kp9f84xt8k/14pic.JPG Now, we need to consider the case all the way back when $A$ had a quadrilateral formation, that is two adjacent segments of length of length 2, and then $B$ removes a coin in such a way that $A$ is not looking at a triangular configuration, as shown below: https://www.dropbox.com/s/erbo4g371cvvq3e/13pic.JPG Then $A$ can add two coins so that $B$ is looking at two adjacent segments, one of length 3 and one of length 2, as shown below. https://www.dropbox.com/s/u49oh18cik3uu52/15pic.JPG?m= As discussed earlier, $B$ must then remove the middle cell of the segment of length 3, so reach a configuration as shown below: https://www.dropbox.com/s/g8ot7twoyfqau9h/16pic.JPG But from here, we know that $A$ can achieve 5, so we have shown that $A$ can always achieve 5. Thus, the desired minimum value of $k$ is $6$, so we are done.

Dang^^

Got quite trolled by this problem for a long time

There appear to be no solutions here complete with nice diagrams (maybe the dropbox links did, but they're all dead now), so I guess I'll provide mine. But of course, who likes "player $A$" and "player $B$", so I'll rename them as Alice and Bilbo.

The answer is \(k=6\). \bigskip Bob's strategy for \(k=6\): Consider the below ``honeycomb'' coloring. Bob can ensure that at any point in time, at most one of the blue hexagons is colored; thus the longest line of labeled hexagons has length five. [asy][asy] size(5cm); defaultpen(fontsize(10pt)); pen fil=lightblue+white+white+white; path hex(real x, real y) { return (x,y)--(x+1,y)--(x+3/2,y+sqrt(3)/2)--(x+1,y+sqrt(3))--(x,y+sqrt(3))--(x-1/2,y+sqrt(3)/2)--cycle; } fill(hex(3/2,-sqrt(3)/2),fil); fill(hex(9/2,-sqrt(3)/2),fil); fill(hex(15/2,-sqrt(3)/2),fil); fill(hex(0,sqrt(3)),fil); fill(hex(3,sqrt(3)),fil); fill(hex(6,sqrt(3)),fil); fill(hex(9,sqrt(3)),fil); fill(hex(3/2,5sqrt(3)/2),fil); fill(hex(9/2,5sqrt(3)/2),fil); fill(hex(15/2,5sqrt(3)/2),fil); for (real x=0; x<=9+1e-9; x+=3) { for (real y=0; y<=2sqrt(3); y+=sqrt(3)){ draw(hex(x,y)); } } for (real x=3/2; x<=10+1e-9; x+=3) { for (real y=-sqrt(3)/2; y<=5sqrt(3)/2; y+=sqrt(3)){ draw(hex(x,y)); } } [/asy][/asy] \bigskip Alice's strategy for \(k=5\): On the contrary, consider arbitrarily-long two chains of long hexagons in a ``parallelogram'' formation as follows. Play strictly within the chain until it is no longer possible; that is, until there are no two adjacent uncovered squares. [asy][asy] size(6cm); defaultpen(fontsize(10pt)); pen fil=lightred+white+white+white; path hex(real x, real y) { return (x,y)--(x+sqrt(3)/2,y+1/2)--(x+sqrt(3)/2,y+3/2)--(x,y+2)--(x-sqrt(3)/2,y+3/2)--(x-sqrt(3)/2,y+1/2)--cycle; } fill(hex(0,3/2),fil); fill(hex(sqrt(3),3/2),fil); fill(hex(3sqrt(3),3/2),fil); fill(hex(4sqrt(3),3/2),fil); fill(hex(5sqrt(3),3/2),fil); fill(hex(7sqrt(3),3/2),fil); fill(hex(8sqrt(3),3/2),fil); fill(hex(3sqrt(3)/2,0),fil); fill(hex(5sqrt(3)/2,0),fil); fill(hex(7sqrt(3)/2,0),fil); fill(hex(11sqrt(3)/2,0),fil); fill(hex(13sqrt(3)/2,0),fil); label("\(x\)",(2sqrt(3),5/2)); label("\(y\)",(6sqrt(3),5/2)); for (real x=0; x<=8sqrt(3); x+=sqrt(3)) { draw(hex(x,3/2)); } for (real x=sqrt(3)/2; x<=8sqrt(3); x+=sqrt(3)) { draw(hex(x,0)); } [/asy][/asy] If we have not won already, then there are two uncovered hexagons \(x\), \(y\) in the top row with \(k\le4\) covered hexagons between them. If \(k=4\), we just win by covering either \(x\) or \(y\). If \(k\le3\), then consider the hexagons in the bottom row adjacent to \(x\) and \(y\). By hypothesis, all four are covered, and at most one of the \(k-2\le2\) hexagons between them is uncovered. We can easily win by filling it.

I do apologize for the poor diagrams. I don't know assymptote and the diagrams I used to substitute are of very poor quality.

Cool problem! Construct a graph where the vertices are the centers of the hexagons and the edges are the pairs of hexagons sharing a side. Then we get the following triangle lattice. Each of $A$'s moves is equivalent to marking two adjacent vertices, and each $B$'s moves is equivalent to unmarking a marked vertex. [asy][asy] for (int i = 0; i <= 4; ++i) { draw(i * dir(60) -- i * dir(60) + (4-i) * dir(0)); draw(i * dir(0) -- i * dir(0) + (4-i) * dir(60)); draw(i * dir(0) -- i * dir(0) + (i) * dir(120)); } [/asy][/asy] We claim that $k=6$. Part 1: Showing that $k=5$ is winnable The complete strategy is shown below. Red vertices are the ones $B$ must unmark to prevent $A$ from getting five in a row on the next turn. https://drive.google.com/file/d/1Sp5UFogzLlZUmQqYZUJfRV5cqOxQvRzm/view?usp=sharing After $A$'s seventh move, no matter what $B$ does, $A$ can mark $5$ in a row in either row $1$ or row $2$. Part 2: Showing that $k=6$ is not winnable Number each of the vertices from $1$ to $3$ in the following repeating pattern: [asy][asy] for (int i = 0; i <= 4; ++i) { draw(i * dir(60) -- i * dir(60) + (4-i) * dir(0)); draw(i * dir(0) -- i * dir(0) + (4-i) * dir(60)); draw(i * dir(0) -- i * dir(0) + (i) * dir(120)); } for (int i = 0; i <= 4; ++i) { for (int j = 0; j <= 4 - i; ++j) { int mod = (2*i + j) % 3 + 1; label("$" + string(mod) + "$", i * dir(0) + j * dir(60), 2 * dir(90)); } } [/asy][/asy] Note that along each line of vertices, the numbers repeat as $1,2,3,1,2,3,\dots$. $B$'s strategy to prevent $A$ from getting $6$ in a row is to unmark any vertex labelled $1$ whenever it is marked. To show that this works, consider the state right before $A$ makes their last turn. They have to be in one of the following cases ($X$ means $A$ marks these vertices to make $6$ in a row): Case 1: $1$ $2$ $3$ $1$ $X$ $X$ Case 2: $1$ $2$ $3$ $X$ $X$ $3$ Case 3: $1$ $2$ $X$ $X$ $2$ $3$ in each of these cases, all three numbers appear in the marked vertices before $A$ marks the final two, which cannot happen if $B$ keeps unmarking $1$. Thus, $k=6$ is unwinnable.

2023 jmo/4 anybody?

My favourite question Also why is there a tag analytic geometry? This is purely Combinatorics (colouring method) So we choose a random hexagon to colour black, and colour all hexagons at distance 2 from it. Repeating the process for each newly coloured hexagon give a hexagonal lattice. Note that any 2 black cells are not adjacent, so A cannot put counters in 2 black cells on each move. On each move, if A previously put a counter in a black cell, B removes it. Otherwise no counters are in black cells and B removes a random counter. So at any time at most 1 black cell can be occupied, giving $k\leq6$. We then find a forced win for A in 8 moves when $k=5$, so we have $k=6$ Full proof here: https://infinityintegral.substack.com/p/usajmo-2014-contest-review

Bit on the difficult side for #4, but I really enjoyed the problem. The answer is $k = 6$. Color all the hexagons in the grid red, blue, or green, such that no two adjacent hexagons share a color, and reading left to right in any row, the colors are in order red, blue, green. Construction: This is probably overly complicated but whatever. We first use a key claim: Claim. $A$ can ensure that at least $4$ counters are consecutively in a line after his turn. Proof. Suppose otherwise, and assume WLOG that the single counter after $A$ and $B$ have both performed one turn is on a red square. Then, $A$ may place two counters on the adjacent green and blue squares (in that order) to the right of the red square. If $B$ removes the blue counter, then $A$ can place two more consecutive counters to the right of the green counter, contradiction. Similarly, $B$ cannot remove the red counter. Hence $B$ must remove the green counter. But now, consider the two adjacent red and blue counters three rows below the original row. $A$ may place counters on both those hexagons; then, if $B$ removes one of the two red counters, $A$ can form a diagonal line of $4$ counters with endpoints at the blue counters, and vice versa. Hence $A$ can make a row of $4$ counters. $\blacksquare$ Now assume that $A$ has a row of $4$ counters after his turn, say in order red, green, blue, red. During $B$'s turn, $B$ must remove a blue or green counter, or $A$ will make five counters in a row. In particular, as long as not all hexagons adjacent to the green counter are occupied, if $B$ removes a green counter, $A$ can replace the green counter and place a counter on one hexagon adjacent to that counter. Continuing in this process, $A$ will be able to ``surround" one of the green or blue counters (as $B$ has to keep removing one of those two counters before this happens). After this happens, on $A$'s next turn, he will place two counters on the green and blue counters to the right of the red counter. In this way, he creates $4$ consecutive counters with colors blue, red, green, blue; by our previous argument, $A$ will be able to surround the red or green counter. But after this happens, there are either four consecutive in both the rows above and below the given row (if the red counter was surrounded) or two groups of two counters in both the rows above and below with one space in between. In both scenarios, $A$ will be able to construct a chain of $5$ counters, as needed. Bound: Compared to the construction, this is very easy. $B$ simply removes any blue counters $A$ has on the board. As no two blue counters are adjacent, on every turn, $A$ may only place one new blue counter. So at the end of $A$'s turn, there is at most one blue counter on the board; but any chain of at least $6$ consecutive counters must contain two blue counters. So in this way, $A$ cannot construct any chains of length $\geq 6$, as needed.

The answer is $k = 6$. For $k \leq 5$: it is like a game of gomoku: $AA$ -> cuts into $A$ -> play $AAA$, threatening five, if he cuts the end then play $AAAA$ threatening two fives, he must cut the middle to reach $AA\_A$. If he cut the middle, play $A\_AAA$, threatening $5$. If he cuts the right end, we get to $AA\_A$. If he cuts the middle $A$, we play $AAAAA$, winning. If he cuts the middle right $A$ we play $A\_AAA$ with A above the third and fourth $A$. If he cuts anything else we can reduce to the previous line, otherwise he will cut middle again. Otherwise, we play $A\_AAA$ with $A$ above the third and fourth $A$ and fourth and fifth $A$. If he refuses to reduce to $A\_AA$ then now we play $AAA\_A$ with the row above being a three in a row, he cannot defend both threats to $5$ so we win. Otherwise, he must allow us to reduce to $AA\_A$. Repeat the above forcing line with $AAAA$ plus on the end to eventually reach $AA\_A$ with two $A$ in the row above between the $A$s and the empty spot. Now we play $AA\_AA$ with three $A$s on the row above, and we win since he cannot defend the four $A$ line and the triple $A$ threats into $5$. Now, to prevent $6$, simply take the unique periodic coloring of the honeycomb with three colors and always remove the hexagon on a fixed color. It is easy to see that it is impossible to make $6$ with this rule.

Solved with stillwater_25. The problem is for one badly worded. Also it is easy to assume that the problem is asking to form a consecutive line of cells after B's move which yields the answer of $k=3$. It wouldn't have hurt to include '(even after one of A's moves)' to avoid people fakesolving just due to this misunderstanding. We claim that the answer is $k=6$. We first show that for $k=5$, $A$ can always win. It is not hard to see that $A$ can force two consecutive grid cells to contain a counter even after one of $B$'s moves (consider a set of three mutually adjacent hexagons and place counters on two pairs of hexagons in this set). Now, in the line through the cells on which counters are placed, $A$ leaves a gap of two cells and places two counters on the next two cells. Label the cells $1,2,3,4,5,6$ in that order where $1,2$ and $5,6$ currently contain counters. If $B$ deletes the counter in cell $6$, $A$ immediately wins by placing counters on cells $3$ and $4$. Thus $B$ is forced to delete the counter in cell $5$. Now, consider the two cells above and adjacent to cell $3$. In turn, $A$ places counters in cell $3$ and one of these cells. If $B$ deletes the counter in the above cell, $A$ can place counters in $4$ and $5$ and win, so he is forced to delete the counter in cell $3$ in both turns. $A$ then repeats this argument on cell $5$. Then, the four cells above cells $3$ and $5$ (which form a consecutive line of length $4$) now all have a counter in them. All that remains is for $A$ to place two counters to be collinear with these and he wins. To see why $k<6$, we color the board in three colors; Red , Blue and Black, such that no two adjacent hexagons are of the same color. Observe that then any line of consecutive grid cells alternate the color as -Red-Blue-Black-Red-Blue- infinitely. Now, $B$ performs the following strategy. If $A$ places a counter on a blue cell he deletes it. Else he deletes a counter on whatever cell he wishes. Note that since no two blue cells are adjacent due to the nature of coloring, $B$ can ensure that after his move, there are no blue cells with counters in them. Thus at any given moment there can only be at most one blue cell with a counter in it. But, if it is possible to have a line of 6 consecutive grid cells, due to the nature of the coloring two of these will be blue which is a clear contradiction.