Tetris reference??!?!?? O piece makes the largest score of $4$

split the grid into 2x2 cells to prove upper bound of 4. Very nice problem! Also why was this like the hardest problem on the jmo

Accidentally said that T piece worked oops that's like 1 point deduction right bc I solved the rest of the problem just like got a wrong config

Why were there two combo games on d2 :sob:

I literally described an algorithm that R can use to limit B to 4 LOL

We can actually prove a stronger version where $R$ chooses to place at most two red squares; this makes the $2\times 2$ squares a little easier to visualize.

Does anybody know who proposed this one?

hopefully this works

i just found the optimal strat for both players and simulated to get the s/z piece

MathJams wrote: hopefully this works

similar to what i did

ihatemath123 wrote: Does anybody know who proposed this one? David Torres

Quique wrote: ihatemath123 wrote: Does anybody know who proposed this one? David Torres Never heard of this person, but this might be my new favorite problem of all time.

yeah @above said this might be his fac problem i agree. tbh i think a lot of ppl lost points for not rigorous sols

Why is this problem so good? I love this....

To prove 4 is always possible, see that all 3 or less tile cases require > 2n red tiles to completely cover the entire perimeter. 4 is the maximum because R can force the 2x2 square case. Simply put 2 adjacent (diagonally) red squares around the first square, then 2 more around the 2nd blue square st the red squares form a square C like shape. Then, for the 3rd blue square, place 2 more red squares around the outside so that blue placing a square to complete the 2x2 is forced to be in the corner and then the process terminates.

pi_is_3.14 wrote: To prove 4 is always possible, see that all 3 or less tile cases require > 2n red tiles to completely cover the entire perimeter. 4 is the maximum because R can force the 2x2 square case. Simply put 2 adjacent (diagonally) red squares around the first square, then 2 more around the 2nd blue square st the red squares form a square C like shape. Then, for the 3rd blue square, place 2 more red squares around the outside so that blue placing a square to complete the 2x2 is forced to be in the corner and then the process terminates. What if B tries to form two separate polygons and connect them

This was difficult to write-up, hopefully the problem is trivial enough that this solution is understandable The answer is $4$. $R$'s strategy is simply to try to surround $B$'s polygon with red squares. $R$ behaves greedily at every move and after each move $B$ makes, he colours two white (if they exist) squares adjacent to the newly added blue one red. It is easy to see that using this strategy $B$ can construct a polygon with up to $4$ squares. To prove that $B$ can always get away with a polygon with area $4$, just note that since $R$ colours $2$ squares at each move, $B$ can always colour a non-coloured square adjacent to one of the squares he coloured in his previous move. Continuing this way we can easily see that $B$ can colour $4$ squares forming a polygon.

does one need to reduce the problem such that each blue polygon is "isolated"?

I claimed that any three collinear tiles cannot all be blue (including diagonally) if R plays optimally. Therefore, the maximum is 4.

EvanZ wrote: I claimed that any three collinear tiles cannot all be blue (including diagonally) if R plays optimally. Therefore, the maximum is 4. tfw staircase

How many points lost for missing the staircase?

probably 7

eduD_looC wrote: How many points lost for missing the staircase? not sure Also i have seen solutions that go like 1) prove that red can prevent 3 in a row 2) prove that red can prevent the staircase I want to point out that this is actually a fakesolve, because if you did this solution, you did not show that red can prevent both of them at the same time, even if you showed that they can be prevented seperately Same thing applies to any solution that shows that Red can prevent each of the 12 pentominoes by breaking into cases on each pentomino etc I did the 2x2 grid partition which was probably intended sol

eduD_looC wrote: How many points lost for missing the staircase? Staircase?

idk about the staircase, the only rigorous, easy to understand sol i know of right now is the 2x2 partitions that i did

john0512 wrote: eduD_looC wrote: How many points lost for missing the staircase? not sure Also i have seen solutions that go like 1) prove that red can prevent 3 in a row 2) prove that red can prevent the staircase I want to point out that this is actually a fakesolve, because if you did this solution, you did not show that red can prevent both of them at the same time, even if you showed that they can be prevented seperately Same thing applies to any solution that shows that Red can prevent each of the 12 pentominoes by breaking into cases on each pentomino etc I did the 2x2 grid partition which was probably intended sol

in fact I believe these moves are pretty much equivalent to the 2x2 partition solution (correct me if I’m wrong), except a bit more restrictive in some places (such that if B places 2 blues in a single 2x2 square)

Also, after doing the 2x2 partitions, I argued that you can't have a blue path from the corner of one 2x2 to the opposite corner, so the polygon can only have one cell in each 2x2 And you obviously can't have 5 cells in 5 different 2x2's that are all connected I don't get docked for just stating the second part right (the part about 5 different cells in 5 different 2x2's can't be connected) I wouldn't think so but im literally so scared cuz if i get a -1 dock anywhere im like dead so many people got 35

john0512 wrote: Also, after doing the 2x2 partitions, I argued that you can't have a blue path from the corner of one 2x2 to the opposite corner, so the polygon can only have one cell in each 2x2 And you obviously can't have 5 cells in 5 different 2x2's that are all connected I don't get docked for just stating the second part right (the part about 5 different cells in 5 different 2x2's can't be connected) I wouldn't think so but im literally so scared cuz if i get a -1 dock anywhere im like dead so many people got 35 You shouldn’t get docked for that

john0512 wrote: Also, after doing the 2x2 partitions, I argued that you can't have a blue path from the corner of one 2x2 to the opposite corner, so the polygon can only have one cell in each 2x2 And you obviously can't have 5 cells in 5 different 2x2's that are all connected I don't get docked for just stating the second part right (the part about 5 different cells in 5 different 2x2's can't be connected) I wouldn't think so but im literally so scared cuz if i get a -1 dock anywhere im like dead so many people got 35 *so many people think they got 35 If you got docked somehow, then other people might have gotten docked too

I will put my strategy for $R$ for upper bound: whenever $B$ colors a cell with odd sum of its coordinates (using usual planar cartesian coordinates; in particular, up is positive $y$ direction and to the right is positive $x$ direction), $R$ colors the adjacent cells below and to the left if possible. If the cell to the left was already colored but the cell above was not, then $R$ colors the cell above instead, and if the cell below was already colored, $R$ colors the cell to the right if that was not colored yet. If there are two white adjacent cells, then $R$ colors both of them. If there is less than that many adjacent white cells, then $R$ colors the rest and uses the remainder of the turn to color any other cell. Now, $R$'s strategy for responding to a cell with even sum of its coordinates is to flip this about a line of slope $-1$. It is easy to see that this strategy restricts the polygons to inside infinite staircases. Furthermore, it is easy to see that two separate clusters of blue cells cannot be connected if $R$ uses this strategy. Now, whenever $B$ builds a cluster, it must be starting from two adjacent cells, and then it can be easily shown that $B$ can only put one more blue cell in each of two directions before getting blocked in the corresponding direction (obviously the solution I am putting here is a sketch of the proof). Remark: I think this a natural solution motivated by the equality case of a staircase (indeed, a staircase is all that B can achieve in this solution, if B is trying to get a score of 4). However, the solution with 2 by 2 squares is much faster and nicer, so unfortunately this solution in comparison is not as nice. The solution with the 2 by 2 squares is motivated by the equality case of a 2 by 2 square, which is the only equality case permitted to B in that solution.

"Tile an L, Take an L." :p Anyway, 7- or 0+? It seems like u/MathJams had a similar overall idea, but my finish was messier... The answer is $\boxed{4}$. Claim. $B$ can score at least $4$. Proof. $B$ can color $2$ adjacent squares blue on his first two turns; take cases on how many of $R$'s first $4$ squares border $B$'s $2\times1$ rectangle (details omitted). In any case, $B$ can produce $3$ "free" edges after his third turn, leaving at least $1$ free edge to expand on with his fourth turn. $\Box$ Claim. $R$ can limit $B$'s score to at most $4$. Proof. The key is that whenever $B$ colors a square $B_k$ nonadjacent from all existing blue squares, $R$ can color two adjacent squares to $B_k$ so that $B_k$ cannot $\textit{see}$ any other blue squares, where two blue squares are said to see each other if they are aligned horizontally or vertically with no squares (red or blue) in between them. To see why, we use an inductive argument; the base case is trivial. Then, suppose that his $n+1$th turn $B$ colors $B_{n+1}$ in a setting where no blue squares see each other (from turn $n$, the inductive assumption). Clearly, $B_{n+1}$ can see at most $4$ squares ($1$ in each direction), but in fact $B_{n+1}$ cannot see $2$ squares in opposite directions (north and south or west and east), because that would mean those $2$ squares had seen each other from turn $n$, contradiction. So if say $B_{n+1}$ sees a northern square along the vertical axis and an eastern square along the horizontal axis, $R$ can color the squares directly to the north and east of $B_{n+1}$, obstructing all sight.

Essentially, there are two cases to consider:

; direct experimentation reveals that in any possible case, $R$ can limit $B$'s expansion to $2$ additional squares, giving an area of $\le4$ as desired. $B$ forms an L. But the only way for $B$ to expand is to form a square, which $R$ can readily enclose as desired. Remark that this is analogous to the case mentioned before, but the author wished to point out that $B_k$ can be placed adjacent to $2$ squares, which are themselves diagonally adjacent. However it is impossible for $B_k$ to be placed so such that the $3$ blue squares form a line, since that would imply the $2$ existing squares saw each other, which by assumption is impossible. In all cases, $R$ can limit $B$'s maximal area to at most $4$, as claimed. $\Box$ The result follows by combining the two claims. $\blacksquare$

HonestCat wrote: pi_is_3.14 wrote: To prove 4 is always possible, see that all 3 or less tile cases require > 2n red tiles to completely cover the entire perimeter. 4 is the maximum because R can force the 2x2 square case. Simply put 2 adjacent (diagonally) red squares around the first square, then 2 more around the 2nd blue square st the red squares form a square C like shape. Then, for the 3rd blue square, place 2 more red squares around the outside so that blue placing a square to complete the 2x2 is forced to be in the corner and then the process terminates. What if B tries to form two separate polygons and connect them (note this is just a sketch) If B puts 2 diagonally adjacent, then pretty much same. R must force 2 bends to close the figure (as perimeter is 2 + 2 * # of squares). For $n \ge 5$, at least 2 of the moves by B must be connecting moves (connecting blue squares) and red before those moves, can simply block off and force a "bend".

Here is a working casework solution: Essential main idea is that $R$ 'normally' just responds by coloring the squares beneath and to the right of what $B$ colored. However, if the square $B$ just colored is either diagonally down-left or up-right of a previous $B$, you have one extra $R$ move and use it to "wrap/separate" the $B$'s. The key claim is that by this, $B$ "cannot" connect two polygons in one move, as if this was the case, then the empty cell that $B$ just colored has to have two blue neighbors, which can be shown be casework to be impossible by our algorithm. Thus, every blue polygon can only increase by area 1 at most each move. Now, casework suffices when dealing with when $B$ increases the area of a blue polygon from 1 to 2, 2 to 3, and finally 3 to 4, by trying to "wrap" it in a 2x2 area.

mathboy100 wrote: tbh i think a lot of ppl lost points for not rigorous sols I kind of wish people would just write "wrong" or "incomplete" instead of "not rigorous" everywhere, otherwise people get the impression that rigor is something different from correctness. I am also annoyed to report the original solution I thought I had to this problem was outright incorrect (the algorithm I provided that I thought was winning did not actually work). Frikkin' staircase.

v_Enhance wrote: mathboy100 wrote: tbh i think a lot of ppl lost points for not rigorous sols I kind of wish people would just write "wrong" or "incomplete" instead of "not rigorous" everywhere, otherwise people get the impression that rigor is something different from correctness. I am also annoyed to report the original solution I thought I had to this problem was outright incorrect (the algorithm I provided that I thought was winning did not actually work). Frikkin' staircase. Good point, I should've used incomplete instead. The staircase had me during the test until I noticed the 2x2 strategy. idk if this problem was easy enough for a p4.

Does this strategy work (corralling the blue into an o tetromino):

aryabhata000 wrote: Does this strategy work (corralling the blue into an o tetromino): I think you need to refine (4). For example, you could have something like this after B plays twice: . . R . R B R B x Here, it is important to say that R should play in the square marked with an x with the extra move they still have. There is another similar case that we should consider. One strategy for B that is very useful in general for testing if your algorithm works is the following sequences of moves: (0,0), (2,2), and (1,1) in that order.

First, we can easily define a strategy for R to limit B to a score of 4. Second, we need to prove the R can't kill B when B has 3 points or less. To prove this, define $L(n)=\text{The number of white squares adjacent to Blue after B put n squares}$. Obviously, when $L(2)=6$, but R only has 4 squares, so he can't kill B. There are only 2 cases for Blue. $L(3)=7\text{ or } 8$. But R only have 6 squares, so he can't kill B. Hence, 4 is the largest point B can get.

Is it allowed to create a process for that R can restrict B through drawing a bunch of figures and pathways? Since it also says to make it largest. Do I still need to prove that 1, 2, 3, are achievable? What I mean is that I use drawings in a grid combo solution without much terminology.

don't try to make the casework solution work you aren't learning splat

Partition the grid into $2\times 2$ boxes. $B$ can color squares blue as follows: for every square $R$ colors red, $B$ colors the two squares adjacent to it in the same $2\times 2$ box blue (or any two squares if they are already blue). Clearly there are no adjacent red squares in one $2\times 2$ box. It follows that $4$ is the maximum. The construction is trivial. $\square$

The answer is $\boxed{4}.$ We partition the grid into $2 \times 2$ squares. We see that $B$ can simply color infinitely far away if his strategy doesn't work (the strategy is as above).

for a sec i misread as blue getting 2 colors per turn and i was like "is the answer not 6+?"