On a chessboard $8\times 8$, $n>6$ Knights are placed so that for any 6 Knights there are two Knights that attack each other. Find the greatest possible value of $n$.
Problem
Source: III Caucasus Mathematical Olympiad
Tags: Chessboard, combinatorics
19.03.2018 16:18
The answer is $10$, the construction is easy, so left for the reader For the proof, color the chessboard in chessboard-like pattern If there're at least $11$ knights, there exists at least $6$ that lie on the same-colored cells. These six knights can't attack each other, contradiction.
07.04.2018 22:48
Clearly $n=10$ One such construction is placing the elements Or entries diagonally $8$ and then placing other $2$ elements according to the rule.
25.01.2021 04:40
$\color{blue} \textbf{\text{Answer.}}$ $\boxed{n=10}$. $\color{blue} \textbf{\text{Construction.}}$ For example, place knights as shown, i.e. on the every coloured square place one. Since we choose 6 of them, then we must have two of them in the same colour, i.e. they are attacking each other. [asy][asy]size(5cm); path S = box( (-3,0), (5,8) );fill(S, white); fill(shift(0,0)*unitsquare, blue); fill(shift(1,2)*unitsquare, blue); fill(shift(3,4)*unitsquare, grey); fill(shift(4,6)*unitsquare, grey); fill(shift(-3,0)*unitsquare, red); fill(shift(-2,2)*unitsquare, red); fill(shift(-3,5)*unitsquare, green); fill(shift(-2,7)*unitsquare, green); fill(shift(4,0)*unitsquare, orange); fill(shift(3,2)*unitsquare, orange); for (int i=-3; i<=4; ++i) { draw(shift(i,7)*unitsquare); } for (int i=-3; i<=4; ++i) { draw(shift(i,6)*unitsquare); } for (int i=-3; i<=4; ++i) { draw(shift(i,5)*unitsquare); } for (int i=-3; i<=4; ++i) { draw(shift(i,4)*unitsquare); } for (int i=-3; i<=4; ++i) { draw(shift(i,3)*unitsquare); } for (int i=-3; i<=4; ++i) { draw(shift(i,2)*unitsquare); } for (int i=-3; i<=4; ++i) { draw(shift(i,1)*unitsquare); } for (int i=-3; i<=4; ++i) { draw(shift(i,0)*unitsquare); } draw(S, black+1.4); [/asy][/asy] $\color{blue} \textbf{\text{Proof.}}$ We can put $10$ knights on the board (look construction), thus assume that we can put more than than $10$. Call the new one $\mathcal{S}$. Notice that we must put $\mathcal{S}$ close to attacking range of a knight, since otherwise choosing $\mathcal{S}$ and one in every colour, we obtain no two attack each other, contradiction. Therefore, we must have $\mathcal{S}$ attacking one of the coloured squares. Assume $\mathcal{S}$ attacks both squares in one colour, but that is clear contradiction, by colouring board chessboard-like pattern. Hence, in every colour there is square, which is not attacked by $\mathcal{S}$. Now choosing $\mathcal{S}$ and one in every colour not attacked by $\mathcal{S}$, we obtain contradiction.