An L-shape is one of the following four pieces, each consisting of three unit squares: [asy][asy] size(300); defaultpen(linewidth(0.8)); path P=(1,2)--(0,2)--origin--(1,0)--(1,2)--(2,2)--(2,1)--(0,1); draw(P); draw(shift((2.7,0))*rotate(90,(1,1))*P); draw(shift((5.4,0))*rotate(180,(1,1))*P); draw(shift((8.1,0))*rotate(270,(1,1))*P); [/asy][/asy] A $5\times 5$ board, consisting of $25$ unit squares, a positive integer $k\leq 25$ and an unlimited supply of L-shapes are given. Two players A and B, play the following game: starting with A they play alternatively mark a previously unmarked unit square until they marked a total of $k$ unit squares. We say that a placement of L-shapes on unmarked unit squares is called $\textit{good}$ if the L-shapes do not overlap and each of them covers exactly three unmarked unit squares of the board. B wins if every $\textit{good}$ placement of L-shapes leaves uncovered at least three unmarked unit squares. Determine the minimum value of $k$ for which B has a winning strategy.
Problem
Source:
Tags: combinatorics
26.06.2015 23:56
It's $4$. For $3,2,1$ it's easy to find that A-wins. A marks the center and remain just some cases to check. We will show that no matter how $A$ marks a unit square then $B$ can mark two units so that any placement can't cover a $magical\ unit \ square$. Then 5 units are not covered and since $20=2(mod3)$, we get two more points that are not covered. $X-(x,y)$-means $X$ marks unit $(x,y)$, cartesian coordinates. We study the bottom right $3x3$ square. 1)If $A-(3,3)$ then $B-(4,2)$ and if $A-(5,1)$ then $B-(5,3)$ and we find $magical\ unit\ s.-(5,2)$ else $B-(4,1)$ and we find $magical\ unit\ s.-(5,1)$. 2)If $A$ marks one from $(5,3),(4,2),(4,1)$ then $B$ marks the other two and we get two magical points $(5,1)(5,2)$.If $A$ marked one $magical\ point$ then the other still remains. If A marks one from $(5,2),(4,2),(3,1)$ is done the same way. 3)If $A-(5,1) $ then $B-(4,2)$. 3.1)$A-(4,1)$ then $B-(4,3)$ and we find $magical\ unit\ s.-(5,2)$. 3.2) $A-(5,2)$ then $B-(3,2)$ and we find $magical\ unit\ s.-(4,1)$. 3.3)$A$ marks any other unit, then $B-(4,3)$ and we find $magical\ unit\ s.-(5,2)$. 4) If $A-(4,3)$ then $B-(4,1),(4,2)$ and we find $magical\ unit\ s.-(5,1),(5,2)$. Case $A-(3,2)$ is done the same way. 5) If $A-(5,3)$ then $B-(4,1),(4,2)$ and we find $magical\ unit\ s.-(5,1),(5,2)$. Case $A-(3,1)$ is done the same way.
27.06.2015 12:14
How many students could solve this problem in the olympiad?
28.06.2015 00:53
You can see from official results http://www.dms.rs/jbmo/results/results.html
29.06.2015 13:55
The following solution (for k = 4) was found by a French student. Its originality lies in the fact that B's winning strategy is non-interactive, i.e. does not depend on which squares were marked by A. It is the following. Let us number the columns of the square from A to E, and the lines from 1 to 5. For instance, A1, A5, E1, E5 are the corners of the board. Regardless of what A does, B plays so that the squares B3 and C2 be marked. Then, suppose that two additional squares are marked and that there exists a perfect tiling of unmarked squares with L-shapes: 1. At least one of A1, A2, B1, B2 must be marked. 2. For symmetry reasons, and since at most one of A3, A5, C1, E1 is marked, assume that neither A3 nor A5 is marked. 3. Since covering A3 with the L-shape {A3,A4,B4} would leave A5 untilable, the square A3 has to be covered by a L-shape {A3,A2,B2}. 4. Consequently, A1 and B1 have to be marked, and neither C1 nor E1 is marked. 5. Like in item 3, since neither C1 nor E1 is marked, then A1 and A2 have to be marked. 6. This makes too many marked squares, which shows that, regardless of which squares (in addition to B3 and C2) had been marked, no perfect tiling of unmarked squares with L-shapes worked.
02.07.2015 17:03
Arslan wrote: How many students could solve this problem in the olympiad? It's not a too hard problem for last problem.
02.07.2015 17:06
It can be solved by colouring the squares.
01.08.2015 15:11
The proposer of that problem is the same with the proposer of this year's BMO combinatorics problem, Dimitris Christofides (Demetres in this forum) from Cyprus.