I think the answer is 576

JRD wrote: I think the answer is 576 No, $258$ hint: $a_n+a_{n-1}=3\times2^{n-1}$

can you Explain your Solution

$258$ is the official answer. In 2001, the official gave two solutions the pictures from a Chinese book, really sorry in Chinese

Attachments:

Label the vertices $1, 2, \ldots, 24$. Arrange the vertices as follows: 01 09 17 04 12 20 07 15 23 02 10 18 05 13 21 08 16 24 03 11 19 06 14 22 Suppose that the grid is toroidal (the left side and the right side are connected, and so as the top and the bottom sides). Hence the given conditions can be restated as follows: No two chosen vertices are orthogonally adjacent. (Horizontal adjacency means a distance of 8 and vertical adjacency means a distance of 3.) Now we have reduced the problem to a specific case $n = 8$ of the following problem: Given a $3 \times n$ toroidal grid, determine the number of ways to choose $n$ cells such that no two squares are orthogonally adjacent. We'll solve the generalized problem. Suppose that the number of ways for a given $n$ is $x_n$. Note that the given condition requires us to choose exactly one cell from each row. $x_1 = 0, x_2 = 6$ are immediate. Now we will construct a recursion. Suppose that we ignore the constraint that cells chosen in the top and the bottom rows may not occupy the same column. Then, after choosing $3$ ways for the cell in the first row, we have $2$ ways to choose the cell in the next row (namely the two cells not in the same column as the chosen cell in the current row). So there are $3 \cdot 2^{n-1}$ ways in total. However, we need to subtract this number from the number of ways where the last row's chosen cell occupy the same column as the chosen cell in the first row. In this case, note that we can remove the last row and get a satisfying configuration for $3 \times (n-1)$ grid, so there are $x_{n-1}$ ways where the chosen cells in the first row and the last row occupy the same column. Hence $x_n = 3 \cdot 2^{n-1} - x_{n-1}$ or $x_{n-1} + x_n = 3 \cdot 2^{n-1}$. The recurrence has a solution $x_n = A2^n + B(-1)^n$. With $x_1 = 0, x_2 = 6$, the only satisfying solution is $x_n = 2^n + 2(-1)^n$, so $x_8 = 2^8 + 2(-1)^8 = \boxed{258}$.

The answer is $258$. We will prove this in the following poorly-written proof. We will deal with the general case where $24$ is replaced with $3n$, and we wish to find the number of sets of $n$ distinct vertices such that no two are $3$ or $n$ apart. Label the vertices $1,2,\ldots,3n$ and split them into groups of three: $1,n+1,2n+1$ (group 1), $2,n+2,2n+2$ (group 2), and so on until $n,2n,3n$ (group n). Since there are $n$ groups and $n$ vertices we must select, it follows that we are picking one vertex from each group. This deals with the $n$ apart condition, so now we only have to focus on the $3$ apart condition. We will construct a recursion relation to do this. Let $a_n$ denote the number of ways to select a set of $n$ vertices with the aforementioned properties. First off, we clearly have $a_1=0$ because each vertex is three apart from itself. We also have $a_2=6$ which can be manually computed. Now consider the number of ways to select this set of $n$ vertices: if we pick the first vertex from the first group, the second from the second, and so on, ignoring the condition that $n$ and $n+1$ cannot both be in the set (and the same for $2n$ and $2n+1$, $3n$ and $3n+1$) there are clearly $3\cdot 2^{n-1}$ ways to do this. However, we have to deal with the fact that $n$ and $n+1$ can't be in the set at the same time, as mentioned previously. Our figure of $3\cdot 2^{n-1}$ overcounts all choices of the first $n-1$ vertices selected, except in the case where the same choice of $n-1$ vertices is not valid if we delete the $n$th group (leaving us with $3(n-1)$ vertices). The number of overcounts is therefore the number of legal sets of $n-1$ vertices, so our recursion relation is $a_n=3\cdot 2^{n-1}-a_{n-1}$. If we wanted to, we could just bash out the first $8$ terms and call it a day, but we'll find a closed form instead for the sake of generalization. From $a_{n}=3\cdot 2^{n-1}-a_{n-1}$ we get $a_{n+1}=3\cdot 2^{n}-a_{n}$. Subtracting the first from the second and cleaning things up yields: $$a_{n+1}=3\cdot 2^{n-1}+a_{n-1}$$Now subtracting this equation from the first, we get: $$a_n-a_{n+1}=-2a_{n-1}$$Upon rearranging and shifting this yields: $$a_n=a_{n-1}+2a_{n-2}$$The roots of the characteristic polynomial for this are $2$ and $-1$, so we have $a_n=A\cdot 2^n+B(-1)^n$ for some constants $A,B$. Plugging in $a_1=0$ and $a_2=6$ gives us $A=1$ and $B=2$, so we have: $$a_n=2^n+2(-1)^n$$Thus we have $a_8=2^8+2(-1)^8=256+2=\boxed{258}$. $\blacksquare$