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).
[This is very similar to the "sphere-packing bound" with respect to Hamming distance in coding theory, if you want to follow up on some of those terms.]
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.