Last year the inhabitants of Elfland (which are -of course- Elfs) had a referendum and decided to stop using barter and to adopt their own currency (the Elfcoin).

On January 1st, 2020 the central bank of Elfland released $100$ banknotes worth $1$ Elfcoin each so that the elfs can use them as currency in the next years. The bank is obviously worried about the wearing out of the banknotes, so they decided to recall $10$ banknotes every year and to replace them with $10$ new banknotes. The operation of recalling old banknotes and replacing them with new banknotes is done "atomically" on January the 1st of every year after 2020. The $10$ banknotes to recall are chosen at random among all the banknotes in Elfland every year, thus it could be the case (for example) that one or more banknotes released in 2021 are recalled in 2022.

Since no other country uses Elfcoin, the banknotes never exit Elfland. Moreover, the elfs never destroy or hide banknotes.


  1. After how many years you would expect that all the $100$ original banknotes will be recalled?
  2. What if the bank recalls $10$ random banknotes replacing them with $15$ new banknotes? (or with any other number greater than $10$ of banknotes)?
  • $\begingroup$ rot13(abg fher vs guvf urycf nalbar ohg V ena fbzr fvzhyngvbaf gb ortva jvgu naq sbhaq gung sbe gur svefg cneg vg fubhyq or nebhaq sbegl avar cbvag rvtug fvk lrnef) $\endgroup$
    – cmxu
    Jan 28 '20 at 15:56
  • $\begingroup$ Banknotes released in one year cannot be replaced in the same year? I.e. released in January and replaced in December... $\endgroup$
    – daw
    Jan 28 '20 at 15:56
  • $\begingroup$ @daw the banknotes are recalled and released the same day every year e.g. 1st January 2021, then 1st January 2022 then 1st January 2023 and so on. I'll update the question $\endgroup$
    – melfnt
    Jan 28 '20 at 16:03

Using this expected value formula:

let rate = (elfNotes / (elfNotes + yearly_added * i) * yearly_replaced / elfNotes); // yearly_replaced;
returned += (elfNotes - returned) * rate;

With yearly_added = 0 at year 51, the expected value is 99.53, so more likely than not that we have collected all of the original notes With yearly_added (15 added - 10 replaced) = 5, year 244 is the first time returned breaks 99.5%

I have a feeling I have not done this correctly. For one thing, I'm treating returned as a decimal value... I'm skeptical of my own answer, but hoping to learn the right approach to this when @melfnt or another poster reveals the right way to do it


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