-5
$\begingroup$

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

|improve this question
$\endgroup$
6
$\begingroup$

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)$.

|improve this answer
$\endgroup$
  • $\begingroup$ As final answer..can you give no ways for 5, 10, 20 in your answer box $\endgroup$ – Uvc Jul 6 at 11:15
  • $\begingroup$ 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 :) $\endgroup$ – athin Jul 6 at 11:24
3
$\begingroup$

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

|improve this answer
$\endgroup$
  • $\begingroup$ Got the right numbers..can be generalized in one statement $\endgroup$ – Uvc Jul 6 at 11:23
3
$\begingroup$

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;

generating function for the Fibonacci numbers.

We therefore want:

$F(10)=89$.

|improve this answer
$\endgroup$
-1
$\begingroup$

Simplest answer is

To get the number of ways to pick ten rounds is eleventh number of STD Fib sequence..for 20, it is 21st. Even if the seeds of Fib are different..say 3 and 5, no of ways of picking 8, 13, 21 ..so on can be calculated in similar fashion.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ How does this add to the answers already given? $\endgroup$ – greenturtle3141 Jul 7 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.