Two players, B and R, play the following game on an infinite grid of unit squares, all initially colored white. The players take turns starting with B. On B's turn, B selects one white unit square and colors it blue. On R's turn, R selects two white unit squares and colors them red. The players alternate until B decides to end the game. At this point, B gets a score, given by the number of unit squares in the largest (in terms of area) simple polygon containing only blue unit squares. What is the largest score B can guarantee? (A simple polygon is a polygon (not necessarily convex) that does not intersect itself and has no holes.) Proposed by David Torres
Problem
Source: USAJMO 2023/4
Tags: hard
24.03.2023 01:14
Tetris reference??!?!?? O piece makes the largest score of 4
24.03.2023 01:35
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
24.03.2023 01:36
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
24.03.2023 01:41
Why were there two combo games on d2 :sob:
24.03.2023 01:41
I literally described an algorithm that R can use to limit B to 4 LOL
24.03.2023 01:56
We can actually prove a stronger version where R chooses to place at most two red squares; this makes the 2×2 squares a little easier to visualize.
24.03.2023 02:02
Does anybody know who proposed this one?
24.03.2023 03:40
hopefully this works
24.03.2023 04:00
i just found the optimal strat for both players and simulated to get the s/z piece
24.03.2023 04:39
MathJams wrote: hopefully this works
similar to what i did
24.03.2023 05:46
ihatemath123 wrote: Does anybody know who proposed this one? David Torres
24.03.2023 05:56
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.
24.03.2023 06:40
yeah @above said this might be his fac problem i agree. tbh i think a lot of ppl lost points for not rigorous sols
24.03.2023 06:57
Why is this problem so good? I love this....
24.03.2023 08:41
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.
24.03.2023 13:56
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
24.03.2023 14:47
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.
24.03.2023 14:49
does one need to reduce the problem such that each blue polygon is "isolated"?
24.03.2023 16:25
I claimed that any three collinear tiles cannot all be blue (including diagonally) if R plays optimally. Therefore, the maximum is 4.
24.03.2023 16:51
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
24.03.2023 18:20
How many points lost for missing the staircase?
24.03.2023 18:27
probably 7
24.03.2023 18:30
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
24.03.2023 18:30
eduD_looC wrote: How many points lost for missing the staircase? Staircase?
24.03.2023 19:09
idk about the staircase, the only rigorous, easy to understand sol i know of right now is the 2x2 partitions that i did
24.03.2023 19:30
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)
24.03.2023 19:43
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
24.03.2023 19:55
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
24.03.2023 20:04
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
24.03.2023 20:42
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.
24.03.2023 20:43
"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 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×1 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. ◻ Claim. R can limit B's score to at most 4. Proof. The key is that whenever B colors a square Bk nonadjacent from all existing blue squares, R can color two adjacent squares to Bk so that Bk cannot 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+1th turn B colors Bn+1 in a setting where no blue squares see each other (from turn n, the inductive assumption). Clearly, Bn+1 can see at most 4 squares (1 in each direction), but in fact Bn+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 Bn+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 Bn+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 ≤4 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 Bk can be placed adjacent to 2 squares, which are themselves diagonally adjacent. However it is impossible for Bk 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. ◻ The result follows by combining the two claims. ◼
24.03.2023 20:53
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≥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".
24.03.2023 22:55
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.
29.03.2023 02:52
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.
29.03.2023 03:12
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.
29.03.2023 05:35
Does this strategy work (corralling the blue into an o tetromino):
Attachments:
p4page1.pdf (394kb)
p4page2.pdf (424kb)
02.04.2023 05:42
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.
06.06.2023 10:05
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)=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 or 8. But R only have 6 squares, so he can't kill B. Hence, 4 is the largest point B can get.
23.02.2024 03:49
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.
23.02.2024 07:07
don't try to make the casework solution work you aren't learning splat
11.03.2024 05:43
Partition the grid into 2×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×2 box blue (or any two squares if they are already blue). Clearly there are no adjacent red squares in one 2×2 box. It follows that 4 is the maximum. The construction is trivial. ◻
17.12.2024 03:54
The answer is 4. We partition the grid into 2×2 squares. We see that B can simply color infinitely far away if his strategy doesn't work (the strategy is as above).
17.12.2024 04:00
for a sec i misread as blue getting 2 colors per turn and i was like "is the answer not 6+?"