# Le Monde puzzle [#1053]

**R – Xi'an's Og**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

**A**n easy arithmetic Le Monde mathematical puzzle again:

*If coins come in units of 1, x, and y, what is the optimal value of (x,y) that minimises the number of coins representing an arbitrary price between 1 and 149?**If the number of units is now four, what is the optimal choice?*

**T**he first question is fairly easy to code

coinz <- function(x,y){ z=(1:149) if (yand returns M=12 as the maximal number of coins, corresponding to x=4 and y=22. And a price tag of 129. For the second question, one unit is necessarily 1 (!) and there is just an extra loop to the above, which returns M=8, with other units taking several possible values:

[1] 40 11 3 [1] 41 11 3 [1] 55 15 4 [1] 56 15 4A quick search revealed that this problem (or a variant) is solved in many places, from stackexchange (for an average—why average?, as it does not make sense when looking at real prices—number of coins, rather than maximal), to a paper by Shalit calling for the 18¢ coin, to Freakonomics, to Wikipedia, although this is about finding the minimum number of coins summing up to a given value, using fixed currency denominations (a knapsack problem). This Wikipedia page made me realise that my solution is not necessarily optimal, as I use the remainders from the larger denominations in my code, while there may be more efficient divisions. For instance, running the following dynamic programming code

coz=function(x,y){ minco=1:149 if (xreturns the lower value of M=11 (with x=7,y=23) in the first case and M=7 in the second one.

Toleave a commentfor the author, please follow the link and comment on their blog:R – Xi'an's Og.

R-bloggers.com offersdaily e-mail updatesabout R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.