8
$\begingroup$

This problem is easy, I provide it just for fun of the community.

Like many other mad scientists, I believe that time travel is possible. One of such possibilities was described by a Soviet, Ukrainian, and Israeli writer Felix Krivin. I quote his novel “I’ve Stolen the Time Machine”:

Time Machine was stolen again....

This happened at the height of the celebration of a new year $4119$. Thus, taking into accounts technical possibilities of modern machines, the criminal could jump to years: $1149$, $1194$, $1419$, $1491$, $1914$, $1941$, $4191$, $4911$, $9114$, $9141$, and $9411$.

This clearly suggests a pattern of possible jumps in time. It is easy to check that this pattern allows to a time traveler (for instance, to Emmett "Doc" Brown), starting from any year in a range from $0001$ to $9998$, to reach any other year in the range, provided he will live sufficiently long. Indeed, the traveler can live up to $9998$, then jump to $8999$, live up to $9000$, jump to $0009$, live up to $0010$, and jump to the beginning of the new history. From the beginning Doc can live up to the needed year. Since, looking for a shortest path he can avoid entering any year twice, he would achieve the destination year if he would be one of Far Eastern emperors, according to regular wishes of banzai to them. This task may be a challenge even to Methuselah, who, according to Bible, lived $969$ years [Gen. 5:27]. But I’m more interested in possibilities of mere mortals. So, my question is:

How many years to live suffices in order to reach any year in the given range from any other year in the range?

enter image description here

“The Path of Time” by Jean-Paul Avisse

$\endgroup$
  • 2
    $\begingroup$ A fun problem, but it really belongs on the Puzzling StackExchange. $\endgroup$ – Blue Jan 11 at 18:45
  • $\begingroup$ @Blue Maybe. But I have no account at Puzzling.SE and I’m not acquainted well with its contents. The latest thread from there which I read is very far from math related puzzles. For me my problem looks more belonging to recreation math, related with arithmetic and graph theory, than to puzzles, and I encountered in math more puzzle-like problems than mine. For instance, most of Martin Gardner’s books, published in Soviet Union, which I know, were titled as mathematical something. $\endgroup$ – Alex Ravsky Jan 11 at 19:04
2
$\begingroup$

My attempt:-

Claim:- The maximum number of years required to jump from one year to another is $34$ years , and is the time required to reach $9998$ from $0001$.

Proof:- The fastest way to reach $9998$ from $0001$ is to first wait till $0009$ , jump to $9000$ , wait till $9009$ , jump to $9900$ and so on. The number of years is $ 8+9+9+8 = 34 $ . Observe that the maximum number of years to change a digit $n$ to a digit $m$ is $9$ years , i.e when $m+1 = n$ . However , when $n \neq 0$ , the addition of $9$ years , if $n$ is in the unit’s place , carries a $1$ to the ten’s place. Consequently, the number of years needed to change another digit will always be less than $9$ , unless $n = 0$ . In the range , the smallest number with the maximum number of $0$s is $0001$ . From $0001$ , $9998$ takes the longest time to reach.

Special Cases:- For some years , the carry over increases the number of required years .

Example 1:- Jumping from $wxyz$ to $wxy(z-1)$ . Adding $9$ to the first quantity changes $y$ to $y+1$ , increasing the number of required years. Instead , we reach the year $wx(y+1)0$ . From here , we jump to $wx0(y+1)$ , and add years and jump when required. The years required to do so is always less than $34$ . In the special case when $z-1 = 0$ , we reach the year $wx10$ and then add years and jump as required.

Example 2:- When jumping from $wx9z$ to $wx9(z-1)$. Even in this case , it is easy to see that it takes less than 34 years .

There are other special cases , but they can all be proven to take less than 34 years.

$\endgroup$
  • $\begingroup$ What about going from an year to a higher sum to one with a smaller sum? $\endgroup$ – N. S. Jan 11 at 18:51
  • $\begingroup$ @N.S. I assume you mean travelling to the past. For x > y , (x and y both digits of a year) , y - x + 10 <= 9 $\endgroup$ – Sinπ Jan 11 at 19:09
  • $\begingroup$ @N.S. once you hit 9999 it is all over. Note that you cannot get from 9999 to any other year. By the same line of reasoning you cannot ever go back to 0000. You can however do this for any other year. For example: 9998 -> 8999 -> 9000 -> 0009 -> 0010 -> 0001. $\endgroup$ – Mike Jan 11 at 23:50

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.