0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

A 20-element set S

$\endgroup$
  • $\begingroup$ Thanks for answering, Greg Martin! :) $\endgroup$ – user359548 Aug 23 '16 at 20:58
  • $\begingroup$ 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. $\endgroup$ – Greg Martin Aug 24 '16 at 0:22
  • 1
    $\begingroup$ @Greg: Argh. Yes, you’re right, of course. $\endgroup$ – Brian M. Scott Aug 24 '16 at 14:23

Your Answer

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