5
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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}$$

$\endgroup$
  • 2
    $\begingroup$ This shows a nice connection to error correcting codes. Well done. $\endgroup$ – Ross Millikan Aug 22 '14 at 0:57
  • $\begingroup$ @RossMillikan yes indeed, it's an example of a "perfect" code - or something like that - I have forgotten the terminology. $\endgroup$ – David Aug 22 '14 at 1:01
  • $\begingroup$ I was just thinking that you use the fact that you can "correct" each square by $1$ to a "code square" because the " code squares" have a distance of $3$ in the Manhattan metric. This proves the maximum of $20$ $\endgroup$ – Ross Millikan Aug 22 '14 at 2:49
3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thank you, I believe that is the maximum. Perhaps a proof by contradiction is necessary to prove that 21 elements or more is impossible. $\endgroup$ – asdf Aug 22 '14 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.