Now, I have solved!! Answer: $n\equiv 1\pmod 3$. First we show that if $n\equiv 1\pmod3$ and the board is marked such that there are no three consective cells going through diagonal for which at least two of them are marked, there exists a knight tour from $L$ to $R$ without going through the marked cell. Let the $P_n$ be the proposition and $T_n$ be such knight-tour. $P_1$ is obviously true. For $P_4$, if one of $*$ in the following board is not marked, we can go from $L$ to $R$ going through that cell. If both of them are marked it is not satisfy the assumption of $P_4$. Thus, $P_4$ is true. \begin{tabular}{|c|c|c|c|} \hline &&&R\\\hline &*&&\\\hline &&*&\\\hline L&&&\\\hline \end{tabular} We assume $P_{n},P_{n+3}$ is true for $n\geq 1$ and we show $P_{n+6}$. (The following board is for $n=7$. We can easy to extend for any $n\equiv 1\pmod 3$) In the following board, if any of $C,D$ are not marked we can go from $L$ to $R$ by $T_4$ and $T_{n+3}$. Thus, we may assume $C,D$ are marked. Also, if both of $A,8$ is not marked, we can go by the path $L\to A\to (T_{n+3})\to 8\to R$. Thus, we may assume one of $A,8$ is marked. Similarly, we may assume one of $1,B$ is marked. Since we cannot mark both $A,1$ not $B,8$, we can assume $A,B$ is marked. Then, we can go by the path $L\to 1\to 2\to (T_n) \to 3\to 4\to 5\to 6\to 7 \to 8\to R$. Since all numbered cells are at most 2 hops diagonally from marked cells $A,B,C,D$, they are guaranteed to be unmarked. Therefore, $T_{n+6}$ is true. \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline & & & & & & & & & & & & R\tabularnewline \hline & & & & & & & & & & 8 & 5 & \tabularnewline \hline & & & & & & & & 7 & & & B & \tabularnewline \hline & & & & & & & & & D & 6 & & 4\tabularnewline \hline & & & & & & & & & & 3 & & \tabularnewline \hline & & & & & & & & & & & & \tabularnewline \hline & & & & & $\ $ & $\ $ &$\ $ &$\ $ & & & & \tabularnewline \hline & & & & & & & & & & & & \tabularnewline \hline & & & & & & & & & & & & \tabularnewline \hline & & & C & & & & & & & & & \tabularnewline \hline & A & & & 2 & & & & & & & & \tabularnewline \hline & & 1 & & & & & & & & & & \tabularnewline \hline L & & & & & & & & & & & & \tabularnewline \hline \end{tabular} Next, we show that $n\not\equiv 1\pmod 3$ is invalid. The following is the case that $n=5,6,8,9$. $O$ is marked cell. Since we cannot go from $A$ to $B$ without passing $O$ and $L$ and $R$ is different letter($A$ and $B$), we cannot go from $L$ to $R$ without passing marked cell. We can naturally extend from $n$ to $n+6$ since the # of $O$-s row is added by 2 and then letters of $L$ and $R$ are remaining different. \begin{tabular}{|c|c|c|c|c|} \hline B & A & B & A & B\tabularnewline \hline B & A & B & A & B\tabularnewline \hline O & O & O & O & O\tabularnewline \hline A & B & A & B & A\tabularnewline \hline A & B & A & B & A\tabularnewline \hline \end{tabular}\begin{tabular}{|c|c|c|c|c|c|} \hline A & B & A & B & A & B\tabularnewline \hline O & O & O & O & O & O\tabularnewline \hline B & A & B & A & B & A\tabularnewline \hline B & A & B & A & B & A\tabularnewline \hline O & O & O & O & O & O\tabularnewline \hline A & B & A & B & A & B\tabularnewline \hline \end{tabular}\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline A & B & A & B & A & B & A & B\tabularnewline \hline A & B & A & B & A & B & A & B\tabularnewline \hline O & O & O & O & O & O & O & O\tabularnewline \hline B & A & B & A & B & A & B & A\tabularnewline \hline B & A & B & A & B & A & B & A\tabularnewline \hline O & O & O & O & O & O & O & O\tabularnewline \hline A & B & A & B & A & B & A & B\tabularnewline \hline A & B & A & B & A & B & A & B\tabularnewline \hline \end{tabular}\begin{tabular}{|c|c|c|c|c|c|c|c|c|} \hline B & A & B & A & B & A & B & A & B\tabularnewline \hline O & O & O & O & O & O & O & O & O\tabularnewline \hline A & B & A & B & A & B & A & B & A\tabularnewline \hline A & B & A & B & A & B & A & B & A\tabularnewline \hline O & O & O & O & O & O & O & O & O\tabularnewline \hline B & A & B & A & B & A & B & A & B\tabularnewline \hline B & A & B & A & B & A & B & A & B\tabularnewline \hline O & O & O & O & O & O & O & O & O\tabularnewline \hline A & B & A & B & A & B & A & B & A\tabularnewline \hline \end{tabular}

Wow nice.....

toshihiro shimizu wrote: On the $n\times n$ checker board, several cells were marked in such a way that lower lefft ($L$) and upper right($R$) cells are not marked and that for any knight-tour from $L$ to $R$, there is at least one marked cell. For which $n>3$, is it possible that there always exists three consective cells going through diagonal for which at least two of them are marked? Solution. The answer is $\boxed{n\in 3\mathbb N+1}.$ First we prove that all $n$ of the form $3k+1$ work. Call a colouring of the checkerboard bad if there are no three consecutive squares among a diagonal with more than $1$ black square. Call a knight tour white if there is no black squares in that knight tour. Claim 1. Let $n=3k+1.$ In an bad colouring of an $n\times n$ checkerboard, there exists a white knight tour. Proof. We proceed by strong induction on $k.$ The base case is trivial that is for $n=4$, it is true. Now, consider a checkerboard of dimension $n=3k+1$ where $m>1.$ Assign coordinates to each cell of the checkerboard with $L=(1,1)$ and $R=(n,n).$ Consider the set of cells $A=\{(a,a)\mid a=3i+1,~1\le i\le k-1\},$ There can be two cases, either $A$ contains a white cell or not. Case (i). $A$ contains a white cell. Let the white cell be $(3j+1,3j+1).$ Now, consider the checkerboards determined by the set of corners $C_1=\{L=(1,1),(1,3j+1),(3j+1,1),(3j+1,3j+1)\}$ and $C_2=\{(3j+1,3j+1),(3j+1,n),(n,3j+1),(n,n)=R\}.$ By our induction hypothesis, since $(3j+1,3j+1)$ is white, we can move our knight from $L$ to $(3j+1,3j+1)$ considering $C_1$, and then considering $C_2$ we can move our knight from $(3j+1,3j+1)$ to $R$, completing a white knight tour. Case (ii). All the cells of $A$ are black. Note that the checkerboard is symmetric along the diagonal at this moment, also both of $(2,3)$ and $(3,2)$ can't be black. Without loss of generality assume that $(3,2)$ is white. We now divide the proof into two subcases that is whether the cell $(3k,3k-1)$ is black or white. subcase (a). The cell $(3k,3k-1)$ is white. In our first move, we move our knight from $L$ to $(3,2).$ Consider the square determined by the set of corners $C=\{(3,2),(3k,2),(3k,3k-1),(3,3k-1)\},$ we have $(3k,3k-1)$ is white, so using induction hypothesis, we can move our knight from $(3,2)$ to $(3k,3k-1)$ and then we can directly move it to $R$ from $(3k,3k-1)$ in exactly one move. subcase (b). The cell $(3k,3k-1)$ is black. Again, in our first move we move our knight to $(3,2)$. Observe that $(5,3)$ is white since $(4,4)$ is black. So we move the knight to $(5,3),$ now, consider the $4\times 4$ checkerboard determined by the set of corners $S_1=\{(5,3),(8,3),(5,6),(8,6)\},$ note that $(8,6)$ is white as $(7,7)\in A$ is black, so using the induction basis, we can move our knight to $(8,6).$ Again consider the $4\times 4$ checkerboard determined by the set of corners $S_2=\{(8,6),(11,6),(8,9),(11,9)\},$ similarly, we can now move our knight to $(11,9),$ continuing in this way at some point our knight will reach $(3k-1,3k-3).$ Now, consider the $4\times 4$ checkerboard determined by the set of corners $T=\{(3k-1,3k-3),(3k-1,3k),(3k-4,3k-3),(3k-4,3k-1)\},$ observe that as $(3k-2,3k-2)\in A$ is black so $(3k-4,3k-3)$ is white, hence using induction basis we can move our knight to the cell $(3k-4,3k-3).$ Also note that by the initial assumption $(3k,3k-1)$ is black so $(3k-2,3k+1)$ is white, also since $(3k-2,3k-2)\in A$ therefore $(3k-3,3k-1)$ is white and as $(3k,3k-1)$ is black hence $(3k-1,3k)$ is white, so now we can execute the following sequence of moves, \[(3k-4,3k-3)\longrightarrow(3k-2,3k+1)\longrightarrow(3k-3,3k-1)\longrightarrow(3k-1,3k)\longrightarrow R\]And our induction is complete. $\square$ Observe that Claim 1 is enough to conclude that all $n=3k+1,~k\ge 1$ works. We now prove that other $n$ doesn't work. There can be two possibilities $n=3k$ or $3k+2,$ for now let $n=3k,$ in this case we colour the whole $(3h+2)^{\text{th}}$ row black for all $h=0,1,2,\ldots,k-1.$ Note that the second row from the top is coloured. Consider the following colouring example of a $9\times 9$ board where $O$ denotes black squares and $*$ denote the cells where the knight can go after several moves starting from $L$ without landing on black squares. Obviously, there can't be an $*$ in $R,$ as seen by the example below. It is not hard to see that this type of construction holds for all $n=3k.$ \begin{tabular}{|c|c|c|c|c|c|c|c|c|} \hline & * & & * & & * & & * & R\tabularnewline \hline O & O & O & O & O & O & O & O &O\tabularnewline \hline * & & * & & * & & * & &*\tabularnewline \hline * & & * & & * & & * & &*\tabularnewline \hline O & O & O & O & O & O & O & O &O\tabularnewline \hline & * & & * & & * & & * &\tabularnewline \hline & * & & * & & * & & * &\tabularnewline \hline O & O & O & O & O & O & O & O &O\tabularnewline \hline L & & * & & * & & * & &* \tabularnewline \hline \end{tabular}Now, if $n=3k+2,$ we colour the whole $(3h)^{\text{th}}$ row black for all $h=1,2,\ldots,k.$ Note that the two top rows aren't coloured. Consider the following colouring example of a $8\times 8$ board. Obviously, there can't be an $*$ in $R,$ as seen by the example below. It is not hard to see that this type of construction holds for all $n=3k+2.$ \begin{tabular}{|c|c|c|c|c|c|c|c|} \hline * & & * & & * & & * & R\tabularnewline \hline * & & * & & * & & * & \tabularnewline \hline O & O & O & O & O & O & O & O \tabularnewline \hline & * & & * & & * & & * \tabularnewline \hline & * & & * & & * & & *\tabularnewline \hline O & O & O & O & O & O & O & O \tabularnewline \hline *& & * & & * & & * & \tabularnewline \hline L & &* & & * & & *& \tabularnewline \hline \end{tabular}And we are done. $\blacksquare$

Toshiro Shimizu wrote: Quote: For $P_4$, if one of $*$ in the following board is not marked, we can go from $L$ to $R$ going through that cell. If both of them are marked it is not satisfy the assumption of $P_4$. Thus, $P_4$ is true. \begin{tabular}{|c|c|c|c|} \hline &&&R\\\hline &*&&\\\hline &&*&\\\hline L&&&\\\hline \end{tabular} Can someone explain how a knight tour through the $*$ which is unmarked allows us to go through $L$ to $R$ from that cell? I am asking this because if this occurs, isn't it still possible for there to be at least one marked box in each knight tour?

yeah. I don't understand toshiro's solution as well.

Can this be generalized to $m \times n$? I think the answer to the generalized version is $m \equiv n\equiv 1(mod 3)$, and it suffices to prove the case $m=4$ (Induction).

I understand my first question now, but can someone explain how the proposition $P_n$ proves the problems statement.

Can someone explain the problem condition? "three consective cells going through diagonal"

Plops wrote: I understand my first question now, but can someone explain how the proposition $P_n$ proves the problems statement. Sorry, I didn't see your post until now. First half of my proof is showing that if $n\equiv 1\pmod 3$ and "there are no three consective cells going through diagonal for which at least two of them are marked"(name this condition $(\heartsuit)$), we must have a knight tour from $L$ to $R$(contraposition). My proof is based on induction. I will explain how to show $P_{13}$ assuming $P_7$ and $P_10$. See the figure below. If $C$ is not marked, consider sub-grid $10\times 10$ which lower-left is $C$ and upper-right is $R$(ignore others). From $P_{10}$, there is a tour from $C$ to $R$. Also we can go from $L$ to $C$ from condition $(\heartsuit)$(one of $A$, $1$ are not marked). Similarly, if $D$ is not marked, we can find tour from $L$ to $R$. Thus, we may assume $C$ and $D$ are marked. In this case, one of $A$, $1$ and one of $8$, $B$ are not marked from condition $(\heartsuit)$. If such unmarked cell-pair is $A$, $8$, we may find a tour from $A$ to $8$ by $P_{10}$ and we can find a tour from $L$ to $R$. If cells $1$, $B$ are not marked, we can similarly find a tour from $L$ to $R$. So...may assume $A,B,C,D$ are marked. Then, note that numbered cell from $1$ to $8$ are not marked from condition $(\heartsuit)$. Then, we can find a tour from $L\to 1\to 2\to \cdots \to 8\to R$. \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline & & & & & & & & & & & & R\tabularnewline \hline & & & & & & & & & & 8 & 5 & \tabularnewline \hline & & & & & & & & 7 & & & B & \tabularnewline \hline & & & & & & & & & D & 6 & & 4\tabularnewline \hline & & & & & & & & & & 3 & & \tabularnewline \hline & & & & & & & & & & & & \tabularnewline \hline & & & & & $\ $ & $\ $ &$\ $ &$\ $ & & & & \tabularnewline \hline & & & & & & & & & & & & \tabularnewline \hline & & & & & & & & & & & & \tabularnewline \hline & & & C & & & & & & & & & \tabularnewline \hline & A & & & 2 & & & & & & & & \tabularnewline \hline & & 1 & & & & & & & & & & \tabularnewline \hline L & & & & & & & & & & & & \tabularnewline \hline \end{tabular}

neyft wrote: Can someone explain the problem condition? "three consective cells going through diagonal" It means three cell triplet like marked $*$ or $o$ in the figure below. \begin{tabular}{|c|c|c|c|c|c|c|c|} \hline & & & & & & & \tabularnewline \hline *& & & & & & & \tabularnewline \hline &* & & & & & & \tabularnewline \hline & &* & & & &o & \tabularnewline \hline & & & & & o & & \tabularnewline \hline & & & &o & & & \tabularnewline \hline \end{tabular}

Wow really solutions @OP and @ayan.nmath! I would just like to point out a small thing: since the "knight" is a chess piece, it should really be on a "chess board" and not a "checker board" but same difference really.

The answer is all $n\equiv 1\pmod{3}$ We set up coordinate systems representing the cells with $L=(1,1)$ and $R=(n,n)$ We first show the it is always possible when $n\equiv 1\pmod 3$. Let $n=3m+1$. Suppose on the contrary that we can mark some cells of the checker board such that there is at least one marked cell on every knight-tour from $L$ to $R$, and that there are at most $1$ marked cells among $3$ consecutive cells in a diagonal. Consider the sets $$A_1=\{(1,1)\},A_i=\{(3i,3i+2),(3i+1,3i+1),(3i+2,3i)\},2\leq i\leq k-1,A_m=\{(3m+1,3m+1)\}$$$$B_i=\{(2+3i,3+3i),(3+2i,2+3i)\},1\leq i\leq m-1$$We color the cells in $A_i$ using color red and cells in $B_i$ using color blue. For example, if $n=7$ then we color the cells as follows: [asy][asy] size(10cm); real labelscalefactor = 0.5; /* changes label-to-point distance */pen dps = linewidth(0.7) + fontsize(0); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -4.9695720191858195, xmax = 14.439851934694959, ymin = -4.670883164666703, ymax = 10.096479522555567; /* image dimensions */fill((1,3)--(1,2)--(2,2)--(2,3)--cycle, linewidth(2) + blue); fill((2,2)--(2,1)--(3,1)--(3,2)--cycle, linewidth(2) + blue); fill((2,5)--(2,4)--(3,4)--(3,5)--cycle, linewidth(2) + red); fill((3,4)--(3,3)--(4,3)--(4,4)--cycle, linewidth(2) + red); fill((4,3)--(4,2)--(5,2)--(5,3)--cycle, linewidth(2) + red); fill((4,6)--(4,5)--(5,5)--(5,6)--cycle, linewidth(2) + blue); fill((5,5)--(5,4)--(6,4)--(6,5)--cycle, linewidth(2) + blue); /* draw figures */draw((0,7)--(0,0), linewidth(2)); draw((1,0)--(1,7), linewidth(2)); draw((2,7)--(2,0), linewidth(2)); draw((3,0)--(3,7), linewidth(2)); draw((4,7)--(4,0), linewidth(2)); draw((5,0)--(5,7), linewidth(2)); draw((6,0)--(6,7), linewidth(2)); draw((7,7)--(7,0), linewidth(2)); draw((0,7)--(7,7), linewidth(2)); draw((7,6)--(0,6), linewidth(2)); draw((0,5)--(7,5), linewidth(2)); draw((7,4)--(0,4), linewidth(2)); draw((0,3)--(7,3), linewidth(2)); draw((7,2)--(0,2), linewidth(2)); draw((0,1)--(7,1), linewidth(2)); draw((0,0)--(7,0), linewidth(2)); /* dots and labels */clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy][/asy] Notice that from our assumption, in all sets except $A_1$ and $A_m$, at most one cells are marked. Therefore, it is always possible for a knight to travel from $A_i$ to $B_i$ and from $B_i$ to $A_{i+1}$ without passing through the marked cells. in particular, we can always travel from $A_1$ to $A_n$, contradiction. Now we proceed to the case where $n\equiv 0,2\pmod 3$. For $n\equiv 0\pmod 3$ we color the cells with $x$ coordinate congruent to $2$ modulo $3$. For example, when $n=6$, we mark the board as follows: [asy][asy] size(10cm); real labelscalefactor = 0.5; /* changes label-to-point distance */pen dps = linewidth(0.7) + fontsize(0); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -3.0075860057841117, xmax = 14.874423950292881, ymin = -3.9645945192912233, ymax = 10.90570849681492; /* image dimensions */fill((0,2)--(0,1)--(1,1)--(1,2)--cycle, linewidth(2) + red); fill((1,2)--(2,2)--(2,1)--(1,1)--cycle, linewidth(2) + red); fill((2,2)--(3,2)--(3,1)--(2,1)--cycle, linewidth(2) + red); fill((3,2)--(4,2)--(4,1)--(3,1)--cycle, linewidth(2) + red); fill((4,2)--(5,2)--(5,1)--(4,1)--cycle, linewidth(2) + red);fill((5,2)--(6,2)--(6,1)--(5,1)--cycle, linewidth(2) + red); fill((0,5)--(0,4)--(1,4)--(1,5)--cycle, linewidth(2) + red); fill((1,5)--(2,5)--(2,4)--(1,4)--cycle, linewidth(2) + red); fill((2,4)--(3,4)--(3,5)--(2,5)--cycle, linewidth(2) + red); fill((3,5)--(4,5)--(4,4)--(3,4)--cycle, linewidth(2) + red); fill((4,5)--(5,5)--(5,4)--(4,4)--cycle, linewidth(2) + red); fill((5,5)--(6,5)--(6,4)--(5,4)--cycle, linewidth(2) + red); /* draw figures */draw((0,6)--(0,0), linewidth(2)); draw((1,6)--(1,0), linewidth(2)); draw((2,6)--(2,0), linewidth(2)); draw((3,0)--(3,6), linewidth(2)); draw((4,6)--(4,0), linewidth(2)); draw((5,6)--(5,0), linewidth(2)); draw((6,6)--(6,0), linewidth(2)); draw((0,6)--(6,6), linewidth(2)); draw((0,5)--(6,5), linewidth(2)); draw((0,4)--(6,4), linewidth(2)); draw((0,3)--(6,3), linewidth(2)); draw((0,2)--(6,2), linewidth(2)); draw((0,1)--(6,1), linewidth(2)); draw((0,0)--(6,0), linewidth(2)); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy][/asy] Let $n=3m$, then the marked cells divide the board into $m+1$ regions. Let $A_i$ be the $i^{th}$ region from the bottom, then notice that if a knight start from $L$, then in the $i^{th}$ region it can only land on cells with $x-$coordinate same as $i$. In particular, it can never land on $(n-1,n-2)$. Since it lies in the $m^{th}$ region and has x-coordinate $3m-1$. Therefore, any knight tour from $L$ to $R$ must pass through a marked cell, but we can't find such three cells along a diagonal. The case $n\equiv 2\pmod 3$ is similar. We color the cells with $x$-coordinate congruent to $0$ modulo $3$. For example, when $n=5$, we color the cells: [asy][asy] size(10cm); real labelscalefactor = 0.5; /* changes label-to-point distance */pen dps = linewidth(0.7) + fontsize(0); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -2.251479113656612, xmax = 10.046817328700774, ymin = -2.5539468511102306, ymax = 7.673057558850103; /* image dimensions */fill((0,3)--(0,2)--(1,2)--(1,3)--cycle, linewidth(2) + red); fill((1,3)--(2,3)--(2,2)--(1,2)--cycle, linewidth(2) + red); fill((2,2)--(3,2)--(3,3)--(2,3)--cycle, linewidth(2) + red); fill((3,2)--(4,2)--(4,3)--(3,3)--cycle, linewidth(2) + red); fill((4,2)--(5,2)--(5,3)--(4,3)--cycle, linewidth(2) + red); /* draw figures */draw((0,5)--(0,0), linewidth(2)); draw((1,0)--(1,5), linewidth(2)); draw((2,5)--(2,0), linewidth(2)); draw((3,0)--(3,5), linewidth(2)); draw((4,5)--(4,0), linewidth(2)); draw((5,0)--(5,5), linewidth(2)); draw((0,4)--(5,4), linewidth(2)); draw((5,5)--(0,5), linewidth(2)); draw((0,3)--(5,3), linewidth(2)); draw((5,2)--(0,2), linewidth(2)); draw((0,1)--(5,1), linewidth(2)); draw((0,0)--(5,0), linewidth(2)); /* dots and labels */clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy][/asy] Let $n=3m+2$, then the marked cells divide the board into $m+1$ regions. Let $A_i$ be the $i^{th}$ region from the bottom, then notice that if a knight start from $L$< then in the $i^{th}$ region it can only land on cells with $x-$coordinate same as $i$. In particular, it can never land on $(n-2,n-1)$. Since it lies in the $(m+1)^{th}$ region and has x-coordinate $3m$. Therefore, any knight tour from $L$ to $R$ must pass through a marked cell, but we can't find such three cells along a diagonal.