# Go for the Gold

You are given a bag containing 1 and 2 ounce gold rounds.

You need to draw one coin at a time till they Sum up to ten rounds.

How many different ways you can achieve that?

What is the quickest path to calculate?

How about if you are asked to draw till it sums to twenty rounds.

No searches...No calculators..No computers

The number of ways to achieve $$10$$ ounces is:

the number of ways to achieve $$9$$ ounces (as you draw the $$1$$ ounce) + the number of ways to achieve $$8$$ ounces (or as you draw the $$2$$ ounce).

To make it general:

$$F(N) = F(N-1) + F(N-2)$$ with $$F(1) = 1$$ and $$F(2) = 2$$ as the base cases.

So:

We may calculate $$F(10)$$ in bottom-up approach from $$F(3) = 2 + 1 = 3$$, $$F(4) = 3 + 2 = 5$$, and so on. Then we have $$F(10) = 144$$.

Note that:

$$F$$ is actually a Fibonacci function. So you can use its non-recursive formula to determine $$F(N)$$.

• As final answer..can you give no ways for 5, 10, 20 in your answer box – Uvc Jul 6 '19 at 11:15
• Ah ok, I'll do later I guess.. Actually I'm doing it fast on my mobile, and just realized my final answer is incorrect: @JS1 find the final answer :) – athin Jul 6 '19 at 11:24

I used the same approach as athin but I got: 1 2 3 5 8 13 21 34 55 89 giving $$89$$ for the first answer. Essentially it follows a Fibonacci sequence but shifted by one (Fibonacci starts with 1 1 2, this one starts with 1 2 3).

For the second, using a Fibonacci relationship from here, I got:

$$F(20) = F(9)^2 + F(10)^2 = 55^2 + 89^2 =$$

(lengthy no calculator math)

$$(50+5)^2 + (90-1)^2 =$$
$$2500 + 500 + 25 + 8100 - 180 + 1 =$$
$$3000 + 8100 + 25 - 180 + 1 =$$
$$11100 + 26 - 180 = 10920 + 26 =$$
$$10946$$

As for quickest path to calculate, the site I linked to shows how to compute Fibonacci numbers fast using a doubling method like I used to find F(20).

• Got the right numbers..can be generalized in one statement – Uvc Jul 6 '19 at 11:23

The sequence is:

$$1+(x+x^2)+(x+x^2)^2+(x+x^2)^3+\dots$$

and we want the coefficient of $$x^{10}$$.

The sequence equals:

$$\frac{1}{1-x-x^2}$$

which is the;

We therefore want:

$$F(10)=89$$.