## Le Monde puzzle [#1053]

**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 (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.

## Leave a Reply