PUERTA | Puerta TI 2005 | Pregunta 56

Sea G un grafo dirigido cuyo conjunto de vértices es el conjunto de números del 1 al 100. Hay una arista desde un vértice i hasta un vértice j si y si j = i + 1 o j = 3i. El número mínimo de aristas en un camino en G desde el vértice 1 hasta el vértice 100 es

 
(A) 4
(B) 7
(C) 23
(D) 99

Respuesta: (B)
Explicación: La tarea es encontrar el número mínimo de aristas en un camino en G desde el vértice 1 al vértice 100 tal que podamos movernos a cualquiera i+1 o 3i desde un vértice i.

Since the task is to minimize number of edges, 
we would prefer to follow 3*i.  

Let us follow multiple of 3.

1 => 3 => 9 => 27 => 81, now we can't follow multiple
of 3. So we will have to follow i+1. This solution gives
a long path.

What if we begin from end, and we reduce by 1 if 
the value is not multiple of 3, else we divide by 3.
100 => 99 => 33 => 11 => 10 => 9 => 3 => 1

So we need total 7 edges.

Cuestionario de esta pregunta