<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-1070/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://xianblog.wordpress.com/2018/10/11/le-monde-puzzle-1070/"> 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/2015/10/lemondapari.jpeg" target="_blank"><img src="https://xianblog.files.wordpress.com/2015/10/lemondapari.jpeg?w=450&h=299&fit=456%2C456" data-recalc-dims="1"></a>R</strong>ewording <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>  fifth competition problem</p>
<blockquote>
<p><em>For the 3×3 tables below, what are the minimal number of steps to move from left to rights when the yellow tokens can only be move to an empty location surrounded by two other tokens?</em></p>
<p><em><img width="265" src="https://i1.wp.com/www.affairedelogique.com/backoffice/img/fck/affairedelogique/Piece1.jpg" height="124"> In the 4×4 table below, there are 6 green tokens. How many steps from left to right?<br>
</em></p>
</blockquote>
<p><img width="287" src="https://i0.wp.com/www.affairedelogique.com/backoffice/img/fck/affairedelogique/Piece2.jpg" height="136">Painful and moderately mathematical, once more… For the first question, a brute force simulation of random valid moves of length less than 100 returns solutions in 4 steps:</p>
<pre>     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
     1    <span>1</span>    1    0    <span>0</span>    1    0    0    1
     <span>1</span>    0    1    <span>0</span>    1    1    0    0    1
     0    0    1    1    <span>1</span>    1    0    <span>0</span>    1
     0    0    1    <span>1</span>    0    1    <span>0</span>    1    1
     0    0    1    0    0    1    1    1    1
</pre>
<p>But this is not an acceptable move because of the “other” constraint. Imposing this constraint leads to a solution in 9 steps, but is this the lowest bound?! It actually took me most of the weekend (apart from a long drive to and from a short half-marathon!) to figure out a better strategy than brute force random exploration: the trick I eventually figured out is to start from the finishing (rightmost) value F of the grid and look at values with solutions available in 1,2,… steps. This is not exactly dynamic programming, but it keeps the running time under control if there is a solution associated with the starting (leftmost) value S. (Robin proceeded reverse-wise, which in retrospect is presumably equivalent, if faster!) The 3×3 grid has 9 choose 5, ie 126, possible configurations with 5 coins, which means the number of cases remains under control. And even so for the 4×4 grid with 6 coins, with 8008 configurations. This led to a 9 step solution for n=3 and the proposed starting grid in yellow:<br>
<pre><br>
[1] 1 1 1 0 0 1 0 0 1<br>
[1] 1 1 0 0 1 1 0 0 1<br>
[1] 1 1 0 1 1 0 0 0 1<br>
[1] 0 1 0 1 1 1 0 0 1<br>
[1] 0 1 1 1 0 1 0 0 1<br>
[1] 1 1 1 1 0 0 0 0 1<br>
[1] 0 1 1 1 1 0 0 0 1<br>
[1] 0 0 1 1 1 0 0 1 1<br>
[1] 0 0 1 1 0 0 1 1 1<br>
[1] 0 0 1 0 0 1 1 1 1<br>
</pre><br>
and a 19 step solution for n=4:<br>
<pre><br>
[1] 1 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1<br>
[1] 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1<br>
[1] 1 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0<br>
[1] 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 0<br>
[1] 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0<br>
[1] 1 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0<br>
[1] 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0<br>
[1] 1 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0<br>
[1] 1 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0<br>
[1] 1 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0<br>
[1] 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0<br>
[1] 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 0<br>
[1] 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0<br>
[1] 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 0<br>
[1] 0 0 0 1 0 1 0 0 1 0 0 0 1 1 1 0<br>
[1] 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 0<br>
[1] 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0<br>
[1] 0 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0<br>
[1] 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0<br>
</pre><br>
The first resolution takes less than a minute and the second one just a few minutes (or less than my short morning run!). Surprisingly, using this approach does not require more work, which makes me wonder at the solution <a rel="nofollow" href="http://www.affairedelogique.com/espace_probleme.php?corps=concours2018" target="_blank">Le Monde journalists</a> will propose. Given the (misguided) effort put into my resolution, seeing a larger number of points for this puzzle is no wonder.
	<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/10/11/le-monde-puzzle-1070/"> 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 width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/7DhsL3mU0zU" height="1"></a></div>