What is the maximum possible number of elements of $S$?

Question

This is an interesting problem I found.

Let there be a 2-digit sequence that can start with 0, like 04 or 93. Let a "nudge" be defined as exactly one of the following operations:

1) Increasing one of the digits by 1.

2) Decreasing one of the digits by 1.

3) Changing a 0 to a 9.

4) Changing a 9 to a 0.

For example, possible nudges of 19 are 09, 29, 18, and 10.

Say that $S$ is some set of 2-digit sequences so that it takes 3 or more nudges to transform any element of $S$ into some other element of $S$. What is the maximum possible number of elements of $S$?

I thought of a nudge as a knight moves on a chessboard, but with a 10x10 board numbered starting with 1 on the top left and 100 in the bottom right. Clearly the maximum is $100-1=99$ nudges, but that is without considering the extra condition in the problem statement. Any idea how to continue?

Answer 1

Thinking of a $10\times10$ chessboard is good - don't forget that you have to imagine the top and bottom sides as being adjacent, as also the left and right sides. For any given pair $p=(x,y)$ in $S$, define the neighbourhood of $p$ to be the set of all pairs which can be reached in at most one nudge from $p$. That is, the neighbourhood is $$\{\,(x,y),\,(x+1,y),\,(x-1,y),\,(x,y+1),\,(x,y-1)\}\ ,$$ where we interpret $0-1$ as $9$ and $9+1$ as $0$. It is not hard to see that

it takes $3$ or more nudges to transform $p$ to $q$ if and only if the neighbourhoods of $p$ and $q$ do not overlap.

Considering that each neighbourhood has size $5$, we see that no more than $20$ neighbourhoods can fit into the $100$ available squares without overlapping. However this does not guarantee that $20$ are actually possible: we have to consider their "shape" as well as their "size". But it is not too hard to find a solution by trial and error: the different colours indicate the neighbourhoods, and the "centres" of the neighbourhoods are the elements of $S$. $$\def\b{\!\color{blue}{\blacksquare}\!} \def\r{\!\color{red}{\blacksquare}\!} \def\y{\!\color{yellow}{\blacksquare}\!} \def\g{\!\color{green}{\blacksquare}\!} \begin{matrix} \b&\r&\g&\g&\g&\r&\b&\y&\y&\y\\ \r&\r&\r&\g&\y&\b&\b&\b&\y&\g\\ \g&\r&\b&\y&\y&\y&\b&\r&\g&\g\\ \y&\b&\b&\b&\y&\g&\r&\r&\r&\g\\ \y&\y&\b&\r&\g&\g&\g&\r&\b&\y\\ \y&\g&\r&\r&\r&\g&\y&\b&\b&\b\\ \g&\g&\g&\r&\b&\y&\y&\y&\b&\r\\ \r&\g&\y&\b&\b&\b&\y&\g&\r&\r\\ \b&\y&\y&\y&\b&\r&\g&\g&\g&\r\\ \b&\b&\y&\g&\r&\r&\r&\g&\y&\b\\ \end{matrix}$$

Answer 2

Your thought of a chessboard is a good one. Each element you put in$S$ rules out $12$ others. It seems knight moves cause a lot of overlap of the excluded squares. My first thought would be $00,12,24,36,48,50,62,74,86,98,05,17,29,31,43,55,67,79,81,93$ for $20$