<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="https://www.r-bloggers.com/le-monde-puzzle-1006/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://xianblog.wordpress.com/2017/05/03/le-monde-puzzle-1006/"> 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><img height="185" alt="" width="273" src="https://encrypted-tbn3.gstatic.com/images?q=tbn:ANd9GcRsQd3v7efgSlmsNPKddzl-oQS9fZOF8a68V6KPmf5dnmI_EJ66rw">O</strong>nce the pseudo-story [noise] removed, a linear programming <a title="Le Monde puzzle [website]" target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/2011/09/03/le-monde-puzzle-website/">Le Monde mathematical puzzle</a>:</p>
<blockquote>
<p><em>For the integer linear programming problem</em></p>
<p>max 2x¹+2x²+x³+…+x¹⁰</p>
<p><em>under the constraints</em></p>
<p>x¹>x²+x³, x²>x³+x⁴, …, x⁹>x¹⁰+x¹, x¹⁰>x¹+x²</p>
<p><em> find a solution with the maximal number of positive entries.<br>
</em></p>
</blockquote>
<p><strong>E</strong>xpressed this way, it becomes quite straightforward to solve with the help of a <a target="_blank" rel="nofollow" href="https://cran.r-project.org/web/views/Optimization.html#MathematicalProgrammingSolvers">linear programming R code</a> like <a target="_blank" rel="nofollow" href="https://cran.r-project.org/web/packages/lpSolve/index.html">lpSolve</a>. Indeed, a simple iteration of the constraints shows that positive entries are necessarily bracketed by negative entries, since, e.g.,</p>
<p>x²&lt;-88x¹/55, x¹⁰&lt;-33x¹/55</p>
<p>(which applies to all consecutive triplets since the constraints are invariant by transposition). Hence there are at most five positive entries but calling <a target="_blank" rel="nofollow" href="https://cran.r-project.org/web/packages/lpSolve/index.html">lpSolve</a> with this option</p>
<pre>> lp (direction=&quot;max&quot;, 
objective.in=c(2,2,rep(1,8)),
const.mat=A, 
const.dir=rep(&quot;>=&quot;,10), 
const.rhs=rep(1,10)+A%*%c(rep(c(20,-1),5)), 
all.int=TRUE) 
Error: no feasible solution found
</pre>
<p>shows this is not possible. (The added vector is my way of getting around the constraint that <em><a target="_blank" rel="nofollow" href="https://cran.r-project.org/web/packages/lpSolve/index.html">lpSolve</a> only considers positive entries</em>. I therefore moved the negative entries by 20, meaning they are assumed to be larger than -20. Using the larger bound 50 does not change the outcome.) From there, there are 10 possible versions of vectors with four positive entries and a simple loop returns</p>
<pre>> masume
[1] -90
> topast
 [1] -11 1 -13 1 -15 1 -17 1 -19 -9
</pre>
<p>as the maximal criterion and argument of this maximum with four positive entries.</p>
<p>As an aside, the previous <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/2011/09/03/le-monde-puzzle-website/">Le Monde puzzle</a> [#1005] was also provided by a linear system: given 64 cubes, each of the 384 faces being painted in one of four colours, with exactly 40 of these cubes exhibiting the four colours,  the question was about the number of cubes that could be bicolour so that a mono-colour super-cube could be reconstituted for all colours.  Which amounted to solve the four equations</p>
<p>4a+2b=24,4c+2d=40, b+c=8,d+3a=24,</p>
<p>leading to 40 quadri-colour, 16 tri-colour, and 8 bi-colour cubes.</p>
<p>Filed under: <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/kids/">Kids</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/statistics/r-statistics/">R</a> Tagged: <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/competition/">competition</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/le-monde/">Le Monde</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/linear-programming/">linear programming</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/linear-system-of-equations/">linear system of equations</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/lpsolve/">lpSolve</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/mathematical-puzzle/">mathematical puzzle</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/optimisation/">optimisation</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/r/">R</a> <a target="_blank" rel="nofollow" href="http://feeds.wordpress.com/1.0/gocomments/xianblog.wordpress.com/33421/"><img alt="" src="http://feeds.wordpress.com/1.0/comments/xianblog.wordpress.com/33421/" border="0"></a> <img alt="" src="https://i1.wp.com/pixel.wp.com/b.gif?resize=1%2C1&ssl=1" border="0" data-recalc-dims="1"></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/2017/05/03/le-monde-puzzle-1006/"> 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 title="The R Project for Statistical Computing" rel="nofollow" href="https://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="https://www.r-bloggers.com/search/data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="https://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="https://www.r-bloggers.com/search/map">maps</a>, <a title="Animation in R" rel="nofollow" href="https://www.r-bloggers.com/search/animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="https://www.r-bloggers.com/search/sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="https://www.r-bloggers.com/search/SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="https://www.r-bloggers.com/search/git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="https://www.r-bloggers.com/search/hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="https://www.r-bloggers.com/search/PCA">PCA</a>, <a title="Time series" rel="nofollow" href="https://www.r-bloggers.com/search/time+series">time series</a>, <a title="finance trading" rel="nofollow" href="https://www.r-bloggers.com/search/trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/P5uqnsTcje4"></a></div>