<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/le-monde-puzzle-1053/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://xianblog.wordpress.com/2018/06/21/le-monde-puzzle-1045-2/"> R – Xi'an's Og</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p><strong><a rel="nofollow" href="https://xianblog.files.wordpress.com/2018/03/sieglemond.jpg" target="_blank"><img data-orig-file="https://xianblog.files.wordpress.com/2018/03/sieglemond.jpg" data-orig-size="660,281" data-medium-file="https://xianblog.files.wordpress.com/2018/03/sieglemond.jpg?w=300" data-attachment-id="35577" data-image-meta="{" data-image-description="" src="https://xianblog.files.wordpress.com/2018/03/sieglemond.jpg?w=450&h=192&fit=450%2C192&resize=450%2C192" data-permalink="https://xianblog.wordpress.com/2018/03/12/le-monde-puzzle-1044/sieglemond/" data-large-file="https://xianblog.files.wordpress.com/2018/03/sieglemond.jpg?w=450&amp;h=192&amp;fit=450%2C192&amp;resize=450%2C192" alt="" data-image-title="sieglemond" sizes="(max-width: 450px) 100vw, 450px" width="450" data-comments-opened="1" class="wp-image-35577" data-recalc-dims="1" height="192"></a>A</strong>n easy arithmetic <a rel="nofollow" href="https://xianblog.wordpress.com/2011/09/03/le-monde-puzzle-website/" title="Le Monde puzzle [website]" target="_blank">Le Monde mathematical puzzle</a> again:</p>
<ol>
<li><em>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? </em></li>
<li><em> If the number of units is now four, what is the optimal choice?</em><em><br>
</em></li>
</ol>
<p><strong>T</strong>he first question is fairly easy to code</p>
<pre>coinz &lt;- function(x,y){
  z=(1:149)
  if (y&lt;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))
}</pre>
<p>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:</p>
<pre>[1] 40 11  3
[1] 41 11  3
[1] 55 15  4
[1] 56 15  4
</pre>
<p>A quick search revealed that this problem (or a variant) is solved in many places, from <a rel="nofollow" href="https://cs.stackexchange.com/q/2734/40391" target="_blank">stackexchange</a> (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 <a rel="nofollow" href="http://www.cs.uwaterloo.ca/~shallit/Papers/change2.pdf" target="_blank">the 18¢ coin</a>, to <a rel="nofollow" href="http://freakonomics.com/2009/10/06/do-we-need-a-37-cent-coin/" target="_blank">Freakonomics</a>, to <a rel="nofollow" href="https://en.wikipedia.org/wiki/Change-making_problem" target="_blank">Wikipedia</a>, although this is about finding the minimum number of coins summing up to a given value, using fixed currency denominations (a knapsack problem). This <a rel="nofollow" href="https://en.wikipedia.org/wiki/Change-making_problem" target="_blank">Wikipedia</a> 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</p>
<pre>coz=function(x,y){
  minco=1:149
  if (x&lt;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))}
</pre>
<p>returns the lower value of M=11 (with x=7,y=23) in the first case and M=7 in the second one.</p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://xianblog.wordpress.com/2018/06/21/le-monde-puzzle-1045-2/"> R – Xi'an's Og</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/GbxpXzMD7B0" height="1"></a></div>