The problem is about chessboard and placing knights that don't hit each other

jdevine wrote: On her turn, Amy places a new red stone on an unoccupied site such that the distance $\sqrt{5}$. Unfinished sentence fragment?

I'm not on the IMO ( ) so I haven't done the problem yet but it looks really nice; I really like combinatorial geometry. Edit: wow, I thought it was combinatorial geometry when I first read it.

Divide the numbers into $4 \times 4$ blocks and label them as follows $$A B C D$$$$C D A B$$$$B A D C$$$$D C B A$$ Each of the four letters forms a cycle from which no two adjacent letters can be taken, so whenever Amy plays in one cycle, Ben plays in the opposite position in the cycle, so Amy can take at most one number from each cycle, and thus takes at most $100$ numbers. To see that $K = 100$ is feasible simply color in a chessboard pattern and always take black points. There are 200 of them so at least 100 can be taken, and no two of them are at distance $\sqrt{5}$

That is it! I didn't solve it yet, but this years problems are really close to IMO 2015, one of the great years. So I like this! 1st and 4th problems of the last year, IMO 2017, NT(solution by mod 3) and Geo (solution by couple of triangular simmilarity) were just peace of kidding!!!

juckter wrote: Really easy, even for P4. Not so easy I think, there are some people who solved last year's P5 and didn't solve this one.

The example is based on a table with white and black.To prove it,you just need to study the 4*4table

Solution : We claim the required $K$ is $100$. We colour the lattice as shown : [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(4.275865116895659cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -148.7496634482596, xmax = -144.47379833136395, ymin = 50.876351507806454, ymax = 55.226795667438786; /* image dimensions */ pen wwqqcc = rgb(0.4,0.,0.8); pen ffdxqq = rgb(1.,0.8431372549019608,0.); pen ttffqq = rgb(0.2,1.,0.); filldraw(circle((-148.10000000000093,54.499629629629744), 0.3), wwqqcc, linewidth(2.) + wwqqcc); filldraw(circle((-147.10000000000093,54.499629629629744), 0.3), red, linewidth(2.) + red); filldraw(circle((-146.10000000000093,54.499629629629744), 0.3), ttffqq, linewidth(2.) + ttffqq); filldraw(circle((-145.10000000000093,54.499629629629744), 0.3), ffdxqq, linewidth(2.) + ffdxqq); filldraw(circle((-148.10000000000093,53.499629629629744), 0.3), ttffqq, linewidth(2.) + ttffqq); filldraw(circle((-147.10000000000093,53.499629629629744), 0.3), ffdxqq, linewidth(2.) + ffdxqq); filldraw(circle((-146.10000000000093,53.499629629629744), 0.3), wwqqcc, linewidth(2.) + wwqqcc); filldraw(circle((-145.10000000000093,53.499629629629744), 0.3), red, linewidth(2.) + red); filldraw(circle((-148.10000000000093,52.499629629629744), 0.3), red, linewidth(2.) + red); filldraw(circle((-147.10000000000093,52.499629629629744), 0.3), wwqqcc, linewidth(2.) + wwqqcc); filldraw(circle((-146.10000000000093,52.499629629629744), 0.3), ffdxqq, linewidth(2.) + ffdxqq); filldraw(circle((-145.10000000000093,52.499629629629744), 0.3), ttffqq, linewidth(2.) + ttffqq); filldraw(circle((-148.10000000000093,51.499629629629744), 0.3), ffdxqq, linewidth(2.) + ffdxqq); filldraw(circle((-147.10000000000093,51.499629629629744), 0.3), ttffqq, linewidth(2.) + ttffqq); filldraw(circle((-146.10000000000093,51.499629629629744), 0.3), red, linewidth(2.) + red); filldraw(circle((-145.10000000000093,51.499629629629744), 0.3), wwqqcc, linewidth(2.) + wwqqcc); /* draw figures */ /* dots and labels */ clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] Now observe that this colouring of the lattice divides it into squares of the same colour. Amy can't place a stone on two adjacent squares of this form. So if Ben places a stone on the opposite vertex of the square, then Amy can't place her stone on any vertex of this square. So at most $100$ red stones can be placed. Now to see that this is realizable, just notice that taking half of the points of the same colour in the usual chessboard colouring works.

Consider a $20 \times 20$ chessboard, so that the lattice points are at the center of each cell. The centers of two cells are at distance $\sqrt{5}$ if and only if you can go from one cell to the other in one step of the knight. Knights change colors on each step. Therefore, you can place knights on all of the cells of the same color, and no two of them will hit each other. Therefore, Amy can ensure she will place at least 100 stones, by placing all of them on cells of the same color. Ben can ensure Amy won't be able to place more than 100 stones by following this strategy: Divide the chessboard in 25 small boards of $4 \times 4$. On each turn, Ben will place a stone in the same $4 \times 4$ board that Amy placed her last stone, in the cell that is symmetric to the cell where Amy placed her stone, with respect to the center of the $4 \times 4$ board. To prove that, color a $4\times 4$ board as shown below. If Ben follows the outlined strategy, Amy won't be able to place stones on cells of the same color in a given $4\times 4$ board. This means Amy will be able to place at most 4 stones on each $4 \times 4$ board, and therefore at most 100 stones on the entire $20 \times 20$ chessboard. $\textcolor{red}{\blacksquare}\ \textcolor{blue}{\blacksquare}\ \textcolor{green}{\blacksquare}\ \textcolor{yellow}{\blacksquare}$ $\textcolor{green}{\blacksquare}\ \textcolor{yellow}{\blacksquare}\ \textcolor{red}{\blacksquare}\ \textcolor{blue}{\blacksquare}$ $\textcolor{blue}{\blacksquare}\ \textcolor{red}{\blacksquare}\ \textcolor{yellow}{\blacksquare}\ \textcolor{green}{\blacksquare}$ $\textcolor{yellow}{\blacksquare}\ \textcolor{green}{\blacksquare}\ \textcolor{blue}{\blacksquare}\ \textcolor{red}{\blacksquare}$ We conclude the greatest possible value of $K$ is $100$

juckter wrote: Divide the numbers into $4 \times 4$ blocks and label them as follows $$A B C D$$$$C D A B$$$$B A D C$$$$D C B A$$ Each of the four letters forms a cycle from which no two adjacent letters can be taken, so whenever Amy plays in one cycle, Ben plays in the opposite position in the cycle, so Amy can take at most one number from each cycle, and thus takes at most $100$ numbers. To see that $K = 100$ is feasible simply color in a chessboard pattern and always take black points. There are 200 of them so at least 100 can be taken, and no two of them are at distance $\sqrt{5}$ Really easy, even for P4. This is also my solution. I did not find this "really easy" and I think if I was doing this in the contest it would have taken me almost as long as P3 took me!

Yeah, I think I grossly misjudged the difficulty of the solution. I had solved the some very similar problems before, so it felt very natural to adapt the idea to this problem.

The answer is $K = 100$. Amy can obtain 100 red stones by only playing on checkerboard-colored black squares only. Next we show that Ben can limit Amy to 100 red stones. Construct a graph $G$ on the sites with sites $\sqrt{5}$ away adjacent. If we can partition $G$ into 100 4-cycles, then Ben can play in the site opposite to the one by Amy in its cycle. This works as Amy can only get one stone in each 4-cycle. To partition $G$ in this manner, first split it into 25 $4 \times 4$ subgrids, and then split each subgrid as follows. [asy][asy] pair[][] A = { {(0, 0), (1, 2), (2, 1), (3, 3)}, {(0, 1), (1, 3), (2, 0), (3, 2)}, {(0, 2), (1, 0), (2, 3), (3, 1)}, {(0, 3), (1, 1), (2, 2), (3, 0)}}; for (int i = 0; i < 4; i += 1) { for (int j = 0; j < 4; j += 1) { filldraw(circle(A[i][j], 0.15), i % 2 == 0 ? (i == 0 ? lightred : lightgreen) : (i == 1 ? lightblue : lightcyan)); }} [/asy][/asy]

This is my approach though the solution revolves around the same idea. Consider a $4\times4$ board. Divide the board into three parts, say A(the corner sites), B(the sites on the edges excluding corners) and C (the middle 4 sites).Let us start with C. Now one overlap of the sites cancelled (or to-be cancelled) would provide 4 red stones. Now we place the next stone(red) in such a way so as to have atleast one overlap(knight's move). Checking gives us that after the placement of Ben's third stone, at most 15 sites are covered, and so Amy can place her fourth stone. A similar case chase for starting positions in B and A gives us that Amy can still place her four stones. So Amy can place atleast $4$ red stones in a $4\times 4$ board. Next we show that for putting an additional $4\times 4$ board adjacent to the previous one, the number of stones in that board is still preserved. And hence we can successfully partition the $20\times 20$ board into $4\times 4$ boards. So the answer is $100$.

Amy gets 100 by coloring like a chessboard and always playing on black squares. Ben blocks 101 by dividing into 4x4 subboards: he will always play in the same subboard that Amy uses. When Amy plays in a subboard, Ben plays in the square centrally-opposite to it (inside the subboard). There can never be 5 Amy-stones in a subboard, since there's at most 1 for each letter W,X,Y, Z in the following configuration: WXYZ YZWX XWZY ZYXW So there's at most 100 Amy-stones at the end.

Sorry for bad english I guess

Nice, very nice generalization

The all alternative diagonals are the safe place for red stones and Ben gets blue one . Now after 200 terms they have figured the best 100, 100 configuration. Which is max. So ans is 100

Define two points to be attacking if they are a distance of $\sqrt{5}$ apart. Color a point white if its sum of coordinates is even, black otherwise. Note that any pair of attacking points are different colors. Amy can place stones in half of the points of one color, so she can place at least 100 stones. Now, split the 20x20 grid into 25 4x4 grids. We then color the cells in each 4x4 grid with 4 different colors in the following pattern: $$\begin{matrix} 1 &3 &2 &4\\ 2 &4 &1 &3\\ 3 &1 &4 &2\\ 4 &2 &3 &1\\ \end{matrix}$$ Note that for the 4 points in each color, each point attacks exactly 2 other points of that color. Therefore, once Amy places a stone, Ben can place a stone in the unique point that is the same color as Amy's stone but doesn't attack it. Then, Amy can only claim one point of each color, and since there are $4\cdot5^2$ colors, Amy can place at most 100 stones. Therefore, the answer is 100.

We claim that the answer is $100.$ The answer $100$ is obviously achievable, as Amy can occupy at least half of the black squares, given we tile the board like a checkerboard. Now, we give a different tiling: we split the board into twenty-five $4\times 4$ boards, colored as such: Now, whenever Amy places a stone, Bob can place the stone in the only square of the same color, such that it is not distance $\sqrt{5}.$ Note that this ensures Amy can only place one stone per color, four stones per $4\times 4$, and in total $100$ stones, so we are done.

We divide the 20 by 20 grid into 25 small grids of 4x4 like $$\begin{matrix} A &B &C &D\\ C &D &A &B\\ B &A &D &C\\ D &C &B &A\\ \end{matrix}$$For any type of site (A, B, C, or D) that Amy chooses, Ben can choose any of the other three types as well or the one unattacked square of the same type. If Ben chooses a site of a different type, Amy can claim the unoccupied site of same type as her first stone, and she would also be able to claim 2 more sites in the square. If Ben chooses a site of the same type, Amy can claim one site each for the other three types, meaning she still gets 4 stones in the square. Then, since Amy can get 4 stones of each square for 25 squares, she can place at least $\boxed{100}$ stones

We claim the answer $K=100.$ Color grid as a chessboard, so Amy can occupy half of all black sites, which suffices. Now consider the following strategy for Ben. Let's split grid $20\times 20$ onto smaller grids $4\times 4,$ in each of them pick four different cycles as below. When Amy firstly occupies site in one cycle, let Ben occupies the opposite site in this cycle. Thus Amy can place at most one stone in each of $100$ cycles, which suffices. [asy][asy] unitsize(20); draw ((0,0)--(2,1)--(3,3)--(1,2)--(0,0), red); draw ((0,3)--(1,1)--(3,0)--(2,2)--(0,3), green); draw ((1,0)--(3,1)--(2,3)--(0,2)--(1,0), blue); draw ((2,0)--(3,2)--(1,3)--(0,1)--(2,0), yellow); for(int x = 0; x < 4; ++x){ for(int y = 0; y < 4; ++y){ dot((x,y)); } } [/asy][/asy]

orthocentre wrote: A site is any point $(x, y)$ in the plane such that $x$ and $y$ are both positive integers less than or equal to 20. Initially, each of the 400 sites is unoccupied. Amy and Ben take turns placing stones with Amy going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance between any two sites occupied by red stones is not equal to $\sqrt{5}$. On his turn, Ben places a new blue stone on any unoccupied site. (A site occupied by a blue stone is allowed to be at any distance from any other occupied site.) They stop as soon as a player cannot place a stone. Find the greatest $K$ such that Amy can ensure that she places at least $K$ red stones, no matter how Ben places his blue stones. Proposed by Gurgen Asatryan, Armenia $K=100$. Amy can be sure for $K>=100$.Color the pointw black and white then Amy place stones at only White points so $K>=100$. Ben can be sure for $K<=100$.To do this he devise the chessdoard $20*20$ at smallers $4*4$ it is enoygth to prove that can be sure that Amy can not place more than $4$ stones at each $4*4$ for this Ben following the below strategi: He place in the same $4*4$ in the same nymber.The numbers of the $4*4$ are: 1342 5786 6875 2431

Solved with aryabhata000 The answer is $\boxed{K = 100}$. We first show that $K \leq 100$. To prove this, notice that we may partition the sites into $25$ $4 \times 4$ regions. We will label each region as such: \[ \begin{bmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \\ 2 & 1 & 4 & 3 \\ 4 & 3 & 2 & 1 \end{bmatrix} \]Any site Amy occupies must correspond to one number in some $4 \times 4$. Note that if Ben occupies the site diagonally opposite the site Amy occupies (with the same number in the same $4 \times 4$) on his next turn, then Amy can no longer occupy any sites of that number in that $4 \times 4$. Thus, for each $4 \times 4$ grid, Amy can guarantee at most $1$ site of each number, meaning $K \leq 4 \times 25 = 100$. We now show that $K \geq 100$. To see this, we color the sites in a checkerboard pattern, and notice that no two light squares are a distance of $\sqrt{5}$ away from each other. Therefore, Alice can guarantee at least $100$ light squares. Combining these, we obtain $K = 100$, as desired.

First of all realize that Amy can guarantee $100$ by taking a white square on each of her turns, because knights only attack opposite colors. To show Ben can guarantee $100$, it suffices to show he can guarantee $4$ in a $4$ by $4$ grid. Consider the following grid: $$ABCD$$ $$cdab$$ $$badc$$ $$DCBA$$ When Amy picks an uppercase letter, she blocks the lowercases of the same letter, so Bob can block the other uppercase of the same letter. The symmetric thing also holds if Amy picks a lowercase letter. Thus, Ben can limit Amy to at most $4$ sites, $1$ for each letter.

The answer is $100$. Amy can guarentee this by placing her first $100$ stones on squares of the same chessboard color. Claim: Ben can limit Amy to $100$ stones Proof. Consider this image of a $4\times 4$ square [asy][asy] draw((0,0)--(4,0)); draw((0,1)--(4,1)); draw((0,2)--(4,2)); draw((0,3)--(4,3)); draw((0,4)--(4,4)); draw((0,0)--(0,4)); draw((1,0)--(1,4)); draw((2,0)--(2,4)); draw((3,0)--(3,4)); draw((4,0)--(4,4)); filldraw(box((0,0),(1,1)),cyan, black); filldraw(box((2,1),(3,2)),cyan, black); filldraw(box((1,2),(2,3)),cyan, black); filldraw(box((3,3),(4,4)),cyan, black); filldraw(box((1,0),(2,1)),lightred, black); filldraw(box((3,1),(4,2)),lightred, black); filldraw(box((2,3),(3,4)),lightred, black); filldraw(box((0,2),(1,3)),lightred, black); filldraw(box((2,0),(3,1)),lightgreen, black); filldraw(box((3,2),(4,3)),lightgreen, black); filldraw(box((1,3),(2,4)),lightgreen, black); filldraw(box((0,1),(1,2)),lightgreen, black); filldraw(box((3,0),(4,1)),lightblue, black); filldraw(box((1,1),(2,2)),lightblue, black); filldraw(box((2,2),(3,3)),lightblue, black); filldraw(box((0,3),(1,4)),lightblue, black); [/asy][/asy] Divide the grid up into $25$ $4\times 4$ subgrids and color each one as shown. The startegy for Ben is if Amy plays in a square inside one $4\times 4$ grid, then Ben plays in the same in the same subgrid that's the same color as the one Amy played and the same chessboard color. It is not hard to check that this is unique and is always a possible move (if Ben couldn't play here then Amy's move before wouldn't be valid). Now, this move means that the other squares left in the region of that color that Amy can play on are each $\sqrt 5$ away from the one that she first put down, meaning amy can never play twice in the same region. As each region has $4$ cells there are $100$ regions implying the claim $\blacksquare$ This claim concludes. Remark: Pretty hard for a 1/4

@Math-Infinity ,he can place in white piece also..

We claim that the answer is $K = 100$ Consider the chessboard coloring; this implies $K \geq 100$ as no two squares of same color have distance $\sqrt{5}$ For the upper bound consider the following coloring, it has 4 cycles; implying $K \leq 4 \cdot 25 = 100$, $\therefore K = 100$

We use checkerboard coloring to colour alternating white and black squares to see that Amy is guaranteed to colour at least half of the black squares, so $K \geq 100$. Now, divide the grid into $4\times4$ squares where each row is one unit apart. $$\text{A B C D}$$$$ \text{C D A B}$$$$\text{B A D C}$$$$\text{D C B A}$$Now, we must minimize Amy's stones here. WLOG, say Amy picks A. Arbitrarily, Ben picks the A that is not $\sqrt{5}$ units away from Amy's letter (since Amy can't pick the other 2 A's). Hence Amy is forced to pick another letter, say B. Similarly, Ben picks the B that is not $\sqrt{5}$ units away from B. Similarly, Amy is forced to pick one C and one D. So she minimally picks $4$ out of the $4\times4$ blocks, hence $K\leq 4*25 = 100$. From these two inequalities, it follows that $K = 100$.

Note that $K\ge 100$ simply by checkboard coloring the grid and Alice placing her stones on one color only. She can guarantee half of the stones on this color since no two are $\sqrt 5$ apart. Now color the grid with $25^2$ of the following: $$\text{ABCD}$$$$\text{CDAB}$$$$\text{BADC}$$$$\text{DCBA}$$ Note that Bob can put his stone on the square with the same color that is not $\sqrt5$ away. This clearly limits Alice to a quarter of each color meaning she can get at most $100$ squares and we are done.

This solution is deceptively simple, but I don't think it's that straightforward. It's easy to get caught up doing other things (hence this problem stands as a very good 1/4). The answer is $K=100$. We call points which have the same parity $x$ and $y$-coordinate critical. Claim: We can construct a matching between the set of all critical and non-critical points such that any matched points have a distance $\sqrt 5$ from each other. Proof. Make $25$ copies of the following diagram: [asy][asy] size(6cm); for(int i=0; i<=3; ++i){ for(int j=0; j<=3; ++j){ if((i-j)%2==0){ dot((i, j), red); } else{ dot((i, j)); } } } draw((0, 3)--(2, 2)); draw((1, 3)--(3, 2)); draw((2, 3)--(3, 1)); draw((3, 3)--(1, 2)); draw((0, 2)--(1, 0)); draw((0, 1)--(2, 0)); draw((1, 1)--(3, 0)); draw((2, 1)--(0, 0)); [/asy][/asy] Each segment in this diagram connects a red critical point to a black non-critical point, as needed. $\blacksquare$ Thus, after any $k < 100$ moves, Amy can always find one of the $200$ such matchings that have both sites unoccupied. Futhermore, after $100$ moves, if Ben always places a stone on a site in a matching with both sites empty, every matching will have a stone on it, so Amy cannot make any more moves. This completes the proof.

The max is $100.$ This is because there are $100$ $4$-cycles that Ben can always only allow Amy to have exactly one square in the $4$ cycle. Amy can achieve this by only playing on one color if we color the board like a checkerboard$.\blacksquare$

The answer is $K = \boxed{100}$. Proof that Amy can place at least $K=100$ stones. Color the board like a chessboard. Amy can place stones only on black squares (she doesn't have to worry about the $\sqrt{5}$ restriction). She can make $100$ moves before she runs out of black squares. Proof that Ben can stop Amy from placing more than $100$ stones. Break the region into $4\times 4$ squares, and color them as follows. The number $n$ denotes the $n$th color we have. $$1 2 3 4$$$$3 4 1 2$$$$2 1 4 3$$$$4 3 2 1$$Call a group of stones with the same color within a $4\times 4$ square a loop. Any time Amy places a stone, Ben can place a stone at the opposite place in the same loop This blocks off all the stones in the loop that Amy just placed a stone in. Therefore, Amy can place a maximum of one stone in each loop. The maximum number of stones she can place is the number of loops, which is $100$. This completes the problem.