Member Avatar for Gotcha

Does anyone knows how to solve this?

Thanks for suggestions.


Find a recurrent relation, its initial conditions and explain how is obtained this relation.

A Driver pays in a station of toll using only five cents coins or ten cents coins, throwing one currency a the time. Find the number of different forms that it can pay in the toll plaza. (the order in which the currencies are thrown is important and consider that the payment of the toll is a multiple of 5 cents.

thanxs,

  • 3 Contributors
  • 2 Replies
  • 119 Views
  • 1 Week Discussion Span
  • Latest Post Latest Post by MartyMcFly

Dani AI

Generated

Let a_n be the number of ordered ways to pay exactly 5n cents using only 5c and 10c coins. For n >= 2 the recurrence is

an = a{n-1} + a_{n-2}

with initial conditions a_0 = 1 (one way to make 0: the empty sequence) and a_1 = 1 (one 5c). This formalizes the split-by-first-coin idea mentioned by : any valid sequence either starts with a 5c (then the remainder is 5(n-1)) or starts with a 10c (remainder 5(n-2)).

There is also a closed, combinatorial form. If k denotes how many 10c coins are used, the number of sequences with exactly k tens is the number of ways to place those k tens among the total n-k coins, i.e. C(n-k, k). Hence

an = sum{k=0}^{floor(n/2)} C(n-k, k),

and this sequence matches the Fibonacci numbers: an = F{n+1} (with F_0 = 0, F_1 = 1). Equivalently, Binet's formula gives a_n = (phi^(n+1) - psi^(n+1)) / sqrt(5), where phi=(1+sqrt(5))/2 and psi=(1-sqrt(5))/2.

A tiny Python routine to compute this by recurrence:

def ways(cents):
    if cents % 5: return 0
    n = cents // 5
    a = [1, 1]
    for i in range(2, n+1):
        a.append(a[i-1] + a[i-2])
    return a[n]

print(ways(25))  # prints 8

Notes: amounts not divisible by 5 give 0. For practical problems count a_0 = 1 only when treating "no coin" as a single valid way to reach zero. This recurrence is the same one that appears in domino/monomino tiling problems.

Recommended Answers

All 2 Replies

Member Avatar for Rashakil Fol

He either throws a nickel first or a dime first. The number of ways to pay is equal to the number of ways to pay by throwing a nickel first added to the number of ways to pay by throwing a dime first.

Member Avatar for MartyMcFly

lol, eight posts, all about homework. :)

Are they all off the same question sheet?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.