GATE2014-3-37

Question

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 \:\text{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 _____.

Answer 1

$T(k)$ is the smallest number of steps needed to move from $k$ to $100$.

Now, it is given that $y$ and $z$ are two numbers such that,

$T(9) = 1 + \min (T(y), T(z))$ , i.e.,

$T(9) = 1 + \min ($Steps from $y$ to $100$, Steps from $z$ to $100)$, where $y$ and $z$ are two possible values that can be reached from $9$.

One number that can be reached from $9$ is $10$, which is the number obtained if we simply move one position right on the number line. Another number is $15$, the shortcut path from $9$, as given in the question. So, we have two paths from $9$, one is $10$ and the other is $15$.

Therefore, the value of $y$ and $z$ is $10$ and $15$ (either variable may take either of the values).

Thus, $yz = 150$.

Comments

nice

---

what a nice approach @Regina phalange

---

""T(9)=1+min(T(9)=1+min(Steps from yy to 100100, Steps from zz to 100)100), where y and z are two possible values that can be reached from 9." Where  it is mentioned???

---

Abhisek Tiwari 4

Read the question carefully.

---

I am unable to find out how it,"where y and z are two possible values that can be reached from 9", is linked. Can you please explain where it is ?

---

T(9)=1+min(T(y),T(z))

@rahulgargnov4  here the 1 in the equation is telling that. Equation says calculate minimum of T(y) and T(z) and then simply add 1 to it. What does that mean? 9 is at a distance of 1 from both y and z.

Analogy : height of the tree is : 1 + height(left) + height (right). Why one is here? because root is at distance one from both right and left. 

Answer 2

$T(9) =$ Distance from $9$ to $100$
$T(9)=1+ \min(T(y),T(z))=1+$min(Distance from $y$ to $100$ , Distance from $z$ to $100$)

There are only two such values where we can reach from $9$ , one is simple step to right on number line , i.e $10$ and another is $15$ (given shortcut)

Hence , $y=10$ , $z=15$
$yz=10 \times 15 = 150$

Comments

http://www.quora.com/Suppose-you-want-to-move-from-0-to-100-on-the-number-line-and-in-each-step-you-either-move-right-by-a-unit-distance-or-you-take-shortcut-and-suppose-T-K-is-the-smallest-number-of-steps-needed-to-move-from-K-to-100-Let-Y-and-Z-be-such-that-T-9-1+min-T-Y-T-Z-What-then-is-the-value-of-the-product-Y*Z

---

Can you please explain this question once again , I am not getting it precisely .

---

I am not getting .. Please explain anyone

---

it is solved like this

T(1)=1+min(T(y),T(z))=1+1=2

T(2)=1+min(T(y),T(z))=1+2=3

T(3)=1+min(T(y),T(z))=1+3=4

.

.

.

T(9)=10

Now, shortcut for T(9)=15

So, yz=10*15=150

but how could it be say , it goes from 0 to 100?

@ Srinath

---

Solution of the equation

T(9)=1+min(T(y),T(z))

Now, 9 to 15 there is a shortcut.

Now, if I take solution like that

T(9)=1+min(T(10),T(15))

    =1+T(15)

that means , T(9) to T(15) there exists 1 step, i.e. why we are adding 1.

Answer 3

From $k$, we have two paths-

1. Path 1- This is the path where we go from $k$ to $k_1$ where $k_1 = k+1$. Here, $k_1$ is the next number to the right of $k$.
2. Path 2- This is the path where we go from $k$ to $k_2$ where $k_2 = k+i$. Here, $k_2$ is the the number to which $k$ has a shortcut.

Therefore, we have the following recurrence relation-

$T(k) = 1 + min(T(k_1), T(k_2))$

This basically means that the smallest no. of steps from $k$ to $100$ includes at least one step (either from $k$ to $k_1$ or from $k$ to $k_2$) and then subsequent smallest no. of steps from either $k_1$ to $100$ or from $k_2$ to $100$, whichever is minimum.

$\therefore T(9) = 1 + min(T(10), T(15))

Here,

$k_1 = 9+1 = 10 \Rightarrow y = 10$, 

$k_2 = 15$ ,($\because$ there is at most a single shortcut involving any number and it is given that the shortcut from $9$ is $15$) $\Rightarrow z = 15$

$\therefore y.z = 10.(15) = 150$