2
$\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$?

$\endgroup$
1
$\begingroup$

I'll provide a formula for finding the minimal number of nudges needed to transform one number into another .

Let $\overline{ab}$ and $\overline{cd}$ two numbers . If we want to nudge $\overline{cd}$ and get to $\overline{ab}$ we can simply reverse the operations needed to go from $\overline{ab}$ to $\overline{cd}$.

We should transform $a$ to $c$ . Assume for example that $a<c$ .To get to $c$ (in a minimal number of nudges) we could either go through $a,a+1,a+2,\ldots,c$ or in the reverse way : $a,a-1,\ldots ,0,9,8,\ldots ,c$ . For the first way there are $c-a$ nudges and for the second there are $10-(c-a)$ .

This means to use a minimal number of nudges we will choose $\min(c-a,10-(c-a))$.

Now use the same argument for transforming $b$ to $d$ .

Putting everything together :

The minimal number of nudges to go from $\overline{ab}$ to $\overline{cd}$ is :

$$\min(\mid c-a \mid,10-\mid c-a \mid )+\min(\mid d-b \mid,10-\mid d-b \mid )$$

$\endgroup$

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.