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

An easy arithmetic Le Monde mathematical puzzle again:

1. 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?
2.  If the number of units is now four, what is the optimal choice?

The first question is fairly easy to code

coinz <- function(x,y){
z=(1:149)
if (y<x){xx=x;x=y;y=xx}
ny=z%/%y
nx=(z%%y)%/%x
no=z-ny*y-nx*x
return(max(no+nx+ny))
}

and 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  4


A 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 (x<y){ xx=x;x=y;y=xx}
for (i in 2:149){
if (i%%x==0)
minco[i]=i%/%x
if (i%%y==0)
minco[i]=min(minco[i],i%/%y)
for (j in 1:max(1,trunc((i+1)/2)))
minco[i]=min(minco[i],minco[j]+minco[i-j])
}
return(max(minco))}


returns the lower value of M=11 (with x=7,y=23) in the first case and M=7 in the second one.