Prove that
Where 
Prove that
Let 
Prove that
Let 
Prove that
be the unit circle in the complex plane. Let 
be the map given by 
.
and 
for 
.
such that 
is called the period of 
.
of period 
.
)
such that![\[
x+f(xy)=f(1+f(y))x
\]](http://latex.artofproblemsolving.com/4/3/3/433f95836dad1224754d480aff8432ef033a37cb.png)
for all 
.
Y by Durjoy1729, Moaaz, Carpemath, Davi-8191, anantmudgal09, Davrbek, Amir Hossein, yayitsme, OlympusHero, KhongMinh, megarnie, Lamboreghini, Adventure10, Mango247, DroneChaudhary, lian_the_noob12, deplasmanyollari
A site is any point 
in the plane such that 
and 
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
. 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
such that Amy can ensure that she places at least red stones, no matter how Ben places his blue stones.
Proposed by Gurgen Asatryan, Armenia
in the plane such that 
and 
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
. 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
such that Amy can ensure that she places at least red stones, no matter how Ben places his blue stones.Proposed by Gurgen Asatryan, Armenia
This post has been edited 3 times. Last edited by djmathman, Jun 16, 2020, 4:03 AM
Reason: problem author
Reason: problem author
.
-
) so I haven't done the problem yet but it looks really nice; I really like combinatorial geometry.
blocks and label them as follows
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 
for a 
table.
table the answer should be 
and here is the proof: If we look at a 
block, it's easy to conclude that we can place at most 
such blocks, we conclude that on a 
is the set of all configurations in which there are placed 
So 
![[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]](http://latex.artofproblemsolving.com/1/9/2/1924ebc7591abdba81f955903f8d89690467a378.png)
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 
on the sites with sites ![[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]](http://latex.artofproblemsolving.com/b/5/c/b5cf4e073db01002f93c1f89658cdd14b941ab0e.png)
Color grid as a chessboard, so Amy can occupy half of all black sites, which suffices.
onto smaller grids 
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 ![[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]](http://latex.artofproblemsolving.com/c/0/0/c00c57e3160d782799dde424a52e0cf81e370517.png)
.
.
at smallers 
it is enoygth to prove that can be sure that Amy can not place more than 
.
.
![\[
\begin{bmatrix}
1 & 2 & 3 & 4 \\
3 & 4 & 1 & 2 \\
2 & 1 & 4 & 3 \\
4 & 3 & 2 & 1
\end{bmatrix}
\]](http://latex.artofproblemsolving.com/6/f/1/6f1fabf5990c5e33e8eb37cd0fbd467387f8455a.png)
Any site Amy occupies must correspond to one number in some 
site of each number, meaning 
.
.
![[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]](http://latex.artofproblemsolving.com/5/1/2/512f0496f9dc57537a66f97bdd8dc56ec2cfde81.png)
Divide the grid up into 
away from the one that she first put down, meaning amy can never play twice in the same region. As each region has 
,
squares where each row is one unit apart.
Now, we must minimize Amy's stones here. WLOG, say Amy picks A. Arbitrarily, Ben picks the A that is not 
.
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 
of the following:
away. This clearly limits Alice to a quarter of each color meaning she can get at most 
![[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]](http://latex.artofproblemsolving.com/3/4/b/34b90eda1b9a70c42c38335d6629bf7efcb1db8f.png)
moves, Amy can always find one of the 
This is because there are 
.
Call a group of stones with the same color within a 
}
.![\[
(1+2k, 1+2r) \text{ or } (2k, 2r)
\]](http://latex.artofproblemsolving.com/1/8/5/185b70431bdc9a630a4266a4657975ade1d1ec28.png)
where 
and 
are integers.
.![\[
\left\lceil \frac{200}{2} \right\rceil = 100
\]](http://latex.artofproblemsolving.com/e/8/2/e82d01afcafd816058d7ba8b2566eb001aa50edf.png)
red stones.
}
sub-grid separately. Redefine its vertices as 
where 
.
.![\[
(5-x, 5-y)
\]](http://latex.artofproblemsolving.com/f/8/d/f8d71dc01267fe6328967e8663e9d659017630ba.png)
![[asy]
size(300);
pen blackpen = black;
pen graypen = gray;
pen redpen = red;
pen bluepen = blue;
pen greenpen = green;
pen orangepen = rgb(1, 0.55, 0);
pen purplepen = purple;
pen shadecolor = rgb(1, 0.9, 0.85);
pair A = (0,0), B = (3,0), C = (3,3), D = (0,3);
pair N = (0,2), O = (0,1), P = (1,1), Q = (1,0), R = (2,0), S = (2,1), L = (2,2), K = (1,2), M = (3,2), T = (3,1);
pair[] gridpoints = {A, B, C, D, N, O, P, Q, R, S, L, K, M, T};
pair[] labels = {
(0,3), (1,3), (2,3), (3,3), // D, I, J, C
(0,2), (3,2), // N, M
(0,1), (3,1), // O, T
(0,0), (3,0), // A, B
(1,2), (2,2), // K, L
(1,1), (2,1), // P, S
(1,0), (2,0) // Q, R
};
string[] labeltext = {
"D", "I", "J", "C",
"N", "M",
"O", "T",
"A", "B",
"K", "L",
"P", "S",
"Q", "R"
};
pen[] labelcolor = {
bluepen, redpen, orangepen, purplepen,
greenpen, greenpen,
redpen, orangepen,
blackpen, graypen,
blackpen, graypen,
bluepen, purplepen,
greenpen, greenpen
};
// Draw grid lines
draw((0,0)--(0,3), graypen);
draw((1,0)--(1,3), graypen);
draw((2,0)--(2,3), graypen);
draw((3,0)--(3,3), graypen);
draw((0,0)--(3,0), graypen);
draw((0,1)--(3,1), graypen);
draw((0,2)--(3,2), graypen);
draw((0,3)--(3,3), graypen);
// Shade inner square
filldraw((1,1)--(1,2)--(2,2)--(2,1)--cycle, shadecolor);
// Draw outer border
draw(A--D--C--B--cycle, orangepen+linewidth(1.2));
// Place dots
dot(D, bluepen); dot(C, purplepen);
dot(N, greenpen); dot(M, greenpen);
dot(O, redpen); dot(T, orangepen);
dot(A, blackpen); dot(B, graypen);
dot(K, blackpen); dot(L, graypen);
dot(P, bluepen); dot(S, purplepen);
dot(Q, greenpen); dot(R, greenpen);
// Label points
for (int i=0; i<labels.length; ++i)
{
label(Label(labeltext[i], labelcolor[i]), labels[i], dir(90));
}
[/asy]](http://latex.artofproblemsolving.com/0/0/2/00201eab37b1df7fed5f5a14fbae7cd25e90d9b4.png)
![\[
\frac{200}{8} \times 4 = 100
\]](http://latex.artofproblemsolving.com/0/4/8/04808e5d05fa889c4c85eb2c6d38e1bda3c4cc05.png)
stones in total.![\[
K = 100
\]](http://latex.artofproblemsolving.com/9/2/4/9242de7667d86d17464ccfd962be100b28889480.png)
as desired.
so Amy is ensured to get at least half of the black squares. Hence she can attain at least 
from the top row, Ben reacts by placing a blue stone on the 
.
.
such center.
stones using not only the 
x 
,
