walking along the number line

117 Views Asked by At

Suppose you start walking along the number line from $0$ to $100$, moving $1$ position to the right in each step. There are some shortcuts $(i,j)$ where $i,j\in[0,100]$ and $i<j$. If you step on $i$ in during your walk you can move to $j$ within $1$ step. $T(k)$ represents the number of minimum ways in which you can move from $k$ to $100$. There is a given shortcut $(9,15)$. There exists two numbers $y$ and $z$ such that $T(9)=1+min(T(y),T(z))$. what is the value of $y.z$ ?

3

There are 3 best solutions below

0
On

From 9 either he can go to 10 or 15 in on step, hence y.z=10.15

2
On

There is not enough information to answer the question.

Dibyendu's description of $T(k)$ is fuzzy, but let's assume $T(k)$ is the minimum number of steps needed to get from $k$ to 100.

If $(9,15)$ is the only shortcut, it is certainly true that $T(9)=1+\min(T(10),T(15))$. But that doesn't mean the answer to the question is 150. It is also true in this case with only one shortcut, $(9,15)$, that $T(9)=1+\min(T(11),T(15))$. In other words, given just the fact that $T(9)=1+\min(T(y),T(z))$, it's impossible to determine the value of $y\cdot z$, because there can be more than one solution to $T(9)=1+\min(T(y),T(z))$, and the value of $y\cdot z$ isn't the same for every solution.

0
On

Alternatively, let's assume $T(k)$ means the number of minimal paths from $k$ to $100$.

Suppose $y = 50$, $z=60$ and there are shortcuts $(20,50)$ and $(30,60)$ and no other shortcuts besides $(9,15)$. There is one minimal path from $9$ to $20$, two minimal paths from $20$ to $60$, one minimal path from $50$ to $100$ and one minimal path from $60$ to $100$.

Therefore $T(9)=2$, $T(50)=T(60)=1$ and $T(9)=1+\min(T(y),T(z))$ as required.

But obviously my choices for $y$ and $z$ were pretty much arbitrary, so that doesn't seem like an interesting problem either.