A Not-So-Simple Graph (Part II)

Probability Level 5

If you have not checked out Part I of the problem, click here . Part I is less challenging, and my solution to that problem might give you inspiration for solving Part II.

Consider a graph with vertices $t_{1},t_{2},t_{3},...,t_{k}$ , where $k \in \mathbb{Z}^{+},k≥2$ . For every integer pair $(m,n)$ where $k≥m>n≥1$ , there are $(m-n)$ distinct edges connecting $t_{m}$ to $t_{n}$ . No edges intersect. An ant moves along the edges of the graph. Given that it can only move from $t_{a}$ to $t_{b}$ if $a>b$ , the number of distinct ways it can move from $t_{k}$ to $t_{1}$ can be expressed as $A(B)^{k}-C(D)^{k}$ , where $A,B,C,D$ are positive numbers. Find $10AC+B+D$ .

The answer is 5.

2 solutions

Sam Zhou
May 31, 2019

Let $x_{k}$ denote the number of ways the ant can move from $t_{k}$ to $t_{1}$ . By inspection, $x_{2}=1$ and $x_{3}=3$ .

We can define $x_{k}$ recursively, and can deduce that $x_{k}=\sum_{i=1}^{k-1} (k-i)x_{i}=x_{k-1}+\sum_{i=1}^{k-2} (k-i)x_{i}=x_{k-1}+\sum_{i=1}^{k-2} (k-1-i)x_{i}+\sum_{i=1}^{k-2} x_{i}=2x_{k-1}+\sum_{i=1}^{k-2} x_{i}$ .

Notice that $\sum_{i=1}^{k-2} x_{i}=x_{k-1}-x_{k-2}$ . Therefore, $x_{k}=3x_{k-1}-x_{k-2}$ . We can now solve this recurrence relation.

The auxiliary equation $\lambda^{2}-3\lambda+1=0$ and has roots $\frac{1}{2} (3+\sqrt{5})$ and $\frac{1}{2} (3-\sqrt{5})$ . These two values are $B$ and $D$ respectively.

Plug the two values and the initial conditions ( $x_{2}=1$ and $x_{3}=3$ ) into the equation $x_{k}=A(B)^{k}-C(D)^{k}$ to get $A=\frac{1}{10} (3\sqrt{5}-5)$ and $C=\frac{1}{10} (3\sqrt{5}+5)$ .

As $10AC=2$ and $B+D=3$ , the answer is $\boxed{5}$ .

Nice solution! It is also interesting to note that the terms of $x_k$ are every other number in the Fibonacci sequence!

David Vreken - 2 years ago

Great solution Sam! I agree with David Vreken who mentioned above that the xk's are numbers in the Fibonacci sequence. I noticed this and used the general formula for Fibonacci sequence terms to find the solution to this problem. By the way, this is a great problem that you should consider sending to MAA so it may be incorporated into the AIME exam!

Bochuan Zhang - 2 years ago

Thanks! I only realized this interesting pattern after I figured out the solution to this problem :)

Sam Zhou - 2 years ago

K T
Jun 3, 2019

Suppose the number of ways to traverse a distance $k=m-n$ is f(k).

Since we can do the first step of size j to any lower in vertex in j ways, we have the recursion relationship: $f(k) = \sum_{j=1}^k{j f(k-j)}$ , with $f(0)=1$ , or

$f(k) =1×f(k-1)+2×f(k-2)+... +k×f(0)$ . This way we find $f(1)=1, f(2)=1, f(3)=3, f(4)=8, f(5)=21,f(5)=55, ...$ . These are the even indexed Fibonacci numbers $F_n$ where $n=2k-2$ . Using Binets formula: $f(k) = F_{2k-2} =\frac{φ^{2k-2}-ψ^{2k-2}}{\sqrt{5}}=\frac{(φ^2)^{k} }{φ^2 \sqrt{5}} - \frac{(ψ^2)^{k}}{ ψ^2\sqrt{5}}$

So $A= \frac{1}{φ^2 \sqrt{5}} = 0.170820...$ $B= φ^2 = 2.618033...$ $C= \frac{1}{ψ^2 \sqrt{5}} =1.170820...$ $D= ψ^2=0.381966...$

And $10AC+B+D=2+3 =\boxed{5}$

A Not-So-Simple Graph (Part II)

The answer is 5.

2 solutions

0 pending reports