10
$\begingroup$

The main international airport in the Kingdom of Treisaria recently installed automatic currency exchange machines. You can insert banknotes from any of the major world currencies (dollars, euros, yen, pounds, etc.) and receive the equivalent amount in the local currency. The machines' screens display the current exchange rates (with a small processing fee pre-deducted).

Having spent some time in France prior to my trip there, I had a bunch of Euro notes on me, so that's the exchange rate I'm interested in. Currently, one euro buys exactly thirteen Treisarian denari.

The machines are programmed to always return the minimum number of banknotes + coins needed for the amount. For example, when the US version needs to give out $60, it's always as 50 + 10, never three 20's. However, since I wanted more small change, and there was nobody in line behind me to complain about me taking too long at the machine, I fed it my Euro notes one at a time.

  • When I put in €5, I receive 1 note and 5 coins.
  • When I put in €10, I receive 3 notes and 5 coins.
  • When I put in €20, I receive 4 notes and 4 coins.
  • When I put in €50, I receive 4 notes and 2 coins.
  • When I put in €100, I receive 3 notes and 2 coins.
  • When I put in €200, I receive 3 notes and 4 coins.
  • When I put in €500, I receive 6 notes and 5 coins.

Treisarian currency has a reputation for being unfriendly to tourists because they don't use the internationally-familiar Arabic numeral system, so people unfamiliar with the local script can't recognize the denominations.

But from the information above, can you work out what the denominations of Treisarian banknotes and coins are? (All are integers, as coins less than 1d have been withdrawn due to inflation. All banknotes are worth more than all coins.)

Hint #1

There are three denominations of coins and four denominations of banknotes.

Hint #2

The country's name is of Semitic origin.

Hint #3

The denominations are such that the greedy algorithm for change-making is optimal for any amount.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ "the internationally-familiar Arabic numeral system" Fun fact: the actual Arabic numeral system today (the one used in languages that use the Arabic alphabet) is completely different from what's referred to in the west as "Arabic numerals" :-) $\endgroup$
    – Rand al'Thor
    Nov 23, 2019 at 8:43
  • $\begingroup$ Is the highest coin valued less than the lowest note? $\endgroup$
    – JMP
    Nov 23, 2019 at 8:50
  • 2
    $\begingroup$ I don't see any reason to think it's unsolvable. It may be hard to solve, though. I am wondering whether it would be contrary to the spirit of the question to solve it by computer. $\endgroup$
    – Gareth McCaughan ♦
    Nov 23, 2019 at 18:10
  • 1
    $\begingroup$ Yup. But we know that a bunch of things are positive integers. $\endgroup$
    – Gareth McCaughan ♦
    Nov 23, 2019 at 19:55
  • 3
    $\begingroup$ A fundamental property in cash money design is that every integer amount should be payable, at least in theory. Can we assume that Treisarians have also followed this guideline? $\endgroup$
    – Bass
    Nov 23, 2019 at 23:10

1 Answer 1

Reset to default
5
$\begingroup$

Coins: 1, 3, 12
Notes: 36, 144, 432, 1728

I have to admit that I looked at hint 3, without which I would perhaps not be able to solve it in reasonable time.

With hint 3 it's somehow an easy guess that

smaller numbers should divide bigger ones.

Starting with the 5 euros and 10 euros, I can bound the value of the smallest note

between 33 and 41.

so without hesitation I immediately guess

that the smallest note is 36.

the rest are just try and try (reasonably fast, in several minutes).

After solving it, I think perhaps hint 2 could also be useful, at least to someone with better knowledge than me...

Improve this answer
$\endgroup$
2
  • $\begingroup$ How did you determine this? $\endgroup$
    – dan04
    Nov 24, 2019 at 4:50
  • $\begingroup$ @dan04 Just added explanations. $\endgroup$
    – WhatsUp
    Nov 24, 2019 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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