Can 2 picked squares share an edge?

random314 wrote: Can 2 picked squares share an edge? No because then this two squares have at least two vertex

sorry for making this quite vague at the beginning but it is not necessarily that a square can share only one vertex with a max of one other square. It can be two vertices, however. I've adjusted to make that clear.

We shall gneralize this for any $n \equiv 1 \pmod{4}$. The answer is $k_{max} = 2\left \lfloor \frac{n}{2} \right \rfloor \left \lceil \frac{n}{2} \right \rceil$., where we are given a $n \times n$ grid and where $n \equiv 1 \pmod{4}$. Now obviously any construction is going to use the following shapes: [asy][asy] import olympiad; pair A=origin, B=(0.1,0), C=(0.1,0.1), D=(0,0.1); path p=A--B--C--D--cycle; draw(p); draw(shift(0.2,0)*p); draw(shift(0.2,0.1)*p); draw(shift(0.4,0)*p); draw(shift(0.5,0)*p); draw(shift(0.7,0)*p); draw(shift(0.8,0.1)*p); [/asy][/asy] Call them in order of apperance, figure $a$, figure $b$, figure $c$ and figure $d$. Denote with the real area to be the area formed by the intersection of the perpendiculars of the lower left vertex with the perpendiculars from the upper right vertex. [asy][asy] import olympiad; pair A=origin, B=(0.1,0), C=(0.1,0.1), D=(0,0.1); path p=A--B--C--D--cycle; draw(p); draw(shift(0.2,0)*p); draw(shift(0.2,0.1)*p); draw(shift(0.4,0)*p); draw(shift(0.5,0)*p); draw(shift(0.7,0)*p); draw(shift(0.8,0.1)*p); draw((0.7,0.1)--(0.7,0.2)); draw((0.7,0.2)--(0.8,0.2)); draw((0.8,0)--(0.9,0)); draw((0.9,0)--(0.9,0.1)); [/asy][/asy] Thus we see that the real area of figures $1,2,3$ all stay the same while figure $4$ is $4$. Call the squares, which are distant one unit of distance around the figures the vacuum. Obviously we don't want to have a big vacuum since, we take away a lot of possible squares, since the minimum distance between two figures must be $1$. Obviously figure $4$ has the biggest vacuum and we won't use it., since figures $1$, $2$ and $3$ have a smaller vacuum. Now we claim that the following construction achieves the maximum. The construction: Just use figure $2$ and start from the upper left square and make the minimal distance of $1$ between two figures. [asy][asy] import olympiad; pair A=origin, B=(1,0), C=(1,1), D=(0,1); path p=A--B--C--D--cycle; for(int i = 0;i <= 4;++i){ for(int j = 0;j <=4;++j){ if((j == 0) || (j==1) || (j==3) || (j==4)){ if((i==0) || (i==2) || (i==4)){ filldraw(shift(i,j)*p,black); }else{ draw(shift(i,j)*p); } }else{ draw(shift(i,j)*p); } } } [/asy][/asy] We easily see that we have in each column $\left\lfloor \frac{n}{2} \right\rfloor$ figures and that we have $\left \lceil \frac{n}{2} \right \rceil$ cells marked in the first row. Thus we get that $k$ must be equal to $2\left\lfloor \frac{n}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil$. Now let's assume that in a construction we have that a mixed number of figures $1,2$ and $3$. Obviously when we want to maximize we won't use figure $1$, very often, since it has only $1$ square. Let's also say that we start off, with this pattern of using only figure $2$, but at some row, we get a change (possibly we don't start off with the pattern). But notice that if we break this pattern that in the next row we are going to have more empty squares (i.e. squares that isn't possible to choose) and by continuing this, we are going to have more empty squares then in our construction. Thus we have that $k_{max} = 2\left\lfloor \frac{n}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil$, when $n \equiv 1 \pmod{4}$.

CheshireOrb wrote: In a board of $2021 \times 2021$ grids, we pick $k$ unit squares such that every picked square shares vertice(s) with at most $1$ other picked square. Determine the maximum of $k$. Here is my Solution. First we can colouring $337*4*1011$ with me following: . [asy][asy] import olympiad; pair A=origin, B=(1,0), C=(1,1), D=(0,1); path p=A--B--C--D--cycle; for(int i = 0;i <= 4;++i){ for(int j = 0;j <=4;++j){ if((j == 0) || (j==1) || (j==3) || (j==4)){ if((i==0) || (i==2) || (i==4)){ filldraw(shift(i,j)*p,black); }else{ draw(shift(i,j)*p); } }else{ draw(shift(i,j)*p); } } } [/asy][/asy] Now we are going to prove that we can not colouring more than this. Suppose that we colouring $n$ square with $n>337*4*1011$ First of all every vertice can be use at most $2$ times and the number of the vertice is at most $n$ because any construction is going to use the following shapes: [asy][asy] import olympiad; pair A=origin, B=(0.1,0), C=(0.1,0.1), D=(0,0.1); path p=A--B--C--D--cycle; draw(p); draw(shift(0.2,0)*p); draw(shift(0.2,0.1)*p); draw(shift(0.4,0)*p); draw(shift(0.5,0)*p); draw(shift(0.7,0)*p); draw(shift(0.8,0.1)*p); [/asy][/asy] Now the vertice is $2022*2022$ and we use $4n$so there are $4n-2022^2$ vertice with are using two times but we know that : $4n-2022^2<=n$ wiche mean $n<=2022^/3=337*4*1011$ bone!!! We the same method we can solve the problem in a chessboard $k*k$ with $k=5(mod6)$

Let a unit square have area $1$, and extend the board by surrounding it by a border of side length $\frac{1}{2}$. Consider the connected components of the picked cells, and surround them by as shown. These figures must remain disjoint after picking all the squares. Notice that the fraction inside these figures of picked cells is less than or equal to $\frac{1}{3}$ (just do some calculations). This means that, calculating the area of the extend board (which contains all off these figures) $$k\leq \frac{1}{3} 2022^2=1 362 828$$ We can take the construction given above to show that this upper bound is attainable. The end.

Attachments: