Suppose you want to move from 0 to 100 on the number line. In each step, you…
2014
Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers \(i,j \) with \(i < j\). Given a shortcut \((i,j)\), if you are at position \(i\) on the number line, you may directly move to \(j\). Suppose \(T(k)\) denotes the smallest number of steps needed to move from \(k\) to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular, from 9 there is a shortcut to 15. Let \(y\) and \(z\) be such that \(T(9) = 1 + \min(T(y),T(z))\). Then the value of the product \(yz\) is _____.
Attempted by 35 students.
Show answer & explanation
Correct answer: 150
Key idea: From position 9 you can either move right by 1 to reach 10, or take the given shortcut to reach 15. Since there is at most one shortcut involving any number and the shortcut from 9 goes to 15, the recurrence becomes T(9) = 1 + min(T(10), T(15)).
If you move right, you go to 10, so one branch uses T(10).
If you take the shortcut, you go to 15, so the other branch uses T(15).
Thus the two values compared in the min are T(10) and T(15), so y = 10 and z = 15. Their product is 150.