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

Given a $2$-digit sequence (which can start with $0$), let us define a nudge as the operation of either increasing or decreasing one of the digits by $1$, or changing a $0$ to a $9$ or a $9$ to a $0$. For example, we can nudge $19$ to get $09$, $29$, $18$, or $10$.

Suppose $S$ is a set of $2$-digit sequences such that it takes at least $3$ nudges to transform any element of $S$ into another element of $S$. What is the maximum possible number of elements of $S$?

I know I have to use either One-to-one Correspondences or Pigeonholes to solve this problem, but I really have no idea.

For an element $s\in S$, let $N(s)$ be the "neighborhood" of $s$, defined as $s$ together with the four two-digit sequences that are one nudge away from $s$ (so $\#N(s)=5$). If $s\ne t$ are both in $S$, then $N(s)$ and $N(t)$ are disjoint: if $x$ were in their intersection, then you could nudge $s$ to $x$ and then $x$ to $t$, contradicting the property given for $S$. Therefore there are at most $20$ elements of $S$, since the union of all the $N(s)$ has at most $100$ elements (the total number of two-digit sequences).
In this case, it's possible to find an example of such an $S$ with $20$ elements, so that really is the maximum and not just an upper bound, namely $$S = \{ab\colon 0\le a,b\le 9, \, a\equiv2b\pmod5\}.$$ pictured below.
• No, the 1-neighborhoods are disjoint if and only if the elements are all at least 3 nudges apart. (Play around with the picture, where nudges are just moving vertically/horizontally by one square on the $10\times10$ torus.) The 2-neighborhoods being disjoint is equivalent to all elements at least 5 nudges apart. – Greg Martin Aug 24 '16 at 0:22