edited by
9,969 views
52 votes
52 votes

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 _____.

edited by

4 Answers

Best answer
66 votes
66 votes
$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$.
edited by
39 votes
39 votes
$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$
edited by
6 votes
6 votes

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$

0 votes
0 votes

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

Here, T(9) is nothing but min steps required to move from $9\rightarrow 100$.

For T(9) we have only 2 choices, i.e either we can take a shortcut to 15 or we can just move by 1 unit to right that is to10.

Let’s assume we didn’t took shortcut and we are simply moving 1 unit by right(i.e we reached to 10) and then, started moving right by 1 unit till 100, Bcz we only know shortcut for 9, for the rest of the numbers we don't know.

i.e $9\rightarrow 10\rightarrow 100$,

(100- 10= 90 +1= 91) steps are required, +1 bcz $9\rightarrow 10 $, 1 step is required. 

okay, Now lets assume we took a shortcut from $9\rightarrow 15\rightarrow 100$,

Now min no.of steps required is (100-15 = 85 +1 =86 steps )  , +1 is for $9\rightarrow 15$.  here also same as for the above reasoing i.e we dont know shortcut for 15 so we are moving right by simply 1 unit till 100. therefore it took 85 steps min.

By, the above complete reasoning we got to know that $min(T(y), T(z)),$ should be either 85 or 90(since, +1 is already given),

As we see,

T(10) is  giving exactly 90 min steps(100-10=90), since we don't know the shortcut for 10, we move by 1 unit to right till 100,

and T(15) is giving exactly 85 min steps(100-15=85), since we don't know the shortcut for 15, we move by 1 unit to right till 100,

$T(9)= 1 +min(T(y),T(z)),$ = 1+ min(T(10), T(15)) = 1 +min (90,85) =1 + 85 = 86.

so,By Observing the above senario, y=10. z=15. 

$\therefore$ Ans is 10*15 =150.

 

Answer:

Related questions

44 votes
44 votes
7 answers
1
35 votes
35 votes
5 answers
4
go_editor asked Sep 28, 2014
8,745 views
Let $S$ be a sample space and two mutually exclusive events $A$ and $B$ be such that $A \cup B = S$. If $P(.)$ denotes the probability of the event, the maximum value of ...