tag:blogger.com,1999:blog-50088791052957711592018-09-15T19:03:36.185-07:00mathrecreationDan MacKinnonnoreply@blogger.comBlogger274125tag:blogger.com,1999:blog-5008879105295771159.post-74195910201578142202018-09-15T19:03:00.000-07:002018-09-15T19:03:36.148-07:00Solving (some) Logic Puzzles with Sets<div>As you may have noticed, since <a href="http://www.mathrecreation.com/2017/11/the-island-of-knights-and-knaves.html">around this time last year</a>, I have been playing around with generating puzzles based on those found in some of Raymond Smullyan's books. This has included <a href="https://dmackinnon1.github.io/knaves/">Knights and Knaves</a>, <a href="https://dmackinnon1.github.io/portia/">Portia's Caskets</a>, <a href="https://dmackinnon1.github.io/inspectorCraig/">The Case Files of Inspector Craig</a>, <a href="https://dmackinnon1.github.io/inspectorCraig/tiger.html">Tigers and Treasure</a>, and <a href="https://dmackinnon1.github.io/inspectorCraig/dreamers.html">The Isle of Dreams</a>. Some of the differences between puzzles are superficial: A "Portia's Casket" puzzle can be recast as a "Knights and Knaves" puzzle, for example. Even though there is some common deep structure to these various puzzles, I've found that sometimes the puzzle types call out for different approaches when writing solvers or generators.<br /><br /></div><div>The latest puzzle type that I have been enjoying is based on some puzzles found in Smullyan's <i><a href="https://archive.org/details/WhatIsTheNameOfThisBook">What is the Name of This Book?</a>. </i>The "Lion and the Unicorn" puzzles are built around characters from Lewis Carroll's <a href="https://en.wikipedia.org/wiki/Through_the_Looking-Glass" style="font-style: italic;">Through the Looking-Glass, and What Alice Found There</a><i>, </i>and for this logic puzzle variation, I found that using <a href="https://en.wikipedia.org/wiki/Set_theory">sets</a> to model the puzzle (rather than, say, <a href="http://www.mathrecreation.com/2018/02/inspector-craig-logical-detective.html">propositions</a>, <a href="http://www.mathrecreation.com/2017/12/constructing-portias-caskets.html">truth tables</a>, or <a href="http://www.mathrecreation.com/2012/05/liar-truther-accusation-graphs.html">graphs</a>) seemed to make the most sense.</div><div><i><br /></i></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-6rRGBW_aU-A/W5v_RUleF-I/AAAAAAAAEuc/6sofCKRx63w2mk3qEV25VHPwqbtJvHQSwCLcBGAs/s1600/lion_unicorn.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="424" data-original-width="660" height="205" src="https://1.bp.blogspot.com/-6rRGBW_aU-A/W5v_RUleF-I/AAAAAAAAEuc/6sofCKRx63w2mk3qEV25VHPwqbtJvHQSwCLcBGAs/s320/lion_unicorn.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>The Lion and the Unicorn, posing <br />at the <a href="https://en.wikipedia.org/wiki/East_Block">East Block</a> </i></div><div><br /></div><div>As described in the chapter 47 <i>Alice and the Forest of Forgetfulness</i>,</div><blockquote class="tr_bq"><i>When Alice entered the Forest of Forgetfulness, she did not forget everything, only certain things. She often forgot her name, and the one thing she was most likely to forget was the day of the week. Now, the Lion and the Unicorn were frequent visitors to the forest. These two are strange creatures. The Lion lies on Mondays, Tuesdays, and Wednesdays, and tells the truth on the other days of the week. The Unicorn, on the other hand, lies on Thursdays, Fridays, and Saturdays, but tells the truth on other days of the week.</i></blockquote><blockquote class="tr_bq"><i>One day, Alice met the Lion and the Unicorn resting under a tree. They made the following statements:</i> </blockquote><blockquote class="tr_bq"><i>Lion: Yesterday was one of my lying days.</i> </blockquote><blockquote class="tr_bq"><i>Unicorn: Yesterday was one of my lying days too.</i></blockquote><blockquote class="tr_bq"><i>Alice must know: What day is today? </i></blockquote>If you think you have a solution to this - test it out on <a href="https://dmackinnon1.github.io/forgetfulForest/?id=15">the interactive version of the puzzle</a>.<br /><br />If we model this using sets, our <a href="https://en.wikipedia.org/wiki/Domain_of_discourse">universe of discourse</a> for this problem is the days of the week.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-zC067_tL5F8/W5wXjjUlB6I/AAAAAAAAEuo/jIVlckuNHqoAHGYmb5OuZ-VG_6STv8LqgCLcBGAs/s1600/days_week.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="75" data-original-width="456" height="65" src="https://3.bp.blogspot.com/-zC067_tL5F8/W5wXjjUlB6I/AAAAAAAAEuo/jIVlckuNHqoAHGYmb5OuZ-VG_6STv8LqgCLcBGAs/s400/days_week.png" width="400" /></a></div><br />We consider the set <i>L</i> of days for which the lion is lying, and the set <i>U</i> of days for which the unicorn is lying.<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-vgb-T2IkwpM/W5wY94IqWiI/AAAAAAAAEu0/pX-eDJ32IMo4C0PXfsVM22UTOYJmCAkbgCLcBGAs/s1600/lying_sets.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="92" data-original-width="380" height="77" src="https://2.bp.blogspot.com/-vgb-T2IkwpM/W5wY94IqWiI/AAAAAAAAEu0/pX-eDJ32IMo4C0PXfsVM22UTOYJmCAkbgCLcBGAs/s320/lying_sets.png" width="320" /></a></div><br />The days that the animals are telling the truth are listed in the complements of each set.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-sqFiYgaGm5E/W5wsJaBATmI/AAAAAAAAEvU/vTMaYVsUA7wD9I2zxdesR1dtWo6AF8YrQCLcBGAs/s1600/complements2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="103" data-original-width="451" height="91" src="https://3.bp.blogspot.com/-sqFiYgaGm5E/W5wsJaBATmI/AAAAAAAAEvU/vTMaYVsUA7wD9I2zxdesR1dtWo6AF8YrQCLcBGAs/s400/complements2.png" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"></div><br />These two sets have an empty intersection - the two characters never lie at the same time. The intersection of their truth-telling days is non empty, however: both tell the truth on the same day once a week.<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/--gQd7xR2Xp0/W5wsYORv__I/AAAAAAAAEvY/uEK3gTaTaow1cBmGrA5mdbi5Eq0uw1xxACLcBGAs/s1600/intersect2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="115" data-original-width="249" height="91" src="https://2.bp.blogspot.com/--gQd7xR2Xp0/W5wsYORv__I/AAAAAAAAEvY/uEK3gTaTaow1cBmGrA5mdbi5Eq0uw1xxACLcBGAs/s200/intersect2.png" width="200" /></a></div>The set <i>Days</i> is a set with structure, the days are an ordered set - the lion and the unicorn can talk about 'yesterday' and 'tomorrow.' For any set of days we can ask for its 'tomorrows' - the set of next days, or its set of 'yesterdays', the set of preceding days. When the lion says "I told lies yesterday" this can be translated as "today is a tomorrow for one of my lying days." The set of days covered by Lion's statement would be:<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-SjT5o1uXeOQ/W5ws53saGyI/AAAAAAAAEvk/ctKVfifKZ1oKT69wu06YxkQMQv-eCpFMwCLcBGAs/s1600/lion_statement.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="51" data-original-width="552" height="36" src="https://3.bp.blogspot.com/-SjT5o1uXeOQ/W5ws53saGyI/AAAAAAAAEvk/ctKVfifKZ1oKT69wu06YxkQMQv-eCpFMwCLcBGAs/s400/lion_statement.png" width="400" /></a></div><br />But do any of the days covered by Lion's statement coincide with a day that he is telling the truth? To believe his statement about what day it is, it must describe a day that he is actually speaking truthfully. If Lion is telling the truth, it must be a day in the intersection of the days in Lion's statement and the set of Lion's truthful days.<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-MmvWYQA69iA/W5wt2vyLY3I/AAAAAAAAEvw/bUVwnwl814wMMVga-UNUoCOduLSBezPFACLcBGAs/s1600/thursday.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="55" data-original-width="264" height="41" src="https://3.bp.blogspot.com/-MmvWYQA69iA/W5wt2vyLY3I/AAAAAAAAEvw/bUVwnwl814wMMVga-UNUoCOduLSBezPFACLcBGAs/s200/thursday.png" width="200" /></a></div><br />But, Lion could be lying. If Lion is lying, then today is in the intersection of the days not in Lion's statement, and Lion's lying days.<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-cYOKl1bf39Q/W5wucIcxmOI/AAAAAAAAEv4/5VsGpVeoaCUabBp8wKBdXiKo0v0KtvwZQCLcBGAs/s1600/monday.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="59" data-original-width="257" height="45" src="https://4.bp.blogspot.com/-cYOKl1bf39Q/W5wucIcxmOI/AAAAAAAAEv4/5VsGpVeoaCUabBp8wKBdXiKo0v0KtvwZQCLcBGAs/s200/monday.png" width="200" /></a></div>Since we don't know whether the lion is telling the truth or lying, we have to consider both possibilities, so the set of days that it could be, based only on Lion's statement is:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-dh7zRffwYvk/W52tZkBB8vI/AAAAAAAAEwQ/k182Qp9Ii0w6HkctNpIeiUMbzuMdFsm4ACLcBGAs/s1600/lion_days2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="74" data-original-width="282" src="https://2.bp.blogspot.com/-dh7zRffwYvk/W52tZkBB8vI/AAAAAAAAEwQ/k182Qp9Ii0w6HkctNpIeiUMbzuMdFsm4ACLcBGAs/s1600/lion_days2.png" /></a></div><br />Going through a similar process, we can get another set of days based on the Unicorn's statements.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Df11voW5k2Y/W52t7LBgRiI/AAAAAAAAEwc/zMa10iO7q3I5fweZxI40NcIkFiYGy_ktACLcBGAs/s1600/unicorn_days2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="68" data-original-width="269" src="https://1.bp.blogspot.com/-Df11voW5k2Y/W52t7LBgRiI/AAAAAAAAEwc/zMa10iO7q3I5fweZxI40NcIkFiYGy_ktACLcBGAs/s1600/unicorn_days2.png" /></a></div><br />Days that fall in both the set from the Lion <i>and</i> the set from the Unicorn are possible solutions for today's day - if the intersection is empty, then there is no solution, if there are several days in the intersection, then the puzzle is ambiguous, if there is a single day in the intersection, that is today:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-0DSBf5cWv_Q/W52u5aZ3okI/AAAAAAAAEws/j_IHjbyQotoIMLSfIi6ggfbB4exWIRbAQCLcBGAs/s1600/all_together.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="103" data-original-width="487" height="83" src="https://2.bp.blogspot.com/-0DSBf5cWv_Q/W52u5aZ3okI/AAAAAAAAEws/j_IHjbyQotoIMLSfIi6ggfbB4exWIRbAQCLcBGAs/s400/all_together.png" width="400" /></a></div><br />The notation might make this way of thinking seem difficult - here is the process stated a bit more plainly (see that it lines up with the formula above...):<br /><br />1. Consider the Lion. Which days does the Lion's statement refer to?<br />2. Of these days, which coincide with Lion's truthful days?<br />3. Which of the days are not covered by the Lion's statement? Do any of these coincide with Lion's lying days?<br />4. Combine these two lists of days from the Lion.<br />5. Follow steps 1 through 4 for the Unicorn to produce a list of possible days from the Unicorn.<br />6. If there is one day that that is in both the Lion's list and the Unicorn's list, that is the solution.<br /><br />We can come up with variations on this puzzle by varying the statements made by the Lion and the Unicorn. Instead of saying "I told lies yesterday," we could have them say things like "I will tell truths tomorrow" or "today is a week day", or even "today is Wednesday." Some of these will generate good puzzles (one element in the final set), others may not.<br /><br />A Jupyter notebook that generates 132 puzzles like this can be found <a href="https://gist.github.com/dmackinnon1/098dd90adf8312a1da2c02860798e496">here</a>, and you can the puzzles out <a href="https://dmackinnon1.github.io/forgetfulForest/">over here</a>.<br /><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/KW7gw8ZK4DQ" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2018/09/solving-some-logic-puzzles-with-sets.htmltag:blogger.com,1999:blog-5008879105295771159.post-41930987375559270652018-09-06T11:13:00.000-07:002018-09-06T11:13:25.611-07:00generating celtic knot patternsThis post describes an algorithm for generating <a href="https://en.wikipedia.org/wiki/Celtic_knot">celtic knot patterns</a> - ornamental knots, links, and braids that are laid out in a grid, like the one below:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-7MzshhMqWPY/W144X-DdLvI/AAAAAAAAEoA/G4Wpg9Cbnd0rdtBFrbGKSXT9Jx_LLKU-ACLcBGAs/s1600/simple2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="408" data-original-width="266" height="320" src="https://2.bp.blogspot.com/-7MzshhMqWPY/W144X-DdLvI/AAAAAAAAEoA/G4Wpg9Cbnd0rdtBFrbGKSXT9Jx_LLKU-ACLcBGAs/s320/simple2.png" width="208" /></a></div><br />If you would rather skip reading about how these are generated and start playing around with creating patterns like the one above, please try out the <a href="https://dmackinnon1.github.io/celtic/">editor</a> and <a href="https://dmackinnon1.github.io/celtic/random.html">random knot-pattern generator</a> that I've posted on my <a href="https://github.com/dmackinnon1">github</a> <a href="https://dmackinnon1.github.io/">pages</a>.<br /><br />I have tried out various strategies for generating these patterns (for example, <a href="https://www.mathrecreation.com/2008/07/knot-tiles.html">using</a> <a href="https://dmackinnon1.github.io/quiltic/">tiles</a>), but the method described here is closest to how I like to draw them by hand, as described in the book by Aidan Meehan, <i>Celtic Design: Knotwork - The Secret Method of the Scribes.</i> The variation offered here is intended to suggest how to write a program to generate these patterns based on a simplified version of the techniques in Meehan's book.<br /><br />A knot pattern is made up of strands that represent string or chord, and the gaps between the woven strands. The technique described below actually involves drawing the gaps, with the strands emerging out of the negative space between the gaps. Essentially, a grid of dots are drawn, and lines are selectively drawn between adjacent dots - these become the gaps between the strands. Additional rules are applied to connect the dots to create a woven effect, and the dots are replaced with polygons to create a more stylised effect.<br /><br /><b>1) define primary grid points</b><br />A knot pattern is laid out on a square coordinate system using a set of "primary" points that are set at one unit distances in the horizontal and vertical directions. We'll say that (0,0) is the top left corner of the grid, and the positive <i>x</i> direction is towards the right and positive <i>y</i> direction is down. The dimensions of the primary grid must be odd (there must be a total odd number of dots in both the <i>x</i> and <i>y</i> directions). Because we are starting with (0,0) in the top left, the top right point (<i>x</i>, 0) must have x even (4 in the example below), and the bottom left point (0,<i>y</i>) must have y even (6 in the example below).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-y34mxxvpzV4/W3jo0AZGwxI/AAAAAAAAEps/cu4LMR9-lCwxLEEZylF8kQRdG-aF368fACLcBGAs/s1600/primaryGrid.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="390" data-original-width="325" height="320" src="https://1.bp.blogspot.com/-y34mxxvpzV4/W3jo0AZGwxI/AAAAAAAAEps/cu4LMR9-lCwxLEEZylF8kQRdG-aF368fACLcBGAs/s320/primaryGrid.png" width="266" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>the primary grid</i></div><div class="separator" style="clear: both; text-align: center;"></div><br /><i>(Note: In Meehan's account, things are layered a little differently so what we are calling the primary grid is referred to as the tertiary grid.)</i><br /><i><br /></i><b>2) identify secondary grid points</b><br />Some of the points on the grid are special - these form a secondary grid. The special secondary grid points are those where both <i>x</i> and <i>y</i> values are even, or both are odd.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-_as6VLcVf2Q/W3juJ6Rc97I/AAAAAAAAEqE/R8zNfSQTLdEQwqbHXtO_x_yK6AuEvSZXgCLcBGAs/s1600/secondaryGrid.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="389" data-original-width="319" height="320" src="https://1.bp.blogspot.com/-_as6VLcVf2Q/W3juJ6Rc97I/AAAAAAAAEqE/R8zNfSQTLdEQwqbHXtO_x_yK6AuEvSZXgCLcBGAs/s320/secondaryGrid.png" width="262" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>the secondary grid</i></div><div class="separator" style="clear: both; text-align: center;"></div><br />In step 4 below, the secondary grid points where both <i>x</i> and <i>y</i> are even will be referred to as <i>even nodes</i>, and those that have both <i>x</i> and <i>y</i> odd will be referred to as <i>odd nodes</i>. The requirement to have the primary grid have odd dimensions (step 1) was needed to ensure that the corners of the pattern are all secondary points.<br /><i><br /></i><b>3. draw a quadrilateral around the nodes</b><br />Each node will become a gap in the node pattern - the basic shape of a gap is quadrilateral whose vertices lie 1/4 unit above, below, and to the right and left of each node.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/--t3hg3zsdOM/W5FMtD9MRxI/AAAAAAAAEr4/OKuDX3WZLG4BPnWzbqvzHwNWL5sZPcFiACLcBGAs/s1600/single_node.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="460" data-original-width="494" height="185" src="https://2.bp.blogspot.com/--t3hg3zsdOM/W5FMtD9MRxI/AAAAAAAAEr4/OKuDX3WZLG4BPnWzbqvzHwNWL5sZPcFiACLcBGAs/s200/single_node.png" width="200" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>the basic node polygon</i></div><br />With all of the polygons drawn for the nodes, we get a grid of 'diamonds' like this:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-ET807dyA3HE/W5FM-EnRmOI/AAAAAAAAEsA/N4_1dBLs4_oVMKvnTgO2BDcUY3yGVk04ACLcBGAs/s1600/nodes_drawn.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="504" data-original-width="381" height="320" src="https://2.bp.blogspot.com/-ET807dyA3HE/W5FM-EnRmOI/AAAAAAAAEsA/N4_1dBLs4_oVMKvnTgO2BDcUY3yGVk04ACLcBGAs/s320/nodes_drawn.png" width="241" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>node polygons drawn for <br />secondary grid points</i></div><br /><br /><b>4. extend lines from node polygon vertices</b><br />To create a woven affect, we extend lines from the vertices of each node polygon<br /><div><br /></div><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-zKOgNlz1N10/W5FT9rVXZfI/AAAAAAAAEsY/XIkvTeWh0DsNpMvY3XIf6t2Z7iIQz6PugCLcBGAs/s1600/even_odd2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="340" data-original-width="681" height="198" src="https://1.bp.blogspot.com/-zKOgNlz1N10/W5FT9rVXZfI/AAAAAAAAEsY/XIkvTeWh0DsNpMvY3XIf6t2Z7iIQz6PugCLcBGAs/s400/even_odd2.png" width="400" /></a></div><br />Doing this for all nodes creates an image like the one below.￼<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-gq2iIPW4slI/W5FUg6BpWgI/AAAAAAAAEsg/adCCwZr4NdcxOVN5grDr5XwaqJ9RYFUwwCLcBGAs/s1600/with_node_lines.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="496" data-original-width="376" height="320" src="https://1.bp.blogspot.com/-gq2iIPW4slI/W5FUg6BpWgI/AAAAAAAAEsg/adCCwZr4NdcxOVN5grDr5XwaqJ9RYFUwwCLcBGAs/s320/with_node_lines.png" width="242" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>lines extended from node <br />polygon vertices</i></div><br />If you exchange the rules for odd and even nodes, you end up with a correct "opposite" weave: strands that were going under instead go over, and vice-versa.<br /><br /><b>5<i>. </i>place barriers, drop lines</b><br />In the above image, the simple woven pattern seems to extend off the sides. To create an edge boundary for the pattern, and to create more interesting twists and turns, we follow some rules for drawing boundaries.<br /><br /><i>boundary rule 1</i>: A boundary can connect any two non-diagonally adjacent nodes (secondary points), as long as rule 2 is not violated. The midpoint of a boundary segment will be a primary point.<br /><br /><i>boundary rule 2</i>: A primary point cannot have more than one boundary going through it.<br /><br />The example below shows boundaries drawn along the edge of the image, as well as some internal boundaries.<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-XDC8Vzno7ag/W5FX3GvDtEI/AAAAAAAAEss/9aZ6blad8QsVf20U8GizQpuyCtBXwvoNACLcBGAs/s1600/boundaries_drawn.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="493" data-original-width="375" height="320" src="https://4.bp.blogspot.com/-XDC8Vzno7ag/W5FX3GvDtEI/AAAAAAAAEss/9aZ6blad8QsVf20U8GizQpuyCtBXwvoNACLcBGAs/s320/boundaries_drawn.png" width="243" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>legal boundary examples, showing<br />primary and secondary points <br />(node polygons are hidden)</i></div><br />Now that we have introduced boundaries, we refine how lines are drawn coming out of the nodes (adjusting step 4):<br /><br /><i>node-line rule</i>: Only draw a line from a node vertex if there is no boundary across from the vertex.<br /><br />Applying the node-line rule, and drawing the polygons (and dropping the primary grid points) we get an image like the one below, where the weaving respects the boundaries - the strands (in white) that emerge seem to bounce off the edges and twist to avoid internal boundaries.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-L9mi8Yh-s1E/W5FYSMhfGbI/AAAAAAAAEs0/cHgspXAbMvEqIMFCWqLW-bQk3deLcfqFACLcBGAs/s1600/lines_adjusted.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="490" data-original-width="372" height="320" src="https://2.bp.blogspot.com/-L9mi8Yh-s1E/W5FYSMhfGbI/AAAAAAAAEs0/cHgspXAbMvEqIMFCWqLW-bQk3deLcfqFACLcBGAs/s320/lines_adjusted.png" width="242" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>node polygons, boundaries, and lines </i></div><br /><b>6. refine node polygons</b><br />We can apply some styling rules to make the pattern look smoother - these changes to our original node polygon (step 3) will be based on whether or not there are boundaries next to the node.<br /><br /><i>node-style rule</i>: Truncate (chop off) the vertex of a node polygon that is next to a boundary.<br /><br />Below is the same pattern above, but with the node polygons following the node-style rule. You can see the effects of the rule most clearly by looking at the nodes near the edge of the image, and particularly the corner nodes.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-ygiFmXyjcUs/W5FZpkRqmNI/AAAAAAAAEtA/ePo2urD5q4sC3hgde3x6ibXcFm8XRhDTgCLcBGAs/s1600/truncated_nodes.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="489" data-original-width="369" height="320" src="https://3.bp.blogspot.com/-ygiFmXyjcUs/W5FZpkRqmNI/AAAAAAAAEtA/ePo2urD5q4sC3hgde3x6ibXcFm8XRhDTgCLcBGAs/s320/truncated_nodes.png" width="241" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>pattern using truncated <br />node polygons</i></div><br />It is possible to add further adjustments to how the nodes and lines are drawn to create smoother looking knot patterns. I have experimented a bit, but have not obtained great results. Here's an example of the same patter above that adjusts the node polygons and line thicknesses:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-4cRMWYlA7pA/W5FcTUdtojI/AAAAAAAAEtM/3CmRPPHiRIoonOXJWcL-bP6DJBKf_-FnwCLcBGAs/s1600/curvy.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="495" data-original-width="372" height="320" src="https://3.bp.blogspot.com/-4cRMWYlA7pA/W5FcTUdtojI/AAAAAAAAEtM/3CmRPPHiRIoonOXJWcL-bP6DJBKf_-FnwCLcBGAs/s320/curvy.png" width="240" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>a slightly different style applied <br />to the knot pattern</i></div><br />I hope you enjoy playing around with this - either implementing the process described above yourself or playing around with my version: there is a simple editor available <a href="https://dmackinnon1.github.io/celtic/">here</a>, and one that allows for further adjustments of the size and dimensions <a href="https://dmackinnon1.github.io/celtic/free.html">here</a>.<br /><br /><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/rbt0WohbdmI" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2018/09/generating-celtic-knot-patterns.htmltag:blogger.com,1999:blog-5008879105295771159.post-44174192182209213472018-06-06T19:12:00.000-07:002018-06-06T19:12:29.648-07:00origami workshop againA few years back, I posted <a href="http://www.mathrecreation.com/2014/05/origami-workshop.html">some notes about an origami workshop</a> that I had run with some middle school students. Last week I had the opportunity to run origami workshops with similar groups of students, using many of the same models I mentioned before (including the <a href="http://www.mathrecreation.com/2011/01/simple-origami-and-math-jumping-frog.html">hopping frog</a>).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-bRCYlScF1Us/U4VR4FHWI3I/AAAAAAAACes/YM28JceeEror7hU5VotnyOVOQLEHYrpjgCPcBGAYYCw/s1600/frog-crease.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="228" data-original-width="368" height="198" src="https://4.bp.blogspot.com/-bRCYlScF1Us/U4VR4FHWI3I/AAAAAAAACes/YM28JceeEror7hU5VotnyOVOQLEHYrpjgCPcBGAYYCw/s320/frog-crease.JPG" width="320" /></a></div><br /><br />One nice model that I used this time that is not mentioned in that other post is the <a href="https://origamiusa.org/diagrams/multiform">multiform</a> (aka <a href="https://origamiusa.org/diagrams/multiform">windmill/pinwheel</a>) - a flexible hinged surface from which several simple models can be folded, including the <a href="https://makercamp.com/wp-content/uploads/2015/07/Origami-Pinwheel-Final.pdf">windmill</a>, the <a href="https://origamiusa.org/files/house.pdf">house</a>, and the <a href="http://make-origami.com/origami-pajarita/">pajarita</a>, and which can be extended to form the<a href="https://origamiusa.org/diagrams/masu"> masu box</a> and others.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-MNNXbpjnLJ4/Wxgi1_9w5cI/AAAAAAAAEjk/8ELLlEOGCJwI83oyYTEzmMnmMaYs018NQCLcBGAs/s1600/multiform.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="243" data-original-width="240" src="https://1.bp.blogspot.com/-MNNXbpjnLJ4/Wxgi1_9w5cI/AAAAAAAAEjk/8ELLlEOGCJwI83oyYTEzmMnmMaYs018NQCLcBGAs/s1600/multiform.PNG" /></a></div><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/a1tn7es3Mxg" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2018/06/origami-workshop-again.htmltag:blogger.com,1999:blog-5008879105295771159.post-52315105479506413092018-05-17T13:40:00.000-07:002018-05-18T14:46:07.489-07:00The Isle of DreamsAfter a short break, we are returning to some logic puzzles inspired by those of <a href="https://en.wikipedia.org/wiki/Raymond_Smullyan">Raymond Smullyan</a>. Earlier we visited the <a href="http://www.mathrecreation.com/2017/11/the-island-of-knights-and-knaves.html">island of knights and knaves</a>, looked into <a href="http://www.mathrecreation.com/2017/12/constructing-portias-caskets.html">Portia's caskets</a>, explored <a href="http://www.mathrecreation.com/2018/02/inspector-craig-logical-detective.html">the case files of Inspector Leslie Craig</a>, and looked behind doors for <a href="http://www.mathrecreation.com/2018/03/tigers-and-treasure.html">tigers and treasure</a>. In this post, we are visiting the <a href="https://dmackinnon1.github.io/inspectorCraig/dreamers.html">Isle of Dreams</a>. As Smullyan says in his book <i>The Lady or The Tiger?:</i><br /><blockquote class="tr_bq"><i>I once dreamed that there was a certain island called the Isle of Dreams. The inhabitants of this island dream quite vividly; indeed, their thoughts while asleep are as vivid as while awake. Moreover, their dream life has the same continuity from night to night as their waking life has from day to day. As a result, some of the inhabitants sometimes have difficulty in knowing whether they are awake or asleep at a given time. </i> </blockquote><blockquote class="tr_bq"><i>Now, it so happens that each inhabitant is of one of two types: diurnal or nocturnal. A diurnal inhabitant is characterised by the fact that everything he believes while he is awake is true, and everything he believes while he is asleep is false. A nocturnal inhabitant is the opposite: everything a nocturnal person believes while asleep is true, and everything he believes while awake is false. </i></blockquote>On this island then, each islander has a type (diurnal or nocturnal), and a state (awake or asleep), and based on their type and state, you can assess the veracity of their thoughts (either true or false).<br /><br />To play around with this, I decided to make some puzzles similar to ones found in <i>The Lady or The Tiger?</i>, but based on the thoughts of two islanders A and B. Each islander has two distinct thoughts: one about themselves (either about their state or their type), and one about the other (either their state or their type). Importantly, these thoughts occur to both A and B at exactly the same time. Here is an example:<br /><ul style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; list-style-type: none; margin-bottom: 10px; margin-top: 0px; padding-left: 40px;"><li style="box-sizing: border-box; padding-bottom: 10px;"><br class="Apple-interchange-newline" />Islander <span style="box-sizing: border-box; font-weight: 700;">A</span> has two distinct thoughts at the same moment: <span style="box-sizing: border-box; font-weight: 700;">I am nocturnal. B is diurnal.</span></li><li style="box-sizing: border-box; padding-bottom: 10px;">At the same moment, islander <span style="box-sizing: border-box; font-weight: 700;">B</span> has these distinct thoughts: <span style="box-sizing: border-box; font-weight: 700;">I am awake. A is diurnal.</span></li></ul>We want to know: what is the actual type and state of both A and B? Can we know everything about them, or is their something about them that we cannot tell? Or maybe these thoughts are impossible, and lead to contradictions.<br /><br />To solve these kinds of puzzles, it helps to know the <b>Four Laws of the Isle of Dreams</b>:<br /><br /><ol style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px; margin-top: 0px;"><em style="box-sizing: border-box;"><li style="box-sizing: border-box; padding-bottom: 10px;">An islander while awake will believe they are diurnal.</li><li style="box-sizing: border-box; padding-bottom: 10px;">An islander while asleep will believe they are nocturnal.</li><li style="box-sizing: border-box; padding-bottom: 10px;">Diurnal inhabitants at all times believe they are awake.</li><li style="box-sizing: border-box; padding-bottom: 10px;">Nocturnal inhabitants at all times believe they are asleep.</li></em></ol>Let's just establish the first law, and then you should try to convince yourself of the others. Consider the case of a diurnal awake islander: because they are diurnal and awake, they think true thoughts, so they will correctly think that they are diurnal. Second, consider the case of a nocturnal awake islander: because they are nocturnal and awake, they will think false thoughts, and will conclude that they are diurnal. So, no matter whether an islander is diurnal or nocturnal, when awake they will think they are diurnal (some correctly, some falsely). Using this along with rule 2, if an islander thinks they are diurnal, you should conclude that they are awake.<br /><br />Now back to the puzzle:<br /><br /><ul style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; list-style-type: none; margin-bottom: 10px; margin-top: 0px; padding-left: 40px;"><li style="box-sizing: border-box; padding-bottom: 10px;">Islander <span style="box-sizing: border-box; font-weight: 700;">A</span> has two distinct thoughts at the same moment: <span style="box-sizing: border-box; font-weight: 700;">I am nocturnal. B is diurnal.</span></li><li style="box-sizing: border-box; padding-bottom: 10px;">At the same moment, islander <span style="box-sizing: border-box; font-weight: 700;">B</span> has these distinct thoughts: <span style="box-sizing: border-box; font-weight: 700;">I am awake. A is diurnal.</span></li></ul>Applying the four laws of the Isle of Dreams to the first thoughts of the islanders in the puzzle above, we know that A must be asleep (law 2) , and that B must be diurnal (law 3). Now turning to A's second thought: because they are asleep and thinking something that is true (B is diurnal) A must be nocturnal. B's second thought is not true, so since they are diurnal they must be asleep. So, A is nocturnal and asleep, while B is diurnal and asleep. Sweet dreams, A and B.<br /><br />How many puzzles can we make like this, where we have two islanders, each thinking something about their state or type and something about the state or type of the other? Well, there are 4 possible thoughts an islander could have about themselves (I am awake/asleep/nocturnal/diurnal) and 4 possible thoughts about the other (They are awake/asleep/nocturnal/diurnal), giving us 16 pairs of thoughts. Since there are two islanders involved, this gives 256 puzzles (really only 128 truly different puzzles, as A and B are interchangeable).<br /><br />You can try out all 256 of them, or as many as you like, <a href="https://dmackinnon1.github.io/inspectorCraig/dreamers.html">here</a>. They look something like this:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-B8xkwDTvbnU/Wv3c85aw_hI/AAAAAAAAEhQ/ZMteMv7XxeUd6Exda9Gt0ukrhpAGID65QCLcBGAs/s1600/example_dreamers.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="715" data-original-width="625" height="400" src="https://4.bp.blogspot.com/-B8xkwDTvbnU/Wv3c85aw_hI/AAAAAAAAEhQ/ZMteMv7XxeUd6Exda9Gt0ukrhpAGID65QCLcBGAs/s400/example_dreamers.png" width="348" /></a></div><br /><br />This collection of puzzles has some interesting features. There are 192 that are completely solvable: you can find the type and state of both A and B from the thoughts that they think (like the example above). There are 32 partially solvable puzzles, where the first thoughts of A and B (their thoughts about themselves) tell us something about their state and type, but their second thoughts (about the other islander) are inconclusive. Finally, there are 32 puzzles included in the set where the thoughts of A and B are contradictory, and therefore impossible. We can include these contradictory items in the set, as the question page gives you the chance to identify these nasty puzzles.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-p1sHKw6In8A/Wv3ceCZdcsI/AAAAAAAAEhI/6qH1BNAU7Pwn_ReEejQ7Xab3bU-q0vf7ACLcBGAs/s1600/impossible.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="76" data-original-width="404" height="60" src="https://2.bp.blogspot.com/-p1sHKw6In8A/Wv3ceCZdcsI/AAAAAAAAEhI/6qH1BNAU7Pwn_ReEejQ7Xab3bU-q0vf7ACLcBGAs/s320/impossible.png" width="320" /></a></div><br /><br />It turns out that the distribution of the partially solvable and impossible puzzles display an interesting pattern. Let's consider all 16 pairs of thoughts, and make a graph showing which combinations are (a) completely solvable, (b) partially solvable, or (c) impossible.<br /><br />Here are the 16 pairs of thoughts an islander might have:<br /><br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">1: I am awake. The other is awake.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">2: I am awake. The other is asleep.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">3: I am awake. The other is diurnal.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">4: I am awake. The other is nocturnal.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">5: I am asleep. The other is awake.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">6: I am asleep. The other is asleep.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">7: I am asleep. The other is diurnal.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">8: I am asleep. The other is nocturnal.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">9: I am diurnal. The other is awake.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">10: I am diurnal. The other is asleep.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">11: I am diurnal. The other is diurnal.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">12: I am diurnal. The other is nocturnal.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">13: I am nocturnal. The other is awake.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">14: I am nocturnal. The other is asleep.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">15: I am nocturnal. The other is diurnal.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">16: I am nocturnal. The other is nocturnal.</span></div><br />Let's create a graph where the horizontal axis represents A's thoughts and the vertical axis represents B's thoughts. A white square on the graph represents a completely solvable puzzle for that x/y combination of thoughts, a grey square on the graph represents a partially solvable puzzle, and a black square represents an unsolvable puzzle.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-WhlMK3MXdlk/Wv3exT5xA5I/AAAAAAAAEhc/DZPERYBRsc0S5OdqpJI4z-gRAVmfSaR8gCLcBGAs/s1600/solvable_partial_unsolvable.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="369" data-original-width="621" height="237" src="https://1.bp.blogspot.com/-WhlMK3MXdlk/Wv3exT5xA5I/AAAAAAAAEhc/DZPERYBRsc0S5OdqpJI4z-gRAVmfSaR8gCLcBGAs/s400/solvable_partial_unsolvable.png" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>solvable, partially solvable, and unsolvable</i></div><div class="separator" style="clear: both; text-align: center;"><i>Isle of Dreams puzzles</i></div><br />This is really neat: the partially solvable and unsolvable combinations form an interesting pattern dispersed through the whitespace of the completely solvable puzzles. There are 16 "problem squares" of 4 puzzles that have a distinct symmetric pattern, and these 16 problem squares are arranged in 4 sets of 4 puzzles that also have an interesting symmetry.<br /><br />We'll zoom in on one of the "problem squares" to give a better picture of what the graph is displaying:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-E93QQ7495rE/Wv3hnWvDhpI/AAAAAAAAEho/EZ0zMwXJuXEWpGlPWh-wWF4ofW1AbzMiACLcBGAs/s1600/zoom_on_problem.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="616" data-original-width="654" height="375" src="https://2.bp.blogspot.com/-E93QQ7495rE/Wv3hnWvDhpI/AAAAAAAAEho/EZ0zMwXJuXEWpGlPWh-wWF4ofW1AbzMiACLcBGAs/s400/zoom_on_problem.png" width="400" /></a></div><br />Let's look at one of the contradictory puzzles - the one in the bottom left of this "problem square."<br /><br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="font-family: "arial"; font-size: 11pt; white-space: pre-wrap;">A is thinking #1: I am awake. The other is awake.</span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span id="docs-internal-guid-07c77f0e-6fbd-c05e-6c51-0dce1ce2751d"></span></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre;">B is thinking #5: I am asleep. The other is awake.</span></div><br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">From their first thoughts, we know that A is diurnal and B is nocturnal. If A is awake, they they will think true thoughts and consequently B is awake. If B is awake, they must be thinking false thoughts, requiring A to be asleep - a contradiction. On the other hand, if A is asleep, they will be thinking false thoughts, so B will be asleep. B will then be thinking true thoughts, requiring A to be awake, again a contradiction.</div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><br /></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">But why to these partial/contradictory puzzles form the patterns that they do? Maybe we will return again to the Isle of Dreams someday to find an answer.<br /><br /><i>Try the puzzles out here: <a href="https://dmackinnon1.github.io/inspectorCraig/dreamers.html">https://dmackinnon1.github.io/inspectorCraig/dreamers.html</a></i></div><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;"><br /></div><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/81KCWVRgmY0" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2018/05/the-isle-of-dreams.htmltag:blogger.com,1999:blog-5008879105295771159.post-30807986829181909042018-05-06T10:37:00.000-07:002018-05-06T10:37:33.681-07:00more bipartite art<div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-kO-VVkJEQz4/Wu8mB5TPEBI/AAAAAAAAEfQ/Kq4BFSJvN8IdH9cwUDPsRyzzUopNlNNIACLcBGAs/s1600/12_48.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="503" data-original-width="501" height="320" src="https://2.bp.blogspot.com/-kO-VVkJEQz4/Wu8mB5TPEBI/AAAAAAAAEfQ/Kq4BFSJvN8IdH9cwUDPsRyzzUopNlNNIACLcBGAs/s320/12_48.PNG" width="318" /></a></div><br />Playing around with some of the images created by <a href="http://www.mathrecreation.com/2018/01/bipartite-art.html">connecting two sets of dots</a>. In this case, every dot from the second set is connected to every dot in the first set, and the two sets are arranged in concentric circles. In the picture above, the first set of dots has 12 equally spaced dots in a circle, and the second set has 48, but the second set is arranged on a circle whose radius is much, much larger than the first, so the lines from the second set to the first come in from a great distance.<br /><br />If both sets have 3 dots, both sets are on concentric circles, and one of the sets is on a much larger circle, you might get something like this:<br /><br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-tf-R6hq9qAM/Wu8m5-mi8qI/AAAAAAAAEfY/Q0vcdMZaFAQomVkLwEiFYi4v4clJrDtXACLcBGAs/s1600/33.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="470" data-original-width="486" height="309" src="https://3.bp.blogspot.com/-tf-R6hq9qAM/Wu8m5-mi8qI/AAAAAAAAEfY/Q0vcdMZaFAQomVkLwEiFYi4v4clJrDtXACLcBGAs/s320/33.PNG" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: left;">The second set is so far out, that it looks like the lines from a point the second set are parallel. If the first set has 3 points and the second far-out set has 6 points, you might get something like this:</div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-E13MV-KPCqA/Wu8vZOVLIbI/AAAAAAAAEfo/zNfO54vY_KQc93o-vcl7rlumZXisCw5EQCLcBGAs/s1600/36.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="474" data-original-width="469" height="320" src="https://1.bp.blogspot.com/-E13MV-KPCqA/Wu8vZOVLIbI/AAAAAAAAEfo/zNfO54vY_KQc93o-vcl7rlumZXisCw5EQCLcBGAs/s320/36.PNG" width="316" /></a></div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: left;">Increasing size of the far-out set to 18 points:</div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-SijU-7JodOg/Wu8vsDSktsI/AAAAAAAAEfw/y6MlxGXDE8wSRT8S8ijbpAJZNPb97yVsgCLcBGAs/s1600/318.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="483" data-original-width="490" height="315" src="https://1.bp.blogspot.com/-SijU-7JodOg/Wu8vsDSktsI/AAAAAAAAEfw/y6MlxGXDE8wSRT8S8ijbpAJZNPb97yVsgCLcBGAs/s320/318.PNG" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: left;">Can you figure out the number of points in each set that would generate an image like this? You can test out your guesses <a href="https://dmackinnon1.github.io/bipartite2.html">here</a>.</div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-RCAEboGHv0c/Wu8x6D0DKBI/AAAAAAAAEf8/wULAJgeWGmkLs3zXOGH8L8Ir4PlJgYjxACLcBGAs/s1600/12_24.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="508" data-original-width="504" height="320" src="https://2.bp.blogspot.com/-RCAEboGHv0c/Wu8x6D0DKBI/AAAAAAAAEf8/wULAJgeWGmkLs3zXOGH8L8Ir4PlJgYjxACLcBGAs/s320/12_24.PNG" width="317" /></a></div><br /><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/T4o_k9FDYYg" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2018/05/more-bipartite-art.htmltag:blogger.com,1999:blog-5008879105295771159.post-27807974621106457022018-04-27T20:04:00.001-07:002018-04-27T20:04:45.331-07:00some Chessboard Puzzle solutionsIn the <a href="http://www.mathrecreation.com/2018/04/mathematical-chessboard-puzzles.html">previous post</a> I mentioned some <a href="https://dmackinnon1.github.io/chessdom/puzzles.html">mathematical chessboard puzzle puzzles</a>, created as part of working through the book <a href="https://press.princeton.edu/titles/7714.html">Across the Board</a>, by John J. Watkins. This post provides some possible solutions to the puzzles on that <a href="https://dmackinnon1.github.io/chessdom/puzzles.html">puzzle page</a>.<br /><br /><b>Queens on a 5 by 5 board</b><br /><br />The puzzle "<i>Place 3 queens on a 5x5 chessboard. The board must be dominated</i>," is asking you to find the <b>minimal dominating set</b> for queens on a 5x5 board (3 is the queen's domination number for 5x5 boards). Here are two solutions:<br /><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-yHWI-d-cxQ4/WuJAcTHxXbI/AAAAAAAAEb4/0A7LTMW_IjMAx3bPI9hRTJIbfhTwpIR1ACLcBGAs/s1600/3on5Q_dom.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="242" data-original-width="369" height="209" src="https://2.bp.blogspot.com/-yHWI-d-cxQ4/WuJAcTHxXbI/AAAAAAAAEb4/0A7LTMW_IjMAx3bPI9hRTJIbfhTwpIR1ACLcBGAs/s320/3on5Q_dom.png" width="320" /></a></div>The large dots show where the queens are placed, and a small dot appears on every square that is reachable by a queen. In the solution on the left, all three queens can be attacked, but in the solution on the right, the queen in the corner is uncovered.<br /><br />The puzzle "<i>Place 5 queens on a 5x5 chessboard. The board must be dominated. The pieces must be independent</i>," is asking you to find the <b>maximal independent set</b> for queens on a 5x5 board (5 is the queens independence number for 5x5 boards). Here's a solution:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-8MEGuNiIuuQ/WuJCHC7ZvbI/AAAAAAAAEcE/lDqJ8jccuW4IMkR7YKakfvP-lxCtVESvwCLcBGAs/s1600/5qon5_indep.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="237" data-original-width="189" src="https://3.bp.blogspot.com/-8MEGuNiIuuQ/WuJCHC7ZvbI/AAAAAAAAEcE/lDqJ8jccuW4IMkR7YKakfvP-lxCtVESvwCLcBGAs/s1600/5qon5_indep.png" /></a></div><br />There is also a puzzle that asks you to find an arrangement between the domination and independence numbers, "<i>Place 4 queens on a 5x5 chessboard. The board must be dominated. The pieces must be independent.</i>" Here is one solution for that:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-QDOdQQgqENg/WuJCzjdgqsI/AAAAAAAAEcM/Rdg9YVUNhbUV8By2jZJ7n3334rPxRmsWgCLcBGAs/s1600/4qon5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="173" data-original-width="175" src="https://1.bp.blogspot.com/-QDOdQQgqENg/WuJCzjdgqsI/AAAAAAAAEcM/Rdg9YVUNhbUV8By2jZJ7n3334rPxRmsWgCLcBGAs/s1600/4qon5.png" /></a></div><br /><div><br /></div><b>Queens on other boards</b><br /><br />On a 6x6 board, our queen puzzles will be bounded by the domination number of 3 and the independence number of 6. Here are solutions for those:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-3f4tpyvtFXA/WuJLgLh_PvI/AAAAAAAAEco/YQAqgiuJWG8NCkJn_QS5WnYoj2FfKEpvwCLcBGAs/s1600/3and6qon6_dand1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="269" data-original-width="427" src="https://1.bp.blogspot.com/-3f4tpyvtFXA/WuJLgLh_PvI/AAAAAAAAEco/YQAqgiuJWG8NCkJn_QS5WnYoj2FfKEpvwCLcBGAs/s1600/3and6qon6_dand1.png" /></a></div><br />In between these, we have "<i>Place 5 queens on a 6x6 chessboard. The board must be dominated. The pieces must be independent</i>;" here's a solution for that one:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-xWgpyGsXOTo/WuJMJe40RdI/AAAAAAAAEcw/WzFeuqBfUckjdryMcXJ0HaANT4tUntEDgCLcBGAs/s1600/5qon6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="211" data-original-width="209" src="https://1.bp.blogspot.com/-xWgpyGsXOTo/WuJMJe40RdI/AAAAAAAAEcw/WzFeuqBfUckjdryMcXJ0HaANT4tUntEDgCLcBGAs/s1600/5qon6.png" /></a></div><br /><div>Just to get a sense of what solutions to these might look like in general, let's jump up to 8x8. In this case, the domination number for queens is 5, so the puzzle in our set with the fewest queens on 8x8 is "<i>Place 5 queens on a 8x8 chessboard. The board must be dominated. The pieces must be independent</i>." Here is one solution:</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-XWWDqFjyEqE/WuJEStJFqBI/AAAAAAAAEcY/wLgYQsD9tz0WwZRZSCOeUd73HxFjLTfoQCLcBGAs/s1600/5qon8_dom.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="329" data-original-width="283" height="320" src="https://1.bp.blogspot.com/-XWWDqFjyEqE/WuJEStJFqBI/AAAAAAAAEcY/wLgYQsD9tz0WwZRZSCOeUd73HxFjLTfoQCLcBGAs/s320/5qon8_dom.png" width="275" /></a></div><div><br /></div><div>This particular solution is of interest because the pieces are in a pattern known as the Spencer-Cockayne construction, which can be used to find coverings of square boards of side length 9, 10, 11, and 12 as well. More interesting details can be found in <a href="https://press.princeton.edu/titles/7714.html">Across the Board</a>.</div><div><br /></div><div><b>Knights on a 5x5 board</b></div><div><br /></div><div>There are plenty of "independence and domination" problems for the knight on a 5x5 board, because the gap between the domination number (5) and the independence number (13) is so large (compared to queens on the 5x5, at least). Finding solutions for some of the intermediate numbers is a bit tricky, you may find. </div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-hzIr5CfaJT0/WuJPypRJQmI/AAAAAAAAEc8/-2YQW2w8xvUW8nOJPTzfMmrpEO9dknQngCLcBGAs/s1600/5and13knon5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="224" data-original-width="360" height="199" src="https://3.bp.blogspot.com/-hzIr5CfaJT0/WuJPypRJQmI/AAAAAAAAEc8/-2YQW2w8xvUW8nOJPTzfMmrpEO9dknQngCLcBGAs/s320/5and13knon5.png" width="320" /></a></div><div><br /></div><div>For example, here is a solution to "Place 9 knights on a 5x5 chessboard. The board must be dominated. The pieces must be independent":</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-F1rt9s5K31M/WuJQgrA-RfI/AAAAAAAAEdE/jEUh3LATBW0qs2eBmhJhDyvb7FKxMjzBgCLcBGAs/s1600/9kon5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="166" data-original-width="170" src="https://3.bp.blogspot.com/-F1rt9s5K31M/WuJQgrA-RfI/AAAAAAAAEdE/jEUh3LATBW0qs2eBmhJhDyvb7FKxMjzBgCLcBGAs/s1600/9kon5.png" /></a></div><div><br /></div><div><b>Knights on other boards</b></div><div><br /></div><div>All puzzles based on the maximum number of independent knights on a board have the same solution: put a knight on every square of the colour that has the most squares (on odd boards, one colour has more squares than the other). </div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/--pAItn3hric/WuJS1ykz_pI/AAAAAAAAEdQ/515O4Txd6wQCQgbybU01YPI2DJZOnY15gCLcBGAs/s1600/25knon7_ind.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="296" data-original-width="262" src="https://1.bp.blogspot.com/--pAItn3hric/WuJS1ykz_pI/AAAAAAAAEdQ/515O4Txd6wQCQgbybU01YPI2DJZOnY15gCLcBGAs/s1600/25knon7_ind.png" /></a></div><div><br /></div><div>Here is an example of a puzzle based on a "sub-optimal" dominating set that is also independent: "<i>Place 11 knights on a 6x6 chessboard. The board must be dominated. The pieces must be independent.</i>" And a solution:</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-PshzFsN-kMA/WuJUMogMXUI/AAAAAAAAEdc/Fal1umOxLlwXo5JhlW2RzDUC4nnBockdACLcBGAs/s1600/11knon6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="211" data-original-width="208" src="https://2.bp.blogspot.com/-PshzFsN-kMA/WuJUMogMXUI/AAAAAAAAEdc/Fal1umOxLlwXo5JhlW2RzDUC4nnBockdACLcBGAs/s1600/11knon6.png" /></a></div><div></div><div><br /></div><div><b>Bishops on 5x5</b></div><div><br /></div><div>Of the remaining pieces that we have puzzles for, bishops, kings, and rooks, the bishop is the most interesting, and the 5x5 board gives a good idea of how to construct the puzzle solutions.</div><div><br />Consider these two puzzles:<br /><br />"<i>Place 5 bishops on a 5x5 chessboard. The board must be dominated. The pieces must be independent.</i>"<br /><br />"<i>Place 8 bishops on a 5x5 chessboard. The board must be dominated. The pieces must be independent</i>."<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-ta_mG10Yhiw/WuPI5irbKHI/AAAAAAAAEeM/Tyx2MSG9Sa8b3OIY_r_TOwRvoHouhSZLQCLcBGAs/s1600/5and8_bon5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="239" data-original-width="367" height="208" src="https://1.bp.blogspot.com/-ta_mG10Yhiw/WuPI5irbKHI/AAAAAAAAEeM/Tyx2MSG9Sa8b3OIY_r_TOwRvoHouhSZLQCLcBGAs/s320/5and8_bon5.png" width="320" /></a></div><br />The minimum dominating set for bishops on a 5x5 board has 5 pieces, and the maximum independent set has 8. In between these, we can also form puzzles based on non optimal dominating sets (that are also independent), such as:<br /><br />"<i>Place 6 bishops on a 5x5 chessboard. The board must be dominated. The pieces must be independent</i>."<br /><div><br /></div><div>"<i>Place 7 bishops on a 5x5 chessboard. The board must be dominated. The pieces must be independent.</i>"</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-awSxKOR-pgs/WuPJmxSO9_I/AAAAAAAAEeU/EkaOLxew4AgJlWmmJEU7czvXCBIj8gxTQCLcBGAs/s1600/6and7bon5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="181" data-original-width="368" height="157" src="https://4.bp.blogspot.com/-awSxKOR-pgs/WuPJmxSO9_I/AAAAAAAAEeU/EkaOLxew4AgJlWmmJEU7czvXCBIj8gxTQCLcBGAs/s320/6and7bon5.png" width="320" /></a></div><br /></div><div>Solutions for finding similar solutions for bishops on boards of other sizes follow the same patterns as those on the 5x5 board.<br /><br />Hopefully, these examples will help you out if you get stuck on any of the puzzles. As mentioned earlier, if you are interested in learning more about the mathematics behind these puzzles, check out <a href="https://press.princeton.edu/titles/7714.html">Across the Board</a>.<br /><br /><br /><b>Related posts and pages</b><br /><i><a href="https://dmackinnon1.github.io/chessdom/puzzles.html">domination and independence puzzles</a> </i><br /><a href="http://www.mathrecreation.com/2018/04/mathematical-chessboard-puzzles.html"><i>post introducing chessboard puzzles</i></a><br /><a href="https://dmackinnon1.github.io/kixote/"><i>chess tour puzzles</i></a><br /><a href="http://www.mathrecreation.com/2017/01/build-your-own-knights-tour.html"><i>post on chess tour puzzles</i></a></div><div><br /></div><div><br /></div><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/lM5fHeAVfpE" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2018/04/some-chessboard-puzzle-solutions.htmltag:blogger.com,1999:blog-5008879105295771159.post-76755111987465260592018-04-24T13:58:00.001-07:002018-05-01T14:30:28.549-07:00Mathematical Chessboard Puzzles<a href="https://en.wikipedia.org/wiki/Chess_problem">Chess problems</a> are compositions where a set of pieces are arranged as if in a game and a specific goal is set - the problem is to determine how to get from the arrangement to the end goal. An interesting variation on the traditional chess problem are the <a href="https://en.wikipedia.org/wiki/Retrograde_analysis">retrograde analysis</a> chess problems of <a href="https://en.wikipedia.org/wiki/Raymond_Smullyan">Raymond Smullyan</a>, where instead of a goal being set, a question is asked about the conditions that may have lead to the arrangement (a backwards looking problem, rather than the traditional forwards looking type). <a href="https://en.wikipedia.org/wiki/Mathematical_chess_problem">Mathematical chessboard problems</a> are completely different than these traditional chess problems, and bear little connection to the actual game of chess - they are more concerned with the structure of how particular pieces can move on the board, and ask questions about how a single piece can move about the board, or about what positions are reachable by collections of the same type of piece. These problems are questions in <a href="https://en.wikipedia.org/wiki/Graph_theory">graph theory</a> in (thin) disguise, and have attracted the attention of both professional and recreational mathematicians.<br /><br />A useful and very readable guide to mathematical chessboard problems is <a href="https://press.princeton.edu/titles/7714.html">Across the Board</a>, by John J. Watkins. I’ve been playing around with <a href="http://www.mathrecreation.com/2016/12/life-lessons-from-knights-tour.html">knight</a> <a href="http://www.mathrecreation.com/2011/09/punctured-knights-tours.html">tours</a> for a <a href="http://www.mathrecreation.com/2017/01/build-your-own-knights-tour.html">few</a> <a href="http://www.mathrecreation.com/2011/03/knight-moves.html">years</a>, and since picking up this book a while back, I have been returning to it again and again to learn new and interesting things about them. Although I had heard about other mathematical chessboard problems, like the eight queens problem, <i>Across the Board </i>introduced me to the general category of chess independence and domination problems and encouraged me to learn more about them.<br /><br />A group of chess pieces of the same type is said to <b>dominate</b> a board if every square is either occupied or a neighbour (reachable in one move) of an occupied square. A group of chess pieces of the same type is said to be <b>independent</b> if no piece is a neighbour of any other piece. Domination (sometimes called covering) problems are, generally, to find a minimal dominating set, for example, the smallest number of queens required to dominate a board. Independence (or un-guarding) problems generally require you to find a maximal set of pieces that can be placed and remain independent; the greatest number of knights, for example, that can be placed so that no knight attacks another.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-u5GzYQhOqk4/Wt-PphqzGlI/AAAAAAAAEa8/UX-Sd3ur-tgHyRoMghTY_rP5M8JIATvhACLcBGAs/s1600/uninteresting.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="187" data-original-width="357" src="https://4.bp.blogspot.com/-u5GzYQhOqk4/Wt-PphqzGlI/AAAAAAAAEa8/UX-Sd3ur-tgHyRoMghTY_rP5M8JIATvhACLcBGAs/s1600/uninteresting.png" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>Uninteresting examples of dominating queens and independent knights.</i></div><div class="separator" style="clear: both; text-align: center;"><i></i></div><div class="separator" style="clear: both; text-align: center;"><i>A minimal dominating set and a maximal independent set would be more interesting</i></div><br />As part of working through <i>Across the Board</i> and understanding chess domination and independence, I tried to create an interactive ‘mathematical chessboard puzzle’ set (<a href="https://dmackinnon1.github.io/chessdom/puzzles.html">try it out here</a>). Here is a screenshot example: <br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-OKAuo0tgsnk/Wt-QZq3dSJI/AAAAAAAAEbE/lY4-XJIzLsEgqpGJdCUKyM7mD1W5IDkIACLcBGAs/s1600/puzzle_example.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="656" data-original-width="365" src="https://4.bp.blogspot.com/-OKAuo0tgsnk/Wt-QZq3dSJI/AAAAAAAAEbE/lY4-XJIzLsEgqpGJdCUKyM7mD1W5IDkIACLcBGAs/s1600/puzzle_example.png" /></a></div><div><div class="separator" style="clear: both; text-align: center;"><i>An example puzzle from the <a href="https://dmackinnon1.github.io/chessdom/puzzles.html">online set</a>.<br /> The solver is not off to a good start.</i></div><br />What is the difference between a mathematical chessboard <i>problem</i> and a mathematical chessboard <i>puzzle</i>? When considering the <i>problem</i> of queens independence, we would expect a serious treatment: a solution which finds the maximum number of independent queens for boards up to a certain size, an algorithm or method for generating maximal independent arrangements, and for some cases that remain unsolved by methods provided, some way of placing bounds on the independence number. A <i>puzzle</i> based on the idea of queens independence is a much simpler thing: merely an instruction like “Find a way to place 8 queens on an 8x8 board so that the board is dominated and the queens are independent.” <i>Across the Board</i> provides a great survey of results that mathematicians have used in tackling the problems of finding dominating sets, independent sets, and tours. The rest of this post is about puzzles (like the example above) that are generated from those results.<br /><br />In puzzles inspired by the problems of domination and independence, we want to ask the solver to come up with arrangements of pieces of a single type, constrained so that the pieces either dominate the board, are independent, or both. Recall that the domination problem is looking for a minimum number of pieces required to cover the board (either by placement or by attack), while the independence problem is looking for a maximum number of pieces that can be placed independently. For example, for queens on a 5x5 board, the domination number is 3, but the independence number is 5. So for queens on a 5x5 board, our puzzles will require placements of sets ranging from 3 to 5 queens.<br /><br />There is an asymmetry between domination and independence that we have to keep in mind: A solution to the domination problem might not be independent, but the maximal independent set will always be dominating. The example of 3 queens on the 5x5 board shows that you cannot always make your dominating set independent. On the other hand, a maximal independent set will always dominate: if the set does not dominate the board, that means there is a square that cannot be attacked by any of the current pieces - you can therefore add one more piece to the board at that spot, contradicting the fact that you already had a maximal independent set.<br /><br />For our puzzles, we’ll just consider boards from 4x4 to 8x8 (so that they fit reasonably on the screen). In the table below, the lowest number in each cell represents the domination number for that piece on the given board size, and the largest represents the independence number. The letters next to each number indicate whether the set of that size should be said to be independent (i) and/ or dominant (d) - some of this information is redundant, but all indicators are included for completeness. The numbers between the least and greatest represents other possible arrangements. For example, for queens on a 4x4 board, the domination number is 2 (dominant set is not independent in this case), and the independence number is 4, but it is possible to find a dominating independent set of size 3, giving us the entries 2d, 3di, and 4di. <br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-VQekwmjcPPU/Wt-S_b255rI/AAAAAAAAEbQ/cLB8KdBdQE4IzNwYzq0xl_Ix9PpuE2coQCLcBGAs/s1600/table_of_puzzles.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="531" data-original-width="375" src="https://4.bp.blogspot.com/-VQekwmjcPPU/Wt-S_b255rI/AAAAAAAAEbQ/cLB8KdBdQE4IzNwYzq0xl_Ix9PpuE2coQCLcBGAs/s1600/table_of_puzzles.png" /></a></div><br />The independence and domination numbers in the table above are from the results described in <i>Across</i> <i>the Board; </i>the values between were found looking at the solutions for either domination or independence and perturbing them slightly. For example, to fill in the values for queens on an 8x8 board, start with one of the solutions to the queens domination problem for 8x8, which consists of an arrangement of 5 pieces, and move one of the pieces to a reachable square with fewer neighbours, and fill in the gaps with additional pieces. Proceeding by trial and error, this leads to dominating independent sets of 6 and 7 pieces. Finding additional dominating and independent sets for knights is a little more challenging than others - there are some gaps in the table (maybe you can fill them). Most of these possible puzzles were written out in a format for displaying online, which you can view <a href="https://dmackinnon1.github.io/chessdom/data/puzzles.json">here</a>.<br /><br />If you interested in exploring the mathematical chessboard problems through the playful medium of chessboard puzzles, please give <a href="https://dmackinnon1.github.io/chessdom/puzzles.html">these a try</a>; if you are interested in learning more about the mathematics behind these puzzles, check out <a href="https://press.princeton.edu/titles/7714.html">Across the Board</a>.</div><i><br /></i><i>domination and independence puzzles: <a href="https://dmackinnon1.github.io/chessdom/puzzles.html">https://dmackinnon1.github.io/chessdom/puzzles.html</a></i><br /><i>chess tour puzzles: <a href="https://dmackinnon1.github.io/kixote/">https://dmackinnon1.github.io/kixote/</a></i><br /><br /><a href="http://www.mathrecreation.com/2018/04/some-chessboard-puzzle-solutions.html"><i>some puzzle solutions</i></a><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/xk45YJKks90" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2018/04/mathematical-chessboard-puzzles.htmltag:blogger.com,1999:blog-5008879105295771159.post-88468440591737582242018-03-07T09:15:00.000-08:002018-03-07T09:15:02.396-08:00Symmetry and Asymmetry in Tigers and TreasureTiger and treasure logic puzzles, like ones you can try out <a href="https://dmackinnon1.github.io/inspectorCraig/tiger.html">here</a>, offer you a choice between two doors that might lead to treasure, or a tiger. Statements on "door 1" are true only if they lead to treasure, and statements on "door 2" are true only if they lead to a tiger.<br /><br />The <a href="http://www.mathrecreation.com/2018/03/tigers-and-treasure.html">previous post</a> gave an overview of the different "tiger and treasure" logic puzzles that could be formed from a starting list of 14 statements:<br /><ol><li>this room has treasure</li><li>the other room has treasure</li><li>at least one room has treasure</li><li>both rooms have treasure</li><li>this room has a tiger</li><li>the other room has a tiger</li><li>at least one room has a tiger</li><li>both rooms have a tiger</li><li>this room has treasure or the other room has a tiger</li><li>the other room has treasure or this room has a tiger</li><li>this room has treasure and the other room has a tiger</li><li>the other room has treasure and this room has a tiger</li><li>both rooms have treasure or both rooms have a tiger</li><li>one room has treasure and the other has a tiger</li></ol>All possible puzzles are listed <a href="https://github.com/dmackinnon1/inspectorCraig/blob/master/report/tiger_report.csv">here</a> (statement numbers in the file start at 0, rather than 1).<br /><br />When exploring all the different possible puzzles we can make from these, we won't include puzzles that lead to a contradiction, or puzzles where the clues don't allow you to identify either door. This leaves 96 good puzzles out of the 196 combinations of statements, shown in black below:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Hckl0NN-IgU/Wp6ykQawDWI/AAAAAAAAEWw/-jo9VznwkHgoZ0BaaUjC2MC0Y43Y5Qp-wCLcBGAs/s1600/all_puzzles_nonSym.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="700" data-original-width="835" height="335" src="https://1.bp.blogspot.com/-Hckl0NN-IgU/Wp6ykQawDWI/AAAAAAAAEWw/-jo9VznwkHgoZ0BaaUjC2MC0Y43Y5Qp-wCLcBGAs/s400/all_puzzles_nonSym.png" width="400" /></a></div><h4><br /></h4><h4>Symmetry among Puzzles</h4>For each statement in the list of fourteen, you can find the negation of that statement in the list - for example, statement 1 "this room has treasure" has its negation in statement 5 "this room has a tiger." If we plot the list of statements on door 1 vs. the the list of statements on door 2, but re-arrange the statements on the door 2 axis so they are the negations of our original list (the negated list would be statements 5, 6, 8, 7, 1 ,2, 4, 3, 12, 11, 10, 9, 14, 13), we can see the symmetry in these puzzles more clearly:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-h2ye1fP6Qm4/Wp6z4CTsszI/AAAAAAAAEW8/B7JBHfgStvsH4b4jz4v-M3rcjVzlbGARACLcBGAs/s1600/symmetric_all_puzzles.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="695" data-original-width="835" height="331" src="https://4.bp.blogspot.com/-h2ye1fP6Qm4/Wp6z4CTsszI/AAAAAAAAEW8/B7JBHfgStvsH4b4jz4v-M3rcjVzlbGARACLcBGAs/s400/symmetric_all_puzzles.png" width="400" /></a></div><br />This graph is telling us that if we have a puzzle that works, then if we swap the signs on the doors and negate them, we will also get a working puzzle. If you explore this a bit further, you'll see that the symmetry goes deeper. Let's get a little mathy with this.<br /><br />If <i>a</i> and <i>b</i> are statements in our list, a puzzle <i>P</i> can be described by the ordered pair (<i>a</i>,<i>b</i>). Every puzzle <i>P</i> also has a solution, (<i>s</i>, <i>t</i>) where <i>s</i> and <i>t</i> are either "tiger", "treasure", or "unknown."<br /><br />For any statement in the list <i>x</i>, we can write the negation of <i>x</i> as <i>-x</i>. If we form a new puzzle by putting the negation of <i>a</i> on door 2 and the negation of <i>b</i> on door 1, we get a new puzzle <i>-P</i> = (<i>-b</i>,-<i>a</i>).<br /><br />The symmetry of our tiger treasure puzzles can be expressed as this little theorem:<br /><blockquote class="tr_bq">If <i>P</i> = (<i>a</i>,<i>b</i>) is a tiger treasure puzzle with solution (<i>s</i>,<i>t</i>), then its negation, <i>-P</i> = (<i>-b</i>, -<i>a</i>), will have the solution (<i>t</i>, <i>s</i>).</blockquote>Here is an example. Consider the example puzzle from the previous post.<br /><br /><b>Puzzle P</b><br />Door 1 says: Both rooms have a tiger. (statement 8)<br />Door 2 says: The other room has treasure and this room has a tiger. (statement 12)<br /><br />In the previous post, we worked out that door 1 has a tiger and door 2 has treasure.<br /><div><br /></div><div>Statement 8's negation is statement 3, and statement 12's negation is statement 9. So the puzzle -P looks like this:</div><div><br /></div><div><div><b>Puzzle -P</b></div><div>Door 1 says: This room has treasure or the other room has a tiger (statement 9) </div><div>Door 2 says: At least one room has treasure (statement 3)</div></div><div><br /></div><div>If you have tried out a few of these, you may be able to find the solution to -P, which is that door 1 has a tiger and door 2 has treasure, which is the reverse of Puzzle P, where door 1 had treasure and door 2 had the tiger - the contents behind the doors have switched.</div><div><br /></div><div>The symmetric graph above helped point us towards a nice symmetry that holds true for all of the tiger and treasure puzzles, but our original non-symmetric graph can point to another interesting things too.</div><h4><br /></h4><h4>Using asymmetry to make puzzles more interesting</h4><div>In Raymond Smullyan's book "The Lady or the Tiger?" he presented a nice twist on the usual presentation of this kind of puzzle:</div><div><blockquote class="tr_bq">"There are no signs above the doors!" exclaimed the prisoner. "Quite true," said the king. "The signs were just made, and I haven't had time to put them up yet." "Then how do you expect me to choose?" demanded the prisoner. "Well, here are the signs," replied the king. That's all well and good," said the prisoner anxiously, "but which sign goes on which door?" The king thought awhile. "I needn't tell you," he said. "You can solve this problem without that information."</blockquote></div><div>Let's look around for puzzles like this. One question to ask: Which of our problems would allow us to interchange the signs on the doors without affecting the solution to the problem? We'd like to know when does <i>P</i> = (<i>a</i>,<i>b</i>) give the same solution as <i>Q</i> = (<i>b</i>,<i>a</i>)? To explore which puzzles might work in this way, we can start looking at our first graph above, but limit our attention to those puzzles who's reflection in the line door1= door2 is also a puzzle. These are shown in black below (grey shows other puzzles whose reflection is not also a puzzle).</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-OrMJ28xV60U/Wp6-t8os_pI/AAAAAAAAEXM/JyT9cg2B4dk2yVmbHWzjQwTldAL5nLfawCLcBGAs/s1600/reflections.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="687" data-original-width="842" height="326" src="https://1.bp.blogspot.com/-OrMJ28xV60U/Wp6-t8os_pI/AAAAAAAAEXM/JyT9cg2B4dk2yVmbHWzjQwTldAL5nLfawCLcBGAs/s400/reflections.png" width="400" /></a></div><div><br /></div><div>But we don't just want puzzles whose reflection gives us a puzzle, but ones whose reflections have the same solution as the original. It turns out that this gives an uninspiring set of six puzzles:</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-BgzMoOIzwq8/Wp7YjpTL7UI/AAAAAAAAEXc/oWUqQ-GaAZUZao_ajG1PyqNwKAZ_dDQSwCLcBGAs/s1600/reflection_has_same_solution.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="711" data-original-width="765" height="371" src="https://1.bp.blogspot.com/-BgzMoOIzwq8/Wp7YjpTL7UI/AAAAAAAAEXc/oWUqQ-GaAZUZao_ajG1PyqNwKAZ_dDQSwCLcBGAs/s400/reflection_has_same_solution.png" width="400" /></a></div><div><br /></div><div>Only the trivial cases work: puzzles where the statements on the doors are exactly the same end up giving us puzzles that have exactly the same solution when the statements are interchanged. So what about the problem from "The Lady or the Tiger?", it uses these statements:</div><div><div><ul><li>this room contains a tiger (statement 5)</li><li>both rooms contain tigers (statement 8)</li></ul></div></div><div>Why does the solver not need to know which door each goes on? Well, if statement 5 goes on door 1 we get a contradiction, so it must go on door 2. This is why the solver does not need to be told how to label the doors: there is only one possible way to do so without getting a contradiction. So, a way to find more problems like this is to look for puzzles <i>P</i> = (<i>a</i>,<i>b</i>) where <i>P</i> is a legitimate puzzle, but <i>Q</i> = (<i>b</i>, <i>a</i>) is not a puzzle, as that labelling of the doors leads to a contradiction.</div><div><br /></div><div><br /></div><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-6wdODlvbLLw/Wp7apBa1_1I/AAAAAAAAEXs/8W7UK24x4Dc_s7DRHw5gM13y_it6HrwqwCLcBGAs/s1600/puzzles_reflect_no_puzzle.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="684" data-original-width="759" height="358" src="https://1.bp.blogspot.com/-6wdODlvbLLw/Wp7apBa1_1I/AAAAAAAAEXs/8W7UK24x4Dc_s7DRHw5gM13y_it6HrwqwCLcBGAs/s400/puzzles_reflect_no_puzzle.png" width="400" /></a></div><div><br /></div>There are 32 puzzles in this category (shown in black above): puzzles when you exchange the statements on the doors, you obtain a contradiction. Adding to this the 6 trivial cases where both doors have the same statement, we have 38 puzzles where we simply present the statements without explaining which statement is on each door.<br /><br />For example, the puzzle (13, 10) falls into this set.<br /><br />Let's try putting 13 on door 1 and 10 on door 2:<br /><br />door 1: both rooms have treasure or both rooms have a tiger (13)<br /><br />door 2: the other room has treasure or this room has a tiger (10)<br /><br />Because inscriptions on door 1 are only true of door 1 leads to treasure, statement 13 implies that door 2 must lead to treasure. Door 2 leading to treasure makes its statement (10) false, requiring door 1 to lead to a tiger.<br /><br />However, if we switch the statements, we run into trouble:<br /><br />door 1: the other room has treasure or this room has a tiger (10)<br /><div><br /></div>door 2: both rooms have treasure or both rooms have a tiger (13)<br /><br />If statement 10 on door 1 is false, then door 1 would lead to a tiger. However, the statement says that it leads to a tiger, so this cannot be. Door 1 must lead to treasure, making statement 10 true, requiring door 2 to also lead to a treasure. If door 2 leads to treasure, then its statement (13) must be false. However, statement 13 is true (both rooms have treasure), a contradiction.<br /><br />So, presented with statements 10 and 13, there is only one way to arrange them on the doors: put statement 13 on door 1 and statement 10 on door 2, leading to a tiger behind door 1 and treasure behind door 2.<br /><br />Please try out the tiger-treasure puzzles <a href="https://dmackinnon1.github.io/inspectorCraig/tiger.html">here</a> and ask yourself: "What would the negation of this puzzle (-P) be?" and "Is this one of the 38 puzzles that can be answered without being told which sign is on which door?"<br /><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/Ny9IQ6dd3u0" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2018/03/symmetry-and-asymmetry-in-tigers-and.htmltag:blogger.com,1999:blog-5008879105295771159.post-3272994985458835222018-03-02T20:16:00.001-08:002018-03-09T08:16:00.432-08:00Tigers and TreasureHere is yet another type of logic puzzle for you:<br /><blockquote class="tr_bq">Imagine there are two doors, both doors either lead to a tiger or treasure. You would like to know what each door leads to. On each door there is an inscription that provides a clue. If door 1 leads to treasure, its inscription is true, otherwise it is false. If door 2 leads to a tiger, its inscription is true, otherwise it is false. </blockquote><blockquote class="tr_bq">Door 1 says: Both rooms have a tiger.<br />Door 2 says: The other room has treasure and this room has a tiger. </blockquote><blockquote class="tr_bq">Can you figure out what each door leads to?</blockquote><br />Here is one way to think about it:<br /><br />Door 1 cannot lead to treasure, since if it does its inscription must be true. The inscription on door 1 contradicts the assumption that it leads to treasure. Consequently, door 1 must lead to a tiger. However, if door 1 leads to a tiger, its inscription must be false - which means the statement "both rooms have a tiger" cannot be true, so door 2 must lead to treasure. If door 2 leads to treasure, then its statement is false, which lines up with door 1 having a tiger and door 2 having a treasure. If we instead start with the inscription on door 2, if door 2 had a tiger, it would mean that door 1 has a treasure, but door 1 leading to treasure leads to a contradiction. It is safe to conclude that door 1 leads to a tiger, and door 2 leads to treasure.<br /><br />You can find 96 of these puzzles <a href="https://dmackinnon1.github.io/inspectorCraig/tiger.html">here</a>.<br /><br />These puzzles, <a href="https://dmackinnon1.github.io/knaves/">like</a> <a href="https://dmackinnon1.github.io/portia/">previous</a> <a href="https://dmackinnon1.github.io/inspectorCraig/">ones</a> are based on puzzles by Raymond Smullyan. In this post, I wanted to look at a reasonable list of statements that could appear on the doors, and how the statements interact with the peculiarities of the doors.<br /><br />To generate these puzzles, I started with a set of 14 statements that could be placed on either door:<br /><br /><ol><li>this room has treasure</li><li>the other room has treasure</li><li>at least one room has treasure</li><li>both rooms have treasure</li><li>this room has a tiger</li><li>the other room has a tiger</li><li>at least one room has a tiger</li><li>both rooms have a tiger</li><li>this room has treasure or the other room has a tiger</li><li>the other room has treasure or this room has a tiger</li><li>this room has treasure and the other room has a tiger</li><li>the other room has treasure and this room has a tiger</li><li>both rooms have treasure or both rooms have a tiger</li><li>one room has treasure and the other has a tiger</li></ol><br />If we stick with puzzles generated using these 14 statements, there are 196 possible labelling of door 1 and door 2. However, some statements will not work on a particular door. For example, door 2 cannot be labelled with statement 1, since if door 2's statements are only true if door 2 leads to a tiger, the statement "this room has treasure" will lead to a contradiction in every case. If door 2 has a tiger, then its statements are true, but "this room has treasure" would be false. If door 2 has treasure, then its statements are false, but "this room has treasure" would be true.<br /><br />The graph below shows all 196 possible puzzles. The puzzles that lead to contradictions are coloured as white squares, the puzzles that do not lead to contradictions are coloured in black. We can see a white strip across the bottom: these are all the puzzles where door 2 is labelled with statement 1. Can you find the statement that always leads to contradictions for door 1? There are 131 puzzles that are "good" in the sense that they do not lead to contradictions.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-rFDoyZJUltM/WpmFCsnHVdI/AAAAAAAAEVQ/L5DWkLBorOYUx6uUa1pE0nX25hY7YkE7QCLcBGAs/s1600/puzzles_with_solutions.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="692" data-original-width="781" height="353" src="https://2.bp.blogspot.com/-rFDoyZJUltM/WpmFCsnHVdI/AAAAAAAAEVQ/L5DWkLBorOYUx6uUa1pE0nX25hY7YkE7QCLcBGAs/s400/puzzles_with_solutions.png" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>treasure/tiger puzzles with solutions, <br />or an upside-down DigDug level</i></div><br />But some of these 131 puzzles are not so satisfying - the clues provided on the doors don't help in figuring out what lies beyond. In some cases, like the example puzzle above, the clues will tell you what lies beyond both doors. In others, you may only learn the contents of one door. For certain puzzles, you can conclude nothing. There are 35 puzzles, shown in black below, that are contradiction-free, but whose clues provide inconclusive information about the rooms.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-DtU4oruqbYk/WpmIW7vLXXI/AAAAAAAAEVg/Ks4QjZE9qE4gB0C1OUGRxdfqQEld7iGRgCLcBGAs/s1600/puzzles_leading_nowhere.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="692" data-original-width="779" height="353" src="https://3.bp.blogspot.com/-DtU4oruqbYk/WpmIW7vLXXI/AAAAAAAAEVg/Ks4QjZE9qE4gB0C1OUGRxdfqQEld7iGRgCLcBGAs/s400/puzzles_leading_nowhere.png" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>treasure/tiger puzzles where the inscriptions<br />tell you nothing</i></div><br />In the graph above, notice that many puzzles along the vertical stripe at statement 1 are in this category of puzzles that tell us nothing. When put on door 1, the statement "this room has treasure" is not helpful (except in some interactions with door 2 statements); taken on its own, if door 1 has treasure, the statement is simply true, and if door 1 does not have treasure, it is simply false - it does not tell us anything about door 2's possible contents, or generate a contradiction that would allow us to reject one of the options. Similarly, the horizontal stripe at statement 5 symmetrically corresponds to door 2 having the statement "this room has a tiger."<br /><br />So, to get a set of nice puzzles, we take the 131 that are contradiction-free, and remove these 35 unsatisfying puzzles to obtain 96 where you can find the contents of at least one of the rooms based on the inscriptions on the doors.<br /><br />Some of the puzzles are particularly nice: both rooms lead to treasure! There are 20 of these, shown in black below:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-8i6HZY14Xi0/WpmQRBUamaI/AAAAAAAAEVw/bJFXEu8NkRkg9QRs97W8eXB2UIsI-Z-LwCLcBGAs/s1600/puzzles_two_treasures.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="689" data-original-width="786" height="350" src="https://4.bp.blogspot.com/-8i6HZY14Xi0/WpmQRBUamaI/AAAAAAAAEVw/bJFXEu8NkRkg9QRs97W8eXB2UIsI-Z-LwCLcBGAs/s400/puzzles_two_treasures.png" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>treasure/tiger puzzles with two treasures</i></div><br />A quick look at this graph shows that when statement 11 is on door 2, or when statement 10 is on door 1, your odds of getting treasure are pretty good.<br /><br />Looking at statement 11:<br /><blockquote class="tr_bq"><i>this room has treasure and the other room has a tiger</i></blockquote>If seen on door 2, we know it cannot be true: statements on door 2 are only true if door 2 leads to a tiger. So this means two things: First door 2 must have treasure, and second, the statement is false. The only way for the statement to be false is if door 1 also leads to treasure.<br /><br />Looking at statement 10:<br /><blockquote class="tr_bq"><i>the other room has treasure or this room has a tiger</i></blockquote>If seen on door 1, this statement cannot be false: statements on door 1 are only false if door 1 leads to a tiger. If door 1 leads to a tiger, this would make the statement true - a contradiction. So this means two things: door 1 must lead to treasure, and the statement must be true. The only way for the overall statement to be true is if door 2 also leads to treasure.<br /><br />Statements 11 and 13 are, just like statements 1 and 3, negations of each other. <a href="https://en.wikipedia.org/wiki/De_Morgan%27s_laws">DeMorgan's laws</a>, tell us that an "and" statement like "this room has treasure and the other room a has a tiger" when negated becomes an "or" statement, like "the other room has a treasure or this room has a tiger."<br /><br />Just as there are puzzles that lead to 2 treasures, there are those that lead to two tigers. Not surprisingly, there are 20 of these also, and their graph looks like this:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-KfVSLY9gP6Q/WpoU7d-L6VI/AAAAAAAAEWA/rIBkrCBp3TMw29vwx-P5cWJ7lIqucGa9wCLcBGAs/s1600/two_tigers.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="693" data-original-width="778" height="356" src="https://1.bp.blogspot.com/-KfVSLY9gP6Q/WpoU7d-L6VI/AAAAAAAAEWA/rIBkrCBp3TMw29vwx-P5cWJ7lIqucGa9wCLcBGAs/s400/two_tigers.png" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>treasure/tiger puzzles with two tigers</i></div><div><br /></div>Can you see why statement 9 when put on door 2 leads to two tigers, and why the same is true for statement 12 when put on door 1?<br /><br />Although some puzzles end up being solvable with two tigers or two treasures, the classic form of the puzzle would have a solution where we would find a tiger behind one door, and treasure behind the other. It turns out there are 40 of these in our set, distributed like so:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-KA9wcay63o0/WpoeZRQMQXI/AAAAAAAAEWQ/Pxo431XMvEIkpIL-pXSBOgHV-547gNBYwCLcBGAs/s1600/one_of_each.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="698" data-original-width="754" height="370" src="https://3.bp.blogspot.com/-KA9wcay63o0/WpoeZRQMQXI/AAAAAAAAEWQ/Pxo431XMvEIkpIL-pXSBOgHV-547gNBYwCLcBGAs/s400/one_of_each.png" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>treasure/tiger puzzles where the <br />solution is one of each</i></div><br />Rounding out the puzzle collection are puzzles with one door that is unknowable. There are 16 of these, with 8 puzzles having a solution that is a tiger plus an unknown and 8 that is a treasure plus an unknown.<br /><br />So, out of the 196 combinations of our 14 statements on two doors, we have 131 that are contradiction free. Of these, we removed the 35 where the clues do not allow you to draw any conclusions about the rooms. This leaves:<br />- 16 puzzles that have a partial solution (8 where one door leads a tiger, and another 8 where one door leads to treasure);<br />- 40 puzzles that have one door leading to a tiger and one to treasure;<br />- 20 puzzles that have both doors leading to tigers; and<br />- 20 puzzles that have both doors leading to treasure.<br /><br />See how many you can solve: <a href="https://dmackinnon1.github.io/inspectorCraig/tiger.html">https://dmackinnon1.github.io/inspectorCraig/tiger.html</a><br /><br /><i><b>Update</b>: <a href="http://www.mathrecreation.com/2018/03/symmetry-and-asymmetry-in-tigers-and.html">Another post about tigers and treasure puzzles</a></i><br /><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/N-0ZRdd9xiQ" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2018/03/tigers-and-treasure.htmltag:blogger.com,1999:blog-5008879105295771159.post-23804545601628250712018-02-04T12:08:00.000-08:002018-02-04T12:08:25.358-08:00Inspector Craig, Logical DetectiveInspired by the puzzles of Raymond Smullyan, I've been playing with various puzzle types that he either invented or popularised. Earlier I posted some <a href="https://dmackinnon1.github.io/knaves/">knight and knave puzzles</a>, and a a page of puzzles inspired by his "<a href="https://dmackinnon1.github.io/portia/">Portia's Caskets</a>" puzzles, and now another has joined the pile: <a href="https://dmackinnon1.github.io/inspectorCraig/">The Case Files of Inspector Craig</a>.<br /><br />Here's an example of the kind of puzzles you will find on the page:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-K6WDKrSMSbI/WndiTbzMu4I/AAAAAAAAESs/V20aJlHtpPkl84pW8M3NoH5Ha4vuuYqyACLcBGAs/s1600/craig1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="277" data-original-width="451" height="245" src="https://4.bp.blogspot.com/-K6WDKrSMSbI/WndiTbzMu4I/AAAAAAAAESs/V20aJlHtpPkl84pW8M3NoH5Ha4vuuYqyACLcBGAs/s400/craig1.png" width="400" /></a></div><br />Your goal is to classify each suspect as either innocent, guilty, or unknown (in the case where the evidence cannot support either guilt or innocence).<br /><br />Depending on how familiar you are with <a href="https://en.wikipedia.org/wiki/List_of_logic_symbols">logical symbols</a>, it may help to simplify the language used to describe the clues - if we use the letter <b>X</b> to mean "X is guilty," we can express the statements above a bit more formally:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-Z-GSPrJLf1Q/WndjNu972AI/AAAAAAAAES0/NpX52BWlcGIzS3MuU8GBqhiSyUAdCB_5QCLcBGAs/s1600/craig2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="170" data-original-width="165" src="https://4.bp.blogspot.com/-Z-GSPrJLf1Q/WndjNu972AI/AAAAAAAAES0/NpX52BWlcGIzS3MuU8GBqhiSyUAdCB_5QCLcBGAs/s1600/craig2.png" /></a></div>There are two key techniques for solving these puzzles: 1) start with one of the statements, say <b>A</b>, and see if applying the propositions will lead to a contradiction; and 2) start with the statement "<b>A</b> or <b>B</b> or <b>C</b>" and work out the implications of each case - if there is a result that all three lead to, then that must be true.<br /><br />We can use the first method starting with <b>B</b>. If we assume <b>B</b> is guilty then since <b>B</b> always uses <b>A</b> as an accomplice (<b>B</b> <i>implies</i> <b>A</b>), <b>A</b> must be guilty. However we also have a statement that says that <b>A</b> never works with <b>B </b>(<b>A</b> <i>implies not</i> <b>B</b>), which means that <b>B</b> is innocent. Since assuming <b>B</b> is guilty ended up showing that <b>B</b> is innocent (<b>B</b> <i>implies not</i> <b>B</b>), then <b>B</b> must not have been guilty.<br /><br />Using the second method, we know that either <b>A</b> or <b>B</b> or <b>C</b> is guilty. We already know that <b>B</b> is innocent, so that leaves us with <b>A</b> and <b>C</b>. If <b>A</b> is guilty, we can't determine much else. However if <b>C</b> is guilty, then since <b>C</b> always uses <b>A</b> as an accomplice (<b>C</b> <i>implies</i> <b>A</b>), then <b>A</b> is also guilty. So, no matter which of the two alternatives we choose, <b>A</b> is guilty.<br /><br />Unfortunately, there is no way to know whether or not <b>C</b> is guilty based on this reasoning, so we are left to make this selection:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-v1fg7KOiQiM/WndlCcZvZjI/AAAAAAAAETA/xjZwxalLjyYao06VqU1V9Q4dMuWDqVVTACLcBGAs/s1600/craig3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="231" data-original-width="394" height="233" src="https://2.bp.blogspot.com/-v1fg7KOiQiM/WndlCcZvZjI/AAAAAAAAETA/xjZwxalLjyYao06VqU1V9Q4dMuWDqVVTACLcBGAs/s400/craig3.png" width="400" /></a></div><br />Which turns out to be correct.<br /><br />Try a few out here: <a href="https://dmackinnon1.github.io/inspectorCraig/">https://dmackinnon1.github.io/inspectorCraig/</a><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/GqHmpL0alNs" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2018/02/inspector-craig-logical-detective.htmltag:blogger.com,1999:blog-5008879105295771159.post-95258694562969712018-01-13T14:29:00.002-08:002018-01-13T14:29:25.872-08:00bipartite artA bipartite graph consists of two sets of nodes, N and M, where every node in N is connected to every node in M by an edge.<br /><br />If you set up the nodes N and M on a pair of circles centred around the same point, you can get quite a variety of nice looking diagrams. As part of playing around with generating svg images using d3js, I set up <a href="https://dmackinnon1.github.io/bipartite2.html">a page</a> that allows you to create some 'bipartite art.' Some of the diagrams turned out nicely, particularly when you hide the nodes completely:<br /><div class="separator" style="clear: both; text-align: center;"></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-YiVJLS6oJx4/Wk56GnKxpnI/AAAAAAAAEPY/nZZapjNK0g4Z08HvWJSjmB1UsZ3MDDL7ACLcBGAs/s1600/k88a.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="509" data-original-width="619" height="263" src="https://1.bp.blogspot.com/-YiVJLS6oJx4/Wk56GnKxpnI/AAAAAAAAEPY/nZZapjNK0g4Z08HvWJSjmB1UsZ3MDDL7ACLcBGAs/s320/k88a.png" width="320" /></a></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-wmy_MgwOUNo/Wk55_lJcNmI/AAAAAAAAEPQ/awTM0gl0QK4eBfgo1r5WJU9_HHgQ0W6PQCLcBGAs/s1600/k642a.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="485" data-original-width="528" height="293" src="https://1.bp.blogspot.com/-wmy_MgwOUNo/Wk55_lJcNmI/AAAAAAAAEPQ/awTM0gl0QK4eBfgo1r5WJU9_HHgQ0W6PQCLcBGAs/s320/k642a.png" width="320" /></a></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-ZKrDZNB3kfM/Wk56EMQ6pFI/AAAAAAAAEPU/HHQM8otqqogRWB2qAJJZhmg9LEPzKqRqwCLcBGAs/s1600/k2424b.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="502" data-original-width="495" height="320" src="https://4.bp.blogspot.com/-ZKrDZNB3kfM/Wk56EMQ6pFI/AAAAAAAAEPU/HHQM8otqqogRWB2qAJJZhmg9LEPzKqRqwCLcBGAs/s320/k2424b.png" width="315" /></a></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-lzzrYol9xg8/Wk56NBOSk0I/AAAAAAAAEPc/bP-SPOvEXtcOIfFjo0HdAaM3huHnoIK6QCLcBGAs/s1600/k2424a.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="502" data-original-width="546" height="293" src="https://4.bp.blogspot.com/-lzzrYol9xg8/Wk56NBOSk0I/AAAAAAAAEPc/bP-SPOvEXtcOIfFjo0HdAaM3huHnoIK6QCLcBGAs/s320/k2424a.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-L7zD5-2QwGA/Wk555yZv_0I/AAAAAAAAEPI/cD-UMKPpO1wWJi0lLBaO59QBvkL1YuWtwCLcBGAs/s1600/blackhole.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="555" data-original-width="556" height="319" src="https://1.bp.blogspot.com/-L7zD5-2QwGA/Wk555yZv_0I/AAAAAAAAEPI/cD-UMKPpO1wWJi0lLBaO59QBvkL1YuWtwCLcBGAs/s320/blackhole.png" width="320" /></a></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-Cd2KgIo8pII/Wk559i2ZX0I/AAAAAAAAEPM/N_lukAEAUKklh96eHSCnm_Z6OQWKz48awCLcBGAs/s1600/k4812.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="508" data-original-width="509" height="319" src="https://3.bp.blogspot.com/-Cd2KgIo8pII/Wk559i2ZX0I/AAAAAAAAEPM/N_lukAEAUKklh96eHSCnm_Z6OQWKz48awCLcBGAs/s320/k4812.png" width="320" /></a></div><br />Try it out at: <a href="https://dmackinnon1.github.io/bipartite2.html">https://dmackinnon1.github.io/bipartite2.html</a><br /><div><br /></div><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/kj6128OZDcU" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2018/01/bipartite-art.htmltag:blogger.com,1999:blog-5008879105295771159.post-23905300061342523172017-12-19T11:19:00.000-08:002017-12-29T06:00:25.254-08:00Hello Phyllotaxis<a href="https://en.wikipedia.org/wiki/Phyllotaxis">Phyllotaxis</a> spirals are a favorite of recreational math - often explored in connection to other perennial topics such as the golden mean and Fibonacci numbers.<br /><br />When I am trying out a new data visualization platform or programming language, I like to try to draw phyllotaxis spirals as a sort of "<a href="https://en.wikipedia.org/wiki/%22Hello,_World!%22_program">Hello World</a>." My latest "Hello Phyllotaxis" came about during the early stages of learning how to use <a href="http://d3js.org/">D3js</a>. You can try it out <a href="https://dmackinnon1.github.io/phylo2.html">here</a>. <br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-NG0HAqfjiQY/WjlIugGDFLI/AAAAAAAAENQ/8VJLyMBOoS4d5YKJKtm6dSXZeiyukomdQCLcBGAs/s1600/phyllo1.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="607" data-original-width="624" height="311" src="https://4.bp.blogspot.com/-NG0HAqfjiQY/WjlIugGDFLI/AAAAAAAAENQ/8VJLyMBOoS4d5YKJKtm6dSXZeiyukomdQCLcBGAs/s320/phyllo1.PNG" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>Sketched with D3js (see <a href="https://dmackinnon1.github.io/phylo2.html" style="text-align: start;">here</a>)</i></div><br /><a href="http://www.mathrecreation.com/2016/10/some-familiar-spirals-in-desmos.html">Here</a> is a "Hello Phyllotaxis" for Desmos (blog post <a href="http://www.mathrecreation.com/2016/10/some-familiar-spirals-in-desmos.html">here</a>). Over the years I have also pointed to phyllotaxis-like sketches using Fathom <a href="http://www.mathrecreation.com/2009/05/more-phyllotaxis.html">here</a>, Processing <a href="http://www.mathrecreation.com/2011/09/spirals.html">here</a>, and R <a href="http://www.mathrecreation.com/2015/08/simple-fun-with-r.html">here</a>.<br /><br />In the image above, the dark circles are chosen by skip-counting out from the center - in this case, skip counting by 11 (see #6 in <a href="http://www.mathrecreation.com/2012/08/a-deep-dive-into-multiplication-table.html">this post</a>).<br /><br />Below is a brief visual roundup of how this little "program" displays on the various platforms I have tried it on.<br /><br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-deBwZrHf8mw/SMf4iUHfUWI/AAAAAAAACg8/gDVh0TAD4-4Od-TWwyf4LFcofGrkyGhkQCPcBGAYYCw/s1600/fathom_phylo4.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="927" data-original-width="948" height="312" src="https://2.bp.blogspot.com/-deBwZrHf8mw/SMf4iUHfUWI/AAAAAAAACg8/gDVh0TAD4-4Od-TWwyf4LFcofGrkyGhkQCPcBGAYYCw/s320/fathom_phylo4.jpg" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>Sketched with Fathom (see<span style="text-align: start;"> </span><a href="http://www.mathrecreation.com/2009/05/more-phyllotaxis.html" style="text-align: start;">here</a>)</i></div><div class="separator" style="clear: both; text-align: center;"><br /></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-Txgad-BFxLM/T3Ub5K9NnMI/AAAAAAAACc8/h9OHFbMlee8X7QS0J1d3eo7yKNtzghCAQCPcBGAYYCw/s1600/mod17_2.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="405" data-original-width="397" height="320" src="https://2.bp.blogspot.com/-Txgad-BFxLM/T3Ub5K9NnMI/AAAAAAAACc8/h9OHFbMlee8X7QS0J1d3eo7yKNtzghCAQCPcBGAYYCw/s320/mod17_2.JPG" width="313" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>Sketched with Processing (see <a href="http://www.mathrecreation.com/2011/09/spirals.html">here</a>)</i></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-1qk_fTEl4go/VdzWP6XSyLI/AAAAAAAAC20/kfYisM9RqTUfJSev47BtriMCDP_yBosXgCPcBGAYYCw/s1600/exa2b.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="335" data-original-width="386" height="276" src="https://4.bp.blogspot.com/-1qk_fTEl4go/VdzWP6XSyLI/AAAAAAAAC20/kfYisM9RqTUfJSev47BtriMCDP_yBosXgCPcBGAYYCw/s320/exa2b.JPG" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>Sketched with R (see <a href="http://www.mathrecreation.com/2015/08/simple-fun-with-r.html" style="text-align: start;">here</a>)</i></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-uJCCFGeuDRc/V_2l8gHJ-bI/AAAAAAAADlY/Kg2JchW1XMw7nMcN4VB8q5M6QnxAhZvvwCPcBGAYYCw/s1600/spiral1.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="372" data-original-width="387" height="307" src="https://3.bp.blogspot.com/-uJCCFGeuDRc/V_2l8gHJ-bI/AAAAAAAADlY/Kg2JchW1XMw7nMcN4VB8q5M6QnxAhZvvwCPcBGAYYCw/s320/spiral1.PNG" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>Sketched with Desmos (see <a href="http://www.mathrecreation.com/2016/10/some-familiar-spirals-in-desmos.html" style="text-align: start;">here</a> and <a href="https://www.desmos.com/calculator/risuha09iw">here</a>)</i></div><br /><br /><br /><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/ra-Z9if0SSg" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/12/hello-phyllotaxis.htmltag:blogger.com,1999:blog-5008879105295771159.post-23700342637266504832017-12-07T19:39:00.002-08:002017-12-07T19:39:55.803-08:00Constructing Portia's CasketsIn Shakespeare's <i>The Merchant of Venice</i>, Portia tested her suitors by asking them to discover which of three caskets concealed her portrait. Inscriptions on the caskets presented riddles that would challenge the virtue of her potential mates. In his classic <i>What is the Name of this Book?</i> logician Raymond Smullyan, imagined several generations of clever Portias, who presented potential suitors with caskets inscribed with logic puzzles that provided the key to finding her hidden portrait.<br /><br />On <a href="https://dmackinnon1.github.io/portia/">this page</a> I have set up interactive puzzle generators that correspond (roughly) to Smullyan’s first three generations of Portias. In this post I thought I would describe what I find interesting about the way the puzzles are solved and how they are generated. The code that generates and presents these puzzles is found <a href="https://github.com/dmackinnon1/portia">here</a>.<br /><br />Here's the first Portia's Caskets puzzle in "What is the Name of this Book?":<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-J03MNu3OIiA/WimJreGSZiI/AAAAAAAAEKA/0rs36f1BGIowE2vIezfI8PTgEtiYSYOwgCLcBGAs/s1600/portia1.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="217" data-original-width="403" height="215" src="https://1.bp.blogspot.com/-J03MNu3OIiA/WimJreGSZiI/AAAAAAAAEKA/0rs36f1BGIowE2vIezfI8PTgEtiYSYOwgCLcBGAs/s400/portia1.PNG" width="400" /></a></div><br />One way to solve problems like this is to <b>work backwards</b>. For each casket, imagine that the portrait is concealed within that casket, then count how many statements would be true. When you find the portrait placement that matches the requirement that "at most one is true" you have your solution.<br /><br /><h3>Building our first 348 Portia Puzzles</h3>Working backwards also gives us a way to <b>generate</b> puzzles like this one. To generate these puzzles, consider all possible statements on the caskets. Each set of statements gives you three possible puzzles: a puzzle where the portrait is in the gold casket, a puzzle where the portrait is in the silver casket, and a puzzle where it is in the lead casket. To find out if any (or all) of these are valid solvable puzzles, check to see if the portrait placement gives you a 'truth count' that unique within that group of potential puzzles.<br /><br />But what about generating 'all possible statements'? What are the statements that can be included? The statements on the caskets can be thought of as pointers to caskets, pointers that are either positive ("the portrait is in the silver casket") or negative ("the portrait is not in the gold casket"), and that may be directed at the current casket itself ("the portrait is in this casket").<br /><br />For three caskets, this can be represented as an array of three integers. For example the statements for the puzzle above would be represented as [1, -2, -1], the 1 in the first position is saying that the first casket is pointing positively to itself ("the portrait is in this casket"). The -2 in the second position is saying that the second casket is pointing negatively to itself ("the portrait is not in this casket"), and the -1 in the third position is saying that the third casket is pointing negatively at the first casket ("the portrait is not in the gold casket"). We can analyse this puzzle using a chart like the one below:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-fauEF_QqVGs/WimONa4p42I/AAAAAAAAEKM/hdo1547BvbwAFOiDYN4rXSEGYaJvSNWDwCLcBGAs/s1600/truth_counts_portia1.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="192" data-original-width="628" height="121" src="https://3.bp.blogspot.com/-fauEF_QqVGs/WimONa4p42I/AAAAAAAAEKM/hdo1547BvbwAFOiDYN4rXSEGYaJvSNWDwCLcBGAs/s400/truth_counts_portia1.PNG" width="400" /></a></div><br />For the puzzle that says "there is at most one true statement," this means that the portrait is in casket 2 (silver), the only placement which gives at most one true statement. The chart also tells us that we cannot use this statement arrangement to make up other puzzles like "there are no true statements" or "there are exactly two true statements," as the other casket positions (p=1, p=3) both make two statements true.<br /><br />So, generating this sort of Portia Casket problem is easy: first generate all lists of length three (for the three caskets) made up of the values -1, -2, -3, 1, 2, 3 (for positive and negative statements about the three caskets). Each of these lists gives a family of three possible puzzles - one for the portrait being in each casket. Check each possible solution to see how many statements become true with that solution. Any solution that gives a truth count that is unique in that family corresponds to a valid puzzle.<br /><br />For three caskets, following this method of generating puzzles, we get a total of 348 puzzles. Some of these are trivially easy, as in the case where the clue is "all statements are true" and one of the caskets says "the portrait is in here."<br /><br />Smullyan's first Portia puzzle, puzzle 67a, corresponds to the puzzle with identifier <i>portia1-44 </i>in our Portia I generator. Smullyan presents another puzzle by the first generation of Portias, puzzle 67b. This puzzle has statements [-2, -2, 3], and corresponds to <i>portia1-271</i> in the Portia I generator.<br /><br />All the Portia I puzzles are listed in <a href="https://raw.githubusercontent.com/dmackinnon1/dmackinnon1.github.io/master/portia/data/portia1.json">this json file</a>. Here is an example of one from <a href="https://dmackinnon1.github.io/portia/">the page</a>:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-FCqmQhTdRRE/WimqRNAu4aI/AAAAAAAAEK8/Ow2GlOYIMhI8VRc8hmGvXFmfcyMai7SpwCLcBGAs/s1600/portia1-generated.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="326" data-original-width="552" height="235" src="https://1.bp.blogspot.com/-FCqmQhTdRRE/WimqRNAu4aI/AAAAAAAAEK8/Ow2GlOYIMhI8VRc8hmGvXFmfcyMai7SpwCLcBGAs/s400/portia1-generated.PNG" width="400" /></a></div><br />Hopefully, you can see that we would represent the statements as [-1, -2, 2] and that the solution to this puzzle would have to be casket 1.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-TVLoapx6k6M/Wimq37yHW6I/AAAAAAAAELE/cDVX8G7OWUAj6kkzIcWzCsJ3GLqM2XwVQCLcBGAs/s1600/portia1-generated-solved.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="372" data-original-width="549" height="270" src="https://3.bp.blogspot.com/-TVLoapx6k6M/Wimq37yHW6I/AAAAAAAAELE/cDVX8G7OWUAj6kkzIcWzCsJ3GLqM2XwVQCLcBGAs/s400/portia1-generated-solved.PNG" width="400" /></a></div><br /><h3>Finding 16152 more!</h3>In "What is the Name of this Book?" a second generation Portia makes more difficult puzzles by putting two statements on each casket. Our Portia II generator is based on Smullyan's puzzle 68b.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-3ZtEzVvfGyw/WimTTKorxZI/AAAAAAAAEKc/evwtJprqyYgGFMijZEbCnhsYBi9qxNoHgCLcBGAs/s1600/portia2.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="299" data-original-width="383" height="311" src="https://1.bp.blogspot.com/-3ZtEzVvfGyw/WimTTKorxZI/AAAAAAAAEKc/evwtJprqyYgGFMijZEbCnhsYBi9qxNoHgCLcBGAs/s400/portia2.PNG" width="400" /></a></div><br /><br />It seems clear that these puzzles are very similar to the Portia I puzzles except: (1) there are two lists of statements, and (2) instead of giving a total count of the true statements, we describe the distribution ("on one lid both statements are true, on another both statements were false, and on a third one statement was true and one false").<br /><br />If we model the statements as two lists of integers, such as [-1, -1, -3], [2 ,3, 1] for the above, and then for each pair of lists include puzzles where a portrait position generates a unique distribution, we can create puzzles like this one. It makes sense to exclude statement lists where the second set of statements is the same as the first, and to consider puzzles the same if we just exchange the first list of statements with the second list.<br /><br />Following this approach we get a large number (16152) of puzzles (all of them are <a href="https://raw.githubusercontent.com/dmackinnon1/dmackinnon1.github.io/master/portia/data/portia2.json">here</a>). These are generally quite a bit trickier to solve than Portia I puzzles, although the method for solving them is essentially the same. Puzzle 68b above corresponds to <i>portia2-6854, </i>although the Portia II algorithm we used swaps the first statement list for the second (it generates as [2 ,3, 1], [-1, -1, -3]).<br /><br />Here's an example of a generated puzzle:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-d5sqgaOX6mA/WimvJ2fxfGI/AAAAAAAAELQ/zsCzs5a4ugoOIlO2o2FIVwBaGnqzF-_MQCLcBGAs/s1600/portia2-generated.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="374" data-original-width="633" height="236" src="https://1.bp.blogspot.com/-d5sqgaOX6mA/WimvJ2fxfGI/AAAAAAAAELQ/zsCzs5a4ugoOIlO2o2FIVwBaGnqzF-_MQCLcBGAs/s400/portia2-generated.PNG" width="400" /></a></div><br />For this particular puzzle we don't have to work backwards, we can take a direct approach aided by the contradictory statements on casket 2: We know this must be the one casket with one true statement. Since the statements on casket 1 cannot both be true, we know that this must be the casket with no true statements. This implies that casket 3 is the casket with two true statements. One of the statements on casket 3 says the portrait is in casket 2... so that is where it must be.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-OoQk1etUVyU/WimxzLqifLI/AAAAAAAAELc/Q4pq4jS-ITEPKwbxtquM28QYjiLXFuvYACLcBGAs/s1600/portia2-generated-solution.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="412" data-original-width="626" height="262" src="https://3.bp.blogspot.com/-OoQk1etUVyU/WimxzLqifLI/AAAAAAAAELc/Q4pq4jS-ITEPKwbxtquM28QYjiLXFuvYACLcBGAs/s400/portia2-generated-solution.PNG" width="400" /></a></div><br /><h3>Bellini and Cellini give us 3600 more puzzles</h3>Instead of telling us how many of the caskets have true statements, or how true statements are distributed across the caskets, what if solving another riddle was the key to figuring out which statements are true and which are false?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-MghAC5MbZDE/WimiAhQzo2I/AAAAAAAAEKs/VRaSInk9xqwoD29LnO3s5Pbv3iAZdpXAwCLcBGAs/s1600/bellini_cellini.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="294" data-original-width="385" height="305" src="https://2.bp.blogspot.com/-MghAC5MbZDE/WimiAhQzo2I/AAAAAAAAEKs/VRaSInk9xqwoD29LnO3s5Pbv3iAZdpXAwCLcBGAs/s400/bellini_cellini.PNG" width="400" /></a></div><br />When attempting to generate "Bellini and Cellini" puzzles, I decided on an approach that does not quite match up with any of the puzzles in "What is the Name of this Book," but is a combination of Portia I, Portia II, and the "Knights and Knaves" puzzles that Smullyan describes in an earlier chapter (see <a href="http://www.mathrecreation.com/2017/11/the-island-of-knights-and-knaves.html">this post</a>).<br /><br />For Portia III, we imagine that the caskets have inscriptions similar to Portia I, but also have an extra inscription that says something about the provenance of the caskets. For example, casket 1 might have an inscription "casket 2 was made by Bellini." You might think "great, that means that whatever is written on casket 2 must be true." Well, that is correct only if casket 1 was also made by Bellini, if it was made by Cellini, then whatever is written on casket 2 is actually false.<br /><br />So, our Portia III algorithm is actually a set of Portia I statements with a "three-islander Knights and Knaves puzzle" layered on top of it. You can learn more about these <a href="http://www.mathrecreation.com/2017/11/the-island-of-knights-and-knaves.html">here</a>. For simplicity, a specific kind of "three islander" problem was chosen: the three caskets (islanders) point at each other using 2 "accusation/affirmations" and one "similarity/difference" statement. These are always (pretty easily) solvable. Maybe a future Portia puzzle generator will involve different varieties of Bellini & Cellini statements.<br /><br />All the Portia III puzzles that the current algorithm generates are listed in <a href="https://raw.githubusercontent.com/dmackinnon1/dmackinnon1.github.io/master/portia/data/portia3.json">this json file</a>. Let's try one:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-frL7ain6-bI/WimyUAMdPJI/AAAAAAAAELk/gakc2ScnMmkh-pXjPrBEWkBXKQkvF-uiACLcBGAs/s1600/portia3-generated.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="367" data-original-width="681" height="215" src="https://3.bp.blogspot.com/-frL7ain6-bI/WimyUAMdPJI/AAAAAAAAELk/gakc2ScnMmkh-pXjPrBEWkBXKQkvF-uiACLcBGAs/s400/portia3-generated.PNG" width="400" /></a></div><br /><br />Casket 2 includes the inscription "Fashioned by a different maker than 1." If casket 2 is made by Bellini, this means that casket 1 is made by Cellini, since we can trust casket 2 in this case. If on the other hand, casket 2 is made by Cellini, then we should disbelieve the statement, and conclude that casket 1 is made by the same maker (Cellini). Hence, regardless of who made casket 2, we know that casket 1 is made by Cellini, and its inscriptions will be false. Now casket 1 makes the (false) assertion that casket 3 is made by Cellini - so we know that actually casket 3 is made by Bellini and must contain only true inscriptions. Casket 3 says that the portrait is in casket 2, so we believe it:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-FIvlm_Niq_A/Wim0XCyqSBI/AAAAAAAAELw/N9vUfXuUdWkLImPR4zPxI33aYi7Sc7MNgCLcBGAs/s1600/portia3-generated-solution.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="432" data-original-width="675" height="255" src="https://3.bp.blogspot.com/-FIvlm_Niq_A/Wim0XCyqSBI/AAAAAAAAELw/N9vUfXuUdWkLImPR4zPxI33aYi7Sc7MNgCLcBGAs/s400/portia3-generated-solution.PNG" width="400" /></a></div><div class="separator" style="clear: both; text-align: left;"><br /></div>Working backwards is not the approach to take with Portia III: these puzzles require you to first solve the Bellini/Cellini riddle and figure out which caskets are stating the truth, and which are lying. Next you can use this information to follow the true (or false) statements to the portrait.<br /><br />When generating these puzzles, the method is to first generate all possible Portia I statements. For a given set of statements, each possible solution (casket 1, casket 2, or casket 3) makes each statement either true or false. To verify if the puzzle is solvable, we need to check whether the portrait can be discovered once the truth or falsehood of each statement is known. There is a simple rule for this: if <i>p</i> is the position of the portrait, then either we need a statement with value +/-p or we need a statement for each of the remaining caskets. An example of a puzzle that does not work would be [1, 1, 1] where <i>p</i> = 2. The three caskets would all be lying (they would all be saying the portrait was in casket 1), but there would not be enough information to tell us if the portrait was in casket 2 or 3. The same statement list, [1,1,1] is a valid puzzle if <i>p</i> = 1. Once we have a solvable puzzle, we can overlay a few different Bellini & Cellini riddles that would say which caskets are lying and which are stating truths.<br /><div><br /></div><div>So, all told, these three Portias have given us 20100 puzzles, enough to keep us busy for a while. I had a lot of fun digging into them, and I hope you have fun with them as well - please try them out: <a href="https://dmackinnon1.github.io/portia/">https://dmackinnon1.github.io/portia/</a> </div><div><br /></div><br /><div style="text-align: left;"><b>Portia:</b></div><i><div style="text-align: left;"><i>Thus hath the candle singed the moth.</i></div></i><i><div style="text-align: left;"><i>O, these deliberate fools! when they do choose,</i></div></i><i><div style="text-align: left;"><i>They have the wisdom by their wit to lose.</i> </div></i><div style="text-align: left;">- Act II, Scene VII, The Merchant of Venice </div><br /><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/2lb-9mNyNuQ" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/12/constructing-portias-caskets.htmltag:blogger.com,1999:blog-5008879105295771159.post-43190846723212202702017-11-18T06:16:00.000-08:002017-11-18T06:16:08.492-08:00the island of knights and knavesThere is classic type of logic problem where we are asked to imagine an island consisting of two types of people: those that always tell the truth (knights), and those that always tell lies (knaves). In puzzles based on this trope, the islanders make statements, and we have to figure out which islanders are knights and which islanders are knaves.<br /><br /><a href="https://dmackinnon1.github.io/knaves/">This page</a> will generate knight and knave puzzles of varying difficulty. Here’s an example: <br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-XA00rfKskEo/Wg9aOIQ-E2I/AAAAAAAAEIM/WJR3oXmagmU1DFBHr1uVqkZJGl6rELRwwCLcBGAs/s1600/easy4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="214" data-original-width="418" src="https://2.bp.blogspot.com/-XA00rfKskEo/Wg9aOIQ-E2I/AAAAAAAAEIM/WJR3oXmagmU1DFBHr1uVqkZJGl6rELRwwCLcBGAs/s1600/easy4.png" /></a></div><div style="text-align: center;"><i>An "easy" puzzle from https://dmackinnon1.github.io/knaves/</i> </div><br />The grandfather of all these puzzles is an actual islander who referenced an actual island - around 600 BCE, the Cretan <a href="https://en.wikipedia.org/wiki/Epimenides_paradox">Epimenides</a> is credited with the statement “All Cretans are liars.” The fun has not stopped since.<br /><br />The authoritative source for island puzzles is “What is the Name of this Book?” by <a href="https://en.wikipedia.org/wiki/Raymond_Smullyan">Raymond M. Smullyan</a>, which builds these seemingly simple puzzles from humble beginnings (knights and knaves alone on islands) to much more complicated ones that include normals (they sometimes lie, and sometimes tell the truth), the insane (they think lies are truths, and vice versa), monkeys, clubs of knights and knaves, vampires, werewolves and other characters. Using this motley crew, the book slyly leads us to a puzzle-based statement of Godel’s incompleteness theorem.<br /><br />We will stick to the first type of puzzles: knights and knaves alone on an island. How do we solve the puzzle above? Here's one way to reason it out:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-c0oVpQSbNLo/Wg9afBJdY3I/AAAAAAAAEIQ/86EDu9Y3lec4H8EsTygTFIkA-3o5Q1M9ACLcBGAs/s1600/easy4.solution.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="384" data-original-width="417" src="https://3.bp.blogspot.com/-c0oVpQSbNLo/Wg9afBJdY3I/AAAAAAAAEIQ/86EDu9Y3lec4H8EsTygTFIkA-3o5Q1M9ACLcBGAs/s1600/easy4.solution.png" /></a> </div><div class="separator" style="clear: both; text-align: center;"><i>A sample solution for a puzzle generated <br />at https://dmackinnon1.github.io/knaves/</i></div><br />The puzzle generation page mentioned above limits itself to knights and knaves making three kinds of statements:<br /><br /><b>Accusations and Affirmations</b><br />In an accusation, an islander A says something like "B is a knave" or an equivalent statement like "B always lies." In an affirmation, islander A says something like "B is a knight" or "B always tells the truth."<br /><br />Unfortunately, we don't know if A is telling the truth or not, so how can we know if what they are saying about B is true or not? Even without knowing the type of A, we can learn something very helpful about A and B from these statements. If A and B are linked by an accusation, they must be of different types: either A is a knave and B is a knight, or vice versa. If A and B are linked by an affirmation, they must be of the same type: either both are knights, or both are knaves. See if you can reason out why this must be so.<br /><br />One approach to use when solving puzzles that feature several accusations and affirmations is to draw a diagram (as described in an <a href="http://www.mathrecreation.com/2012/05/liar-truther-accusation-graphs.html">old post</a>).<br /><br /><b>Knave Conjunctions</b><br />An example of a knave conjunction, is when A says "B is a knight, or I am a knave," or "C is a knave and I am a knave."<br /><br />These are very helpful statements, as they always tell us the type of both the speaker and the spoken-of. Any islander who says "or I am a knave" will be making a statement that must be, overall, truthful and is therefore a knight, while any islander who says "and I am a knave" will by lying, and must be knave. Try and convince yourself of that.<br /><br />An interesting thing about "knave conjunctions" is that their usefulness comes from how close they are to the <a href="https://en.wikipedia.org/wiki/Liar_paradox">liar paradox</a>. The liar paradox is a more self-directed refinement of that original statement of Epimenides, where we imagine that someone says: "I am lying" and wonder if they are telling the truth or not.<br /><br />An islander cannot make the statement "I am lying," or any equivalent statement such as "I am a knave." If such a statement is true, then the speaker is lying, making the statement also false; and if it is false, the speaker is lying, making the statement also true. So such a statement is contradictory - neither false or true, and our islanders are restricted to statements that are either true or false.<br /><br />Islanders, however, can get close to generating the liar paradox by including its statement as a clause along with another statement. To see how they can do this, you have to be clear on how statements that include "and" and "or" work. If someone on the island says "X or Y" then only X or Y has to be true in order for the whole statement to be true. So a knight can say "X or Y" when only one of the statements is true. However, if a knave says "X or Y" then both X and Y must be false (if one was true, the whole statement would be true, and a knave cannot make a true statement). If an islander says "X and Y" then both X and Y have to be true in order for the statement to be true, and only one needs to be false for the statement to be false. So a knave can say "X and Y" when only one of the statements is false. <br /><br /><b>Similarity and Difference Statements</b><br />Sometimes an islander A might say "B is my type" or maybe "C is not my type." We might not know if A is a knight or knave, but we can infer the type of B and C right away. No matter whether A is lying or telling the truth, if A claims "B is my type," then B must be a knight. On the other hand, if A claims that "C is not my type" we know that C is a knave. Do you agree?<br /><br />It is interesting to compare these statements with our first type of statements, the "accusations/affirmations," these two types of statements are reciprocal in a way. When an islander directly says what type another islander is (an accusation or affirmation), all we learn is that the source and target of the statement are similar or different, without learning the actual type. However, when an islander makes a statement about similarity or difference, we learn exactly what type the target is, without learning if this is similar or different than the source.<br /><br />There are many more interesting things that islanders could say, but once you have reasoned out how these three kinds of statements work, you can beat any puzzle on the <a href="https://dmackinnon1.github.io/knaves/">page</a>.<br /><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/n7QWdxkKFE0" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/11/the-island-of-knights-and-knaves.htmltag:blogger.com,1999:blog-5008879105295771159.post-74584891434167282352017-11-10T12:14:00.001-08:002017-11-10T12:14:50.138-08:00trihexagonal & rhombille tilings<div class="separator" style="clear: both; text-align: center;"><img src="http://78.media.tumblr.com/6af5ec0ff617c1b6cb6f101c88745618/tumblr_oz2ypePiEm1r62rxco1_250.png" /></div><br />The image above is the superposition of two tessellations. The dark bold lines show a tiling of the plane that is made up of regular hexagons and triangles (the <a href="https://en.wikipedia.org/wiki/Trihexagonal_tiling">trihexagonal</a> tiling).<br /><br />The light lines show portions of the reciprocal (or dual) of the dark-lined tessellation.<br /><br />To create a reciprocal tessellation, for every two adjacent tiles in the original tessellation, join the centers of the two tiles by a line segment perpendicular to their shared side. This line segment becomes the edge of one of the tiles in the reciprocal tessellation.<br /><br />The reciprocal of trihexagonal tiling is made up entirely of rhombs, the <a href="https://en.wikipedia.org/wiki/Rhombille_tiling">rhombille </a>tiling.<img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/iU16cvoYa40" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/11/trihexagonal-rhombille-tilings.htmltag:blogger.com,1999:blog-5008879105295771159.post-46139406444665176502017-10-23T11:58:00.001-07:002017-10-25T10:05:42.610-07:00Diophantine DesmosIt may happen that you have a real valued function, but only want to find those points where both the input and output are integers.<br /><br />For example, consider<i> y = </i><b>sqrt</b>(<i>x</i>). Suppose you had a graph of <b>sqrt</b>(<i>x</i>) and wanted to show which values of <i>x</i> give an integer result for <i>y</i>, i.e. which values of <i>x</i> are perfect squares:<br /><br /><br /><div style="text-align: center;"><span id="docs-internal-guid-d6930ba2-49e2-dc66-e8f2-6b42c9787d3a"><span style="font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;"><img height="183" src="https://lh5.googleusercontent.com/4kZcU9oMs5hJOiQkdYTu_c3j3k2ofxVIj_iPE5HFOPBFK02u3lMveyRIs8cm6l_U9cMOFyWSDcPcfmHCXL2VvU9IwNW6Y0GM-56t6TmNaDLSCCKiqhVZsQGAFWII5VU18czzj_Eb" style="border: none; transform: rotate(0rad);" width="400" /></span></span></div><div style="text-align: center;"><i>y = <b>sqrt</b>(x) with only integer solutions shown</i></div><div style="text-align: left;"><i><br /></i></div><div style="text-align: left;"><div>I recently learned how you can find and display integer solutions for certain types of equations in <a href="https://www.desmos.com/">Desmos</a>, and thought I would write a post about how to do this. </div><div><br /></div><div>When we care only about the integer solutions of an equation, we refer to it as a <a href="https://en.wikipedia.org/wiki/Diophantine_equation">Diophantine equation</a>. In general, Diophantine equations can take many forms - the technique described here can be used in a limited class of problems where you can express your Diophantine equation as a function <i>k</i> = <i>f</i>(<i>n</i>), where <i>f </i>takes integers <i>n</i> as inputs and want to know which outputs <i>k</i> are also integers (<i>k</i> > 0).</div><div style="font-style: italic;"><br /></div></div><div style="text-align: left;"><b>step 1 - define your real valued function</b></div><div style="text-align: left;">Let's see how to apply this method using <b>sqrt</b>(<i>x</i>). First, plotting the real-valued <i>f</i>(<i>x</i>) = <b>sqrt</b>(<i>x</i>) function, and creating a list of points by evaluating it for a range of integers, shows there are many points on the graph where we put in an integer, and get out a non-integer.</div><div style="text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-OSPjUmrjcPg/We4QywIiTVI/AAAAAAAAEDk/OZhmzODgmK4aPQaiWZWeRrVMakJ1Gsb6wCLcBGAs/s1600/desmos_dia.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="267" data-original-width="547" height="195" src="https://4.bp.blogspot.com/-OSPjUmrjcPg/We4QywIiTVI/AAAAAAAAEDk/OZhmzODgmK4aPQaiWZWeRrVMakJ1Gsb6wCLcBGAs/s400/desmos_dia.PNG" width="400" /></a></div><div style="text-align: left;"><br /></div><div style="text-align: left;">What we do next is to use some of the functions built into Desmos to create an integer detector function, that we can apply to the outputs of <i>f</i>(<i>x</i>).</div><div style="text-align: left;"><br /></div><div style="text-align: left;"><b>step 2 - create the integer detector function</b></div><div style="text-align: left;">We'd like to build a function that can tell if a given input is an integer or not, and then use this to find out when we have an integer value for <i>f</i>(<i>n</i>). </div><div style="text-align: left;"><div><br /></div><div>We would like to create an <a href="https://en.wikipedia.org/wiki/Indicator_function">indicator</a> function for integers that behaves like this:</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-05vm3c510I0/We4eMdaG3pI/AAAAAAAAEEA/B0Jq4onzvskackS2oCwvD3AT9cZ1NGCuQCLcBGAs/s1600/indicator_function.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="94" data-original-width="289" height="104" src="https://2.bp.blogspot.com/-05vm3c510I0/We4eMdaG3pI/AAAAAAAAEEA/B0Jq4onzvskackS2oCwvD3AT9cZ1NGCuQCLcBGAs/s320/indicator_function.PNG" width="320" /></a></div><div><br /></div><div>To do this, we can make use of some built in functions in Desmos - the <b>ceiling </b>and <b>floor </b>functions. </div><div><br /></div><div>The function <b>ceil </b>rounds a decimal value up to the nearest integer, and <b>floor </b>rounds it down to the nearest integer. Consequently, <b>floor</b>(<i>x</i>) <= <b>ceil</b>(<i>x</i>), with equality only if <i>x</i> is an integer. Note also that for <i>x</i> > 0, <b>ceil</b>(<i>x</i>) != 0, and <b>floor</b>(<i>x</i>)/<b>ceil</b>(<i>x</i>) <= 1, with equality only if <i>x</i> is an integer. The function <b>floor</b>(<i>x</i>)/<b>ceil</b>(<i>x</i>) is almost what we want - it is equal to 1 only when <i>x</i> is an integer. To get a function that is zero when <i>x</i> is not an integer, we take the <b>floor </b>again:</div><div><br /></div></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-2VaPfVr6MIM/We4SMxMnmsI/AAAAAAAAEDw/WpiXB_di5SU3BvVklS0l83uZJSL0MJKCgCLcBGAs/s1600/integer_detector.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="76" data-original-width="231" src="https://2.bp.blogspot.com/-2VaPfVr6MIM/We4SMxMnmsI/AAAAAAAAEDw/WpiXB_di5SU3BvVklS0l83uZJSL0MJKCgCLcBGAs/s1600/integer_detector.PNG" /></a></div><div style="text-align: left;"><br /></div><div style="text-align: left;">By composing <i>t</i> and <i>f</i>, we obtain a function <i>tf </i>which tells us when the values of <i>f</i> are integers. Plotting <i>t</i>(<i>f</i>(<i>x</i>)) for a range of integer inputs shows us which values of <i>f</i> give integer results.</div><div style="text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-MibV5TKoEtU/We4gKPYK8XI/AAAAAAAAEEM/ONGDd6vrPqwNvY_OSe-56xWTucBvZolngCLcBGAs/s1600/integer_values.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="241" data-original-width="720" height="133" src="https://4.bp.blogspot.com/-MibV5TKoEtU/We4gKPYK8XI/AAAAAAAAEEM/ONGDd6vrPqwNvY_OSe-56xWTucBvZolngCLcBGAs/s400/integer_values.PNG" width="400" /></a></div><div style="text-align: left;"><div style="text-align: center;"><i>points in red show values for (x, tf(x)), ponts<br />in blue show values for (x, f(x)). </i></div></div><div style="text-align: left;"><br /></div><div style="text-align: left;">The final step is to integrate <i>tf</i> into our graph so that we can plot the integer solutions to <i>y</i>=<i>f</i>(<i>x</i>).</div><div style="text-align: left;"><br /></div><div style="text-align: left;"><b>step 3 - taking advantage of undefined</b></div><div style="text-align: left;">Desmos handles undefined points gracefully - it just will not plot them. Consequently, if we create a function <i>g</i>, which is identical to <i>f</i> where <i>f</i> takes on integer solutions, but is undefined when it does not, we can get Desmos to plot exactly the points we want and no others.<br /><br /></div><div style="text-align: left;"><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-I_HfyCW6Q4A/We5QjT0oDJI/AAAAAAAAEFU/Vhdpc6cPbmM3E-2gtBrtfNlH1wCjmuAmQCLcBGAs/s1600/new_function.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="91" data-original-width="371" src="https://4.bp.blogspot.com/-I_HfyCW6Q4A/We5QjT0oDJI/AAAAAAAAEFU/Vhdpc6cPbmM3E-2gtBrtfNlH1wCjmuAmQCLcBGAs/s1600/new_function.PNG" /></a></div><br />To create <i>g</i>, we can combine <i>f</i> with our indicator function <i>t</i>:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-tuWxdqO3A44/We4svwhpVpI/AAAAAAAAEEk/_T7jejq1LXo57Ypbm7Go9Fo3ipO0A7MtgCLcBGAs/s1600/new_function_def.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="72" data-original-width="268" src="https://3.bp.blogspot.com/-tuWxdqO3A44/We4svwhpVpI/AAAAAAAAEEk/_T7jejq1LXo57Ypbm7Go9Fo3ipO0A7MtgCLcBGAs/s1600/new_function_def.PNG" /></a></div><br />Plotting points using this new function shows only those which correspond to integer solutions for f(x).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-ELkfH61aCsY/We4t7k9dQbI/AAAAAAAAEEw/oln1g58Fi54xPKLTmQO_P-VbXi96jdAPACLcBGAs/s1600/sqr_root_int.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="260" data-original-width="622" height="166" src="https://2.bp.blogspot.com/-ELkfH61aCsY/We4t7k9dQbI/AAAAAAAAEEw/oln1g58Fi54xPKLTmQO_P-VbXi96jdAPACLcBGAs/s400/sqr_root_int.PNG" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>integer solutions to y = sqrt(x), graph <a href="https://www.desmos.com/calculator/h74wux47iy">here</a></i></div><br /><b><br /></b><b>Another example - Pythagorean triples</b><br />We encounter another example of Diophantine equations when trying to find <a href="https://en.wikipedia.org/wiki/Pythagorean_triple">Pythagorean triples</a>. A Pythagorean triple is an integer solution to the equation a^2 + b^2 = c^2.<br /><br />At first it might look like we can’t apply the method developed above to the problem of finding Pythagorean triples - there seem to be too many variables in play. However, we can explore the problem within certain ranges by taking advantage of other features that Desmos provides.<br /><div><br /></div>We can first define our function as a two variable function, and then use partial evaluation to obtain a new single variable function, parameterized by a slider <i>p</i>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-1lbN_lB42VE/We4wVrn6NeI/AAAAAAAAEE8/MF0e0rF8LioSr4JEf6r0mcdS-HKUVWKSQCLcBGAs/s1600/pythagorean_equation.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="216" data-original-width="341" height="202" src="https://3.bp.blogspot.com/-1lbN_lB42VE/We4wVrn6NeI/AAAAAAAAEE8/MF0e0rF8LioSr4JEf6r0mcdS-HKUVWKSQCLcBGAs/s320/pythagorean_equation.PNG" width="320" /></a></div><br />This allows us to explore Pythagorean triples where one of the legs of the triangle is fixed (determined by the value <i>p</i>). Using the method described above, we can find triples involving p as one of the legs.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-UvJe3_oK5fk/We4w5AhRkKI/AAAAAAAAEFE/46huMuMvRAAwk7MQ3lV7IlFqQQ8VdjcYwCLcBGAs/s1600/pythagorean_triples.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="433" data-original-width="543" height="318" src="https://2.bp.blogspot.com/-UvJe3_oK5fk/We4w5AhRkKI/AAAAAAAAEFE/46huMuMvRAAwk7MQ3lV7IlFqQQ8VdjcYwCLcBGAs/s400/pythagorean_triples.PNG" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>some triples found by Desmos, </i></div><div class="separator" style="clear: both; text-align: center;"><i>where p=24 (graph <a href="https://www.desmos.com/calculator/x2qa0cwggj">here</a>)</i></div><br />For example, with <i>p</i> = 24, Desmos finds the triples (24, 7, 25), (24, 18, 30), and others shown in the image above.<br /><br /><br /><br /><i>Some older Desmos-related posts:</i><br /><i>- <a href="http://www.mathrecreation.com/2016/10/brain-and-propeller-fractals-using.html">Brain and Propeller Fractals in Desmos</a></i><br /><i>- <a href="http://www.mathrecreation.com/2016/11/desmos-polygonal-number-diagrams.html">Polygonal Number Diagrams using Desmos</a></i><br /><i>- <a href="http://www.mathrecreation.com/2016/10/some-familiar-spirals-in-desmos.html">Spirals in Desmos</a></i><br /><i>- <a href="http://www.mathrecreation.com/2016/10/more-familiar-spirals-in-desmos.html">Spirolaterals in Desmos</a></i><br /><br /><br /></div><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/9W8F9KZQpJY" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/10/diophantine-desmos.htmltag:blogger.com,1999:blog-5008879105295771159.post-71616816460531819372017-10-03T18:53:00.000-07:002017-10-04T19:27:03.658-07:00a Truchet puzzle mysteryI thought it would be fun to create a page of Truchet puzzles, and while doing this I noticed something that surprised me: even though they were randomly generated, all puzzles of the same size had the exact same level of complexity.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-g-YTGPWHoQQ/WdL_Wp57EgI/AAAAAAAAEAI/O3xbSM1o3AAmWNML4nL9rL1CRCLXkmIDwCLcBGAs/s1600/solitary_tile.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="147" data-original-width="149" src="https://3.bp.blogspot.com/-g-YTGPWHoQQ/WdL_Wp57EgI/AAAAAAAAEAI/O3xbSM1o3AAmWNML4nL9rL1CRCLXkmIDwCLcBGAs/s1600/solitary_tile.png" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>a single puzzle piece<br />that can be rotated into 4 positions</i></div><br />In these puzzles, Truchet tiles like the one above are used to create a specific pattern. All the pieces are the same - it is just a question of rotating them correctly to make the pattern you are aiming for.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-H7qnk69Hvw0/WdMADxMwStI/AAAAAAAAEAQ/QFLHJHGFBIgTVRXf75IW0SgT-mHV4BQSgCLcBGAs/s1600/truchet2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="244" data-original-width="244" src="https://3.bp.blogspot.com/-H7qnk69Hvw0/WdMADxMwStI/AAAAAAAAEAQ/QFLHJHGFBIgTVRXf75IW0SgT-mHV4BQSgCLcBGAs/s1600/truchet2.png" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>a Truchet puzzle: can you make this pattern<br />using only Truchet tiles?</i></div><br />We can make these Truchet puzzles a bit more interesting if we have a specific starting arrangement, and add the restriction of using the smallest number of moves (clockwise rotations of individual tiles) to get from the starting arrangement to the target arrangement.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-CGJ16AlEZIc/WdMBEpQF8-I/AAAAAAAAEAY/eu5cRFOI2p4-5QQANkoQ40OvKk0t-rewgCLcBGAs/s1600/uniform_to_symmetric1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="212" data-original-width="508" height="166" src="https://4.bp.blogspot.com/-CGJ16AlEZIc/WdMBEpQF8-I/AAAAAAAAEAY/eu5cRFOI2p4-5QQANkoQ40OvKk0t-rewgCLcBGAs/s400/uniform_to_symmetric1.png" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>how many clockwise rotations of tiles will it take to transform<br />the square on the left to the one on the right?</i></div><br />On <a href="https://dmackinnon1.github.io/truchet/match.html">this page</a>, you can try out some puzzles like this. Because you are only allowed to rotate pieces clockwise, you may have to rotate a given tile 0, 1, 2 or 3 times in order to get it into the desired position.<br /><br />Please give it a try: <a href="https://dmackinnon1.github.io/truchet/match.html">https://dmackinnon1.github.io/truchet/match.html</a><br /><br />When setting up this puzzle page, I used a restricted set of arrangements for both the starting and target arrangements. For the starting arrangement, I have all the Truchet tiles in the same position. Let's call this type of arrangement a <b>uniform </b>Truchet square. There will be 4 different uniform Truchet squares of a given size; here is one for <i>n</i> = 6:<br /><div class="separator" style="clear: both; text-align: center;"></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-lP0GKzsPXXc/WdMB3cmH-mI/AAAAAAAAEAg/XOtI24NHs-ExwIgFMuUbvmCTwZw_oD4LACLcBGAs/s1600/uniform_square.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="248" data-original-width="246" src="https://1.bp.blogspot.com/-lP0GKzsPXXc/WdMB3cmH-mI/AAAAAAAAEAg/XOtI24NHs-ExwIgFMuUbvmCTwZw_oD4LACLcBGAs/s1600/uniform_square.png" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>a <b>uniform Truchet square</b>: all tiles <br />are in the same position</i></div><br />Because I like the way they look, I chose the target arrangements to always have <b>4-fold rotational symmetry</b>. An important choice as it turns out. These Truchet squares have sides of even length, and can be divided up into 4 quadrants - as we move around the quadrants in a clockwise direction, the pattern in each quadrant is a 90 degree rotation of the pattern in the preceding quadrant.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-YkCDm_ye6Mc/WdMDs6za5_I/AAAAAAAAEAw/9ktls5NxCMAD44XPzJppyGtRAkdM8CpFwCLcBGAs/s1600/4foldRotationalSymmetry.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="294" data-original-width="586" height="160" src="https://3.bp.blogspot.com/-YkCDm_ye6Mc/WdMDs6za5_I/AAAAAAAAEAw/9ktls5NxCMAD44XPzJppyGtRAkdM8CpFwCLcBGAs/s320/4foldRotationalSymmetry.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>you can make Truchet squares with 4-fold rotational<br />symmetry - they tend to look nice.</i></div><br />With these restrictions, I found that:<br /><ul><li>All 2x2 puzzles are solvable in 6 moves.</li><li>All 4x4 puzzles are solvable in 24 moves.</li><li>All 6x6 puzzles are solvable in 54 moves.</li></ul><div>Mysteriously, no matter what pattern was chosen for the target, all puzzles of the same size required the same number of moves to solve. </div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-d1i77VdA8cE/WdMFv7ilsQI/AAAAAAAAEA8/CoYj_fNBTMM6NG_yPxTcESXZqLh-C5cYwCLcBGAs/s1600/54moves_always.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="525" data-original-width="660" height="317" src="https://2.bp.blogspot.com/-d1i77VdA8cE/WdMFv7ilsQI/AAAAAAAAEA8/CoYj_fNBTMM6NG_yPxTcESXZqLh-C5cYwCLcBGAs/s400/54moves_always.png" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>symmetric puzzles of the same size always <br />have the same number of required moves</i></div><br />In general, it turns out that for any Truchet square <b>T</b> with side length <i>n</i> and 4-fold rotational symmetry, <b>T</b> will always be 6*(n/2)^2 rotations away from any uniform Truchet square.<br /><br />This was more puzzling than the original puzzles: how could my randomly generated puzzles all require the same number of moves to solve?<br /><br />To understand why this is the case, we can find a way to count all the rotations required to transform a uniform Truchet square into one that has four-fold rotational symmetry, and see that this does not depend on a particular choice of either the starting arrangement or the target. This turns out to be easier than you might expect.<br /><blockquote class="tr_bq">Let <b>U</b> be a uniform Truchet square of side length <i>n</i>, and <b>T</b> be a Truchet square with 4-fold rotational symmetry, also of side length <i>n</i>. We'll count how many rotations it takes to transform <b>U</b> into <b>T</b>. </blockquote><blockquote class="tr_bq">Let <i>t1</i> be a tile in the first quadrant of <b>U</b>. If we consider its image under rotation into the other quadrants, we have a set of 4 tiles, <i>t1, t2, t3</i>, and <i>t4</i>. One of these will be aligned with the corresponding tile in <b>T</b> (since the tiles in <b>T</b> that lie in the same positions as <i>t1</i>, <i>t2</i>, <i>t3</i>, and <i>t4</i> are rotated through all 4 positions, while the tiles of <b>U</b> are all in the same position). It will require 0 moves for this tile be put into the same position as the corresponding tile of <b>T</b>. As we move around the quadrants to the other images of our selected tile, they will all be in the same position (<b>U</b> is uniform), but the corresponding tiles of <b>T</b> will be rotated. The corresponding tiles of <b>T</b> will be 1, 2, and 3 rotations ahead from the tiles of <b>U</b>. So each tile in the first quadrant will, along with its images under rotation, contribute 0+1+2+3 = 6 rotations to the overall number of rotations required to transform <b>U</b> into <b>T</b>. There are (n/2)^2 tiles in the first quadrant, hence the total number of rotations required to transform <b>U</b> into <b>T</b> will be 6*(n/2)^2.</blockquote><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Ih3qyuPhJ5A/WdPbj5sbw1I/AAAAAAAAEBM/stT227wH_xwZ8RqVWgzgcQTDXeW2pQpwQCLcBGAs/s1600/uniform_to_rotational.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="126" data-original-width="223" src="https://1.bp.blogspot.com/-Ih3qyuPhJ5A/WdPbj5sbw1I/AAAAAAAAEBM/stT227wH_xwZ8RqVWgzgcQTDXeW2pQpwQCLcBGAs/s1600/uniform_to_rotational.PNG" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>for a given n, it always takes the same number of moves<br /> to transform a uniform Truchet square <b>U</b> into another</i></div><div class="separator" style="clear: both; text-align: center;"><i>one, <b>T</b>, if <b>T</b> has 4-fold rotational symmetry</i></div><br />The reason for all the puzzles requiring the same number of moves is the 4-fold symmetry of the target (and the uniformity of the starting arrangement). If we allowed non-symmetrical target arrangements, or varied the starting arrangements used, the number of rotations required to transform our starting arrangement into the target arrangement could lie anywhere between 0 and 3n^2.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-f3RhlKc8HNY/WdQ-D8RDlYI/AAAAAAAAEBs/oSpcusKQtSchQ1ry_CBPZlq5mKLhuMyxwCLcBGAs/s1600/truchet.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="369" data-original-width="365" height="320" src="https://4.bp.blogspot.com/-f3RhlKc8HNY/WdQ-D8RDlYI/AAAAAAAAEBs/oSpcusKQtSchQ1ry_CBPZlq5mKLhuMyxwCLcBGAs/s320/truchet.PNG" width="316" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>a 24 x 24 Truchet square with 4-fold rotational<br />symmetry - starting from a uniform square, how <br />many moves would be required to re-create it? </i></div><br />Why do the Truchet squares with rotational symmetry seem particularly nice? The human brain loves symmetry, but in the case of Truchet squares, it seems particularly appropriate to be drawn to arrangements like these. Individual Truchet tiles lack rotational symmetry - this lack of symmetry is what gives them their expressive power. By arranging them into a square pattern that does have rotational symmetry, we are overcoming the asymmetry of the original tile, appealing maybe to our need to <a href="https://en.wikipedia.org/wiki/Unity_of_opposites">unify opposites</a>, or to express a sense of <a href="https://en.wikipedia.org/wiki/Dialectic">dialectical tension</a>.<br /><br /><i>Some earlier posts on Truchet tiles:</i><br /><a href="http://www.mathrecreation.com/2017/04/truchet-en-plus.html"><i>truchet en plus</i></a><br /><a href="http://www.mathrecreation.com/2017/03/truchet-tiles.html"><i>truchet tiles</i></a><br /><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/ZbtjU54rqJY" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/10/a-truchet-puzzle-mystery.htmltag:blogger.com,1999:blog-5008879105295771159.post-52318613255243781392017-09-15T11:28:00.002-07:002017-09-15T11:28:47.960-07:00a polynomial division calculatorMany visitors to this blog come to see the posts about dividing polynomials using the grid method (like <a href="http://www.mathrecreation.com/2009/03/dividing-polynomials-grid-method.html">this one</a>). A <a href="http://www.mathrecreation.com/2016/11/polynomial-grid-division-examples.html">while ago</a>, I put up a page which generates examples that (hopefully) illustrate this method.<br /><br />Well, I am excited to say that the <a href="https://dmackinnon1.github.io/polygrid/">examples page</a> has been enhanced with the addition of a simple <a href="https://dmackinnon1.github.io/polygrid/calc.html">calculator</a>, which allows you to provide your own polynomials for dividing.<br /><br />This is not a sophisticated calculator - the polynomials you provide need to be in expanded form, and they have to be single variable polynomials using "x" for the variable - don't try to be fancy or tricky, please.<br /><br />For example, you may want to try something like this:<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-xEkob_35SW0/WbwS6P2MbYI/AAAAAAAAD9w/FWo5fdnR25kAh4I-sfhX9c63SejMpcyWgCLcBGAs/s1600/input_poly.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="104" data-original-width="378" src="https://2.bp.blogspot.com/-xEkob_35SW0/WbwS6P2MbYI/AAAAAAAAD9w/FWo5fdnR25kAh4I-sfhX9c63SejMpcyWgCLcBGAs/s1600/input_poly.PNG" /></a></div>After you provide your polynomials, hitting the <b>calculate </b>button will trigger the parser, that will let you know of any errors. If all goes well, you are prompted to have the calculator show the answer:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-WUQSaTnkZYU/WbwTv7Qtq_I/AAAAAAAAD94/lPHUDK4YzBk_wno8BuCLTvxZYl_FRckvgCLcBGAs/s1600/input_poly_intermediat.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="163" data-original-width="365" src="https://2.bp.blogspot.com/-WUQSaTnkZYU/WbwTv7Qtq_I/AAAAAAAAD94/lPHUDK4YzBk_wno8BuCLTvxZYl_FRckvgCLcBGAs/s1600/input_poly_intermediat.PNG" /></a></div>If you click the <b>Show Answer</b> button, the answer and the grid used for division is shown.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-gUEUBB4fhS0/WbwUK8wV5sI/AAAAAAAAD98/D-VcY3_x9m46CusBwPWbovmG3xIeK2ZngCLcBGAs/s1600/poly_answer.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="422" data-original-width="338" src="https://1.bp.blogspot.com/-gUEUBB4fhS0/WbwUK8wV5sI/AAAAAAAAD98/D-VcY3_x9m46CusBwPWbovmG3xIeK2ZngCLcBGAs/s1600/poly_answer.PNG" /></a></div><br />Finally, clicking on the <b>Show Additional Steps</b> button will walk you through how the grid was filled in to obtain the answer.<br /><br />I hope that this page turns out to be helpful. Please let me know of any issues you run into when using it.<br /><b><br /></b><b>Grid Division Calculator: <a href="https://dmackinnon1.github.io/polygrid/calc.html">dmackinnon1.github.io/polygrid/calc.html</a></b><br /><b><br /></b><b>Grid Division Example Generator: <a href="https://dmackinnon1.github.io/polygrid">dmackinnon1.github.io/polygrid</a></b><br /><br /><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/krACi-Mbtf0" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/09/a-polynomial-division-calculator.htmltag:blogger.com,1999:blog-5008879105295771159.post-41521063037078732992017-07-17T19:45:00.002-07:002017-07-17T19:45:32.780-07:00interactive chladni figure pageA while back there were <a href="http://www.mathrecreation.com/2016/06/chlandi-esque-figures-in-r.html">some</a> <a href="http://www.mathrecreation.com/2016/06/more-chlandi-figures-in-r.html">posts</a> about generating Chladni Figures using R scripts. These scripts generated some pretty nice images, I thought. But, to experiment a bit more it would be nice to have something interactive, so I put together <a href="https://dmackinnon1.github.io/chladni/">this page</a>, which you can use to make images like the one below.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-RsRG1gFuqhQ/WW10wWNNsqI/AAAAAAAAD5c/IKECMA1onTodEz8xTOfjdBAZ17UoCsfBgCLcBGAs/s1600/chladni2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="464" data-original-width="463" height="320" src="https://1.bp.blogspot.com/-RsRG1gFuqhQ/WW10wWNNsqI/AAAAAAAAD5c/IKECMA1onTodEz8xTOfjdBAZ17UoCsfBgCLcBGAs/s320/chladni2.png" width="319" /></a></div><br />Adding more vibrations to the surface, you can get some pretty intricate looking patterns:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-QzISQ3fQeXc/WW107OqvczI/AAAAAAAAD5g/LHhg7cn49Ws6Nqi4uqmku6IPZNkf22HfwCLcBGAs/s1600/chladni4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="357" data-original-width="356" height="320" src="https://3.bp.blogspot.com/-QzISQ3fQeXc/WW107OqvczI/AAAAAAAAD5g/LHhg7cn49Ws6Nqi4uqmku6IPZNkf22HfwCLcBGAs/s320/chladni4.png" width="319" /></a></div><br />If you would like to try it out, please visit: <a href="https://dmackinnon1.github.io/chladni/">https://dmackinnon1.github.io/chladni/ </a>(source <a href="https://github.com/dmackinnon1/chladni">here</a>).<img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/PgEZym5V75k" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/07/interactive-chladni-figure-page.htmltag:blogger.com,1999:blog-5008879105295771159.post-66008639808010694632017-04-29T13:10:00.001-07:002017-05-01T08:44:22.047-07:00truchet en plusSince <a href="http://www.mathrecreation.com/2017/03/truchet-tiles.html">the previous post</a>, I have been playing around with more variations on Truchet tiles (using <a href="https://dmackinnon1.github.io/truchet/">this page</a>). The variety of appealing patterns that you can create from these simple tiles is impressive.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-cVG7DjrJ9v0/WQTcd4GVzxI/AAAAAAAAD4Y/Q-oRBDkDaNcTtbEzB5yV7u--Rq3oc4UNwCLcB/s1600/solitary_tile.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-cVG7DjrJ9v0/WQTcd4GVzxI/AAAAAAAAD4Y/Q-oRBDkDaNcTtbEzB5yV7u--Rq3oc4UNwCLcB/s1600/solitary_tile.png" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>the humble Truchet tile</i></div><br />For example, using this simple base tile you can create a path-like effect, even to the extent that paths can seem to weave under and over each other. The patterns below use this effect to suggest links and knots.<br /><div class="separator" style="clear: both; text-align: center;"></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-3I4W3pWreA4/WQTWL4vTkEI/AAAAAAAAD38/MFrwWtlW20MVg1jGi-o4wS8BL44RtGyeQCLcB/s1600/link_and_knot.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="155" src="https://3.bp.blogspot.com/-3I4W3pWreA4/WQTWL4vTkEI/AAAAAAAAD38/MFrwWtlW20MVg1jGi-o4wS8BL44RtGyeQCLcB/s320/link_and_knot.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>Truchet patters for two links (left) <br />and a <a href="http://www.mathrecreation.com/2010/04/three-ring-circus.html">trefoil knot</a> (right)</i></div><br />Slight variations in the base tile can produce interesting effects. Here's an example that uses the traditional Truchet base tile.<br /><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-tXNCfgnH390/WQQEdBnIMzI/AAAAAAAAD3c/jhjaYib-N4I7psppe6VJfXysxOBWbZULQCLcB/s1600/traditional_1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="232" src="https://3.bp.blogspot.com/-tXNCfgnH390/WQQEdBnIMzI/AAAAAAAAD3c/jhjaYib-N4I7psppe6VJfXysxOBWbZULQCLcB/s320/traditional_1.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><br /></div>Bulging the dark right triangle into a quarter circle allows us create something that looks quite different, even though it consists of exactly the same tile placements. Squares are replaced by circles, V-patterns replaced by tulips, and we end up with organic and densely packed patterns.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-3m1Yci_HaeI/WQQEx8xGmfI/AAAAAAAAD3g/Sy7_GgZEtsYKXGbFSAt9TXekBy9Zs0v5QCLcB/s1600/semi_1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="225" src="https://1.bp.blogspot.com/-3m1Yci_HaeI/WQQEx8xGmfI/AAAAAAAAD3g/Sy7_GgZEtsYKXGbFSAt9TXekBy9Zs0v5QCLcB/s320/semi_1.png" style="cursor: move;" width="320" /></a></div><br />A common variation on the Truchet tile is the Smith tile, which consists of two quarter circles at opposite corners. Unlike the traditional Truchet, the Smith base tile has 180 degree symmetry, but because it lacks 90 degree symmetry, it can still be used to produce interesting and appealing patterns (if we had quarter circles in all four corners, the constructed patterns would always be the same - an array of circles). Using this tile, we end up with circles and blobby regions that create paths and zones across the grid.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Krh6wFb16lY/WQTXVAUxGBI/AAAAAAAAD4E/VVbynlyvEKYsZbx7AVIT8qGnPCFUsvp3wCLcB/s1600/smith.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="237" src="https://1.bp.blogspot.com/-Krh6wFb16lY/WQTXVAUxGBI/AAAAAAAAD4E/VVbynlyvEKYsZbx7AVIT8qGnPCFUsvp3wCLcB/s320/smith.png" width="320" /></a></div><br />A small change to the Smith tile allows us to eliminate the 180 degree symmetry and regain the expressiveness of the traditional tile patterns. For example replacing one of the quarter circles with a square means that some circles in our original pattern become squares, some remain circles, and some take on a lemon-shape, while the overall pattern retains the same topology as it has in the Smith version.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-gla8sLLqKLg/WQTXvoLRKoI/AAAAAAAAD4I/5kd6s8nOr58PjxJoFjehR-OnAqQab2K9gCLcB/s1600/curve_square.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="https://3.bp.blogspot.com/-gla8sLLqKLg/WQTXvoLRKoI/AAAAAAAAD4I/5kd6s8nOr58PjxJoFjehR-OnAqQab2K9gCLcB/s320/curve_square.png" width="320" /></a></div><br />Another small change (using a diagonal line in place of the square) produces patterns that look quite different at fist: our paths now resemble strange jigsaw shapes. A closer look shows how the essential features are retained.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-cgsih759GTk/WQTYB-A6ETI/AAAAAAAAD4M/_mOfVRwERRQc1j5N-9St1VBZk2fakO-AACLcB/s1600/curve_line.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="236" src="https://4.bp.blogspot.com/-cgsih759GTk/WQTYB-A6ETI/AAAAAAAAD4M/_mOfVRwERRQc1j5N-9St1VBZk2fakO-AACLcB/s320/curve_line.png" width="320" /></a></div><br />Even with all the possible variations, the original tile retains its charm. Can you see the four trefoils in the pattern below?<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-Mv-3ui93bdE/WQT1ineVesI/AAAAAAAAD4o/f4nReUedtFAjyPsX_VAjsJ3UmFNKf8z-ACLcB/s1600/4_trefoils.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://2.bp.blogspot.com/-Mv-3ui93bdE/WQT1ineVesI/AAAAAAAAD4o/f4nReUedtFAjyPsX_VAjsJ3UmFNKf8z-ACLcB/s320/4_trefoils.png" width="318" /></a></div><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/oshHWC5AXwc" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/04/truchet-en-plus.htmltag:blogger.com,1999:blog-5008879105295771159.post-6078831408711487152017-03-26T14:13:00.004-07:002017-05-01T08:00:24.297-07:00truchet tilesA <a href="http://www.mathrecreation.com/2016/10/doodling-with-froebel.html">short while back</a>, I posted about the images found in books about Froebelian kindergarten exercises, like <b>The Paradise of Childhood</b> (on Google Books <a href="https://books.google.ca/books?id=UiydAAAAMAAJ">here</a>). These old books provide great examples of patterns and designs that can be easily drawn by hand with graph paper, in many cases only using arrangements of congruent 45-90 triangles.<br /><br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-O9JTuek9QJY/WNVuNBjHeoI/AAAAAAAAD00/gt1qkIQcs7cjYTTfC3I33apmJ8fvUPEzwCLcB/s1600/from_froebel540.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="131" src="https://4.bp.blogspot.com/-O9JTuek9QJY/WNVuNBjHeoI/AAAAAAAAD00/gt1qkIQcs7cjYTTfC3I33apmJ8fvUPEzwCLcB/s400/from_froebel540.png" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>Nineteenth Century Froebelian Doodles</i></div><br />A surprising variety of patterns can be formed by restricting things even further, considering the case where each square is cut in half along a diagonal with half of the square coloured black, the other coloured white (i.e. no blank or completely filled squares, as are found in the images above).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-2vfAS1UW-O8/WNVyYvdKOhI/AAAAAAAAD1A/SBr12BxuD48xmt3gh3PFA2AwbXSgLw7rACLcB/s1600/four_tiles.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="215" src="https://3.bp.blogspot.com/-2vfAS1UW-O8/WNVyYvdKOhI/AAAAAAAAD1A/SBr12BxuD48xmt3gh3PFA2AwbXSgLw7rACLcB/s320/four_tiles.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>Some arrangements of four Truchet Tiles</i></div><br />Arrangements of these tiles were studied extensively by <a href="https://en.wikipedia.org/wiki/S%C3%A9bastien_Truchet">Sebastien Truchet</a>, whose book on the subject (<i>Method for creating an infinite number of different designs with squares halved into two colours along a diagonal</i>) can be found online <a href="https://books.google.ca/books?id=pK7-X6u7FCMC">here</a>.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-_-_lr52e10o/WNVzvRJbHEI/AAAAAAAAD1M/E17rv0oFGh4Y6YisNAHzmFL7BeNRYXhYgCLcB/s1600/truchet_book.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="137" src="https://4.bp.blogspot.com/-_-_lr52e10o/WNVzvRJbHEI/AAAAAAAAD1M/E17rv0oFGh4Y6YisNAHzmFL7BeNRYXhYgCLcB/s320/truchet_book.png" width="320" /></a></div><br /><a href="https://en.wikipedia.org/wiki/Truchet_tiles">Truchet tiles,</a> as they became known, have been studied extensively and generalised to include other tile sets that are not rotationally symmetrical. In the image below, we start with a traditional Truchet tiling, then only show the diagonals, and finally replacing the diagonals with quarter circles, centred around the vertices where the diagonals used to touch (these tiles, introduced by Cyril Stanley Smith, create interesting patterns of blob-like paths and circles).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-cDGA6vs7PQo/WNV5WpNgq6I/AAAAAAAAD1c/LUB-xZUIJesNoPqBdhcdhQDHwv03SH03gCLcB/s1600/3_styles.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://3.bp.blogspot.com/-cDGA6vs7PQo/WNV5WpNgq6I/AAAAAAAAD1c/LUB-xZUIJesNoPqBdhcdhQDHwv03SH03gCLcB/s320/3_styles.png" width="310" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>Three popular variations on Truchet tiles: <br />traditional, diagonal, and semi-circles</i></div><br /><br />To play around with these I've put together a "Truchet Tiles" page <a href="https://dmackinnon1.github.io/truchet/">here</a>.<br /><br />There are a number of illustrations in Truchet's text that are worth checking out, and you can reproduce them using the page mentioned above. Here is tiling "38" from Truchet:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-XGSyZw7iuDs/WNV7ddCRcwI/AAAAAAAAD1o/SWhXyxB3ScskM7PzOBB2fe7RobIbyiPDgCLcB/s1600/truchet38.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://3.bp.blogspot.com/-XGSyZw7iuDs/WNV7ddCRcwI/AAAAAAAAD1o/SWhXyxB3ScskM7PzOBB2fe7RobIbyiPDgCLcB/s1600/truchet38.png" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>tile pattern 38 from <a href="https://books.google.ca/books?id=pK7-X6u7FCMC">Truchet</a></i></div><br />Here is the same tiling using the Truchet tile page, also rendered using only diagonals and the Smith tiles.<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-dqfAVgozUo0/WNV9SJD68xI/AAAAAAAAD10/GCCxB1wccW8_g4X8q93XUkjob69Eog2OwCLcB/s1600/truchet38.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://2.bp.blogspot.com/-dqfAVgozUo0/WNV9SJD68xI/AAAAAAAAD10/GCCxB1wccW8_g4X8q93XUkjob69Eog2OwCLcB/s400/truchet38.png" width="351" /></a></div><div class="separator" style="clear: both; text-align: center;"><i>tile pattern 38, generated <a href="https://dmackinnon1.github.io/truchet/">here</a></i></div><br /><br />There are lots of questions that can be asked about arrangements of the tiles. Truchet enumerates some of the possible arrangements using symbols and illustrations - below are the first two tables of rows of tiles that he lists (how many will be in the next two tables?).<br /><br /><div class="separator" style="clear: both; text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-XdzKsHWn21Y/WNfRjcvmFMI/AAAAAAAAD2I/pcqxnuVtrscdDjyh3hS0irY1_dmUCWxtQCLcB/s1600/truchet_perms.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://2.bp.blogspot.com/-XdzKsHWn21Y/WNfRjcvmFMI/AAAAAAAAD2I/pcqxnuVtrscdDjyh3hS0irY1_dmUCWxtQCLcB/s320/truchet_perms.png" width="217" /></a></div>Here is another rendering of one of Truchet's original patterns, number 52:<br /><div class="separator" style="clear: both; text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-HYQ9I6334Gc/WNgt5GeguBI/AAAAAAAAD2Y/8ceGNidGTMYyYIM2Pi3RcXGzfKGnlU7KgCLcB/s1600/truchet_52_both.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="176" src="https://2.bp.blogspot.com/-HYQ9I6334Gc/WNgt5GeguBI/AAAAAAAAD2Y/8ceGNidGTMYyYIM2Pi3RcXGzfKGnlU7KgCLcB/s320/truchet_52_both.png" width="320" /></a></div><br />And replacing the traditional truchet tiles with similarly oriented diagonal and Smith tiles - as you might have noticed, doing this looses information by a factor of 2 for each tile:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-OfsVpusRIPI/WNgukNohe0I/AAAAAAAAD2g/NWnhk5HUc4YNH86yMCFVxLb0CQSS5VmaQCLcB/s1600/diag_smith52.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="159" src="https://2.bp.blogspot.com/-OfsVpusRIPI/WNgukNohe0I/AAAAAAAAD2g/NWnhk5HUc4YNH86yMCFVxLb0CQSS5VmaQCLcB/s320/diag_smith52.png" width="320" /></a></div><br />Try out the Truchet tile page here: <a href="https://dmackinnon1.github.io/truchet/">https://dmackinnon1.github.io/truchet/</a>.<br /><i><br /></i><i>Update: More truchet fun in <a href="http://www.mathrecreation.com/2017/04/truchet-en-plus.html">this post</a>.</i><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/yBFmsuCyDv4" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/03/truchet-tiles.htmltag:blogger.com,1999:blog-5008879105295771159.post-41344591698160988802017-03-24T12:01:00.002-07:002017-03-24T12:01:34.807-07:00probability simulations using RAn ongoing side project of mine is learning how to use the statistics scripting language R, and have been putting putting together R markdown files that set up simulations for a variety of probability problems. You can find some of them here: <a href="https://dmackinnon1.github.io/r_examples/">https://dmackinnon1.github.io/r_examples/</a>.<br /><br />These are simulations that generate data based on problems like the Birthday problem, the Monty Hall problem, and the Burnt Pancake problem. Learning scripting languages aside, it is always good to keep digging into probability problems: they confuse practically everyone.<br /><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/ZNZ-39mtcVk" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/03/probability-simulations-using-r.htmltag:blogger.com,1999:blog-5008879105295771159.post-6192344750941902412017-03-07T18:40:00.002-08:002017-03-08T04:46:07.662-08:00Ulam's two step cellular automata<div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-MOQCugs8bDk/WL9gOpLqywI/AAAAAAAAD0M/TTSzybGkMFkQ4ruLTFRK9w_Lo-i2-stfwCLcB/s1600/some_ulam2steps.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://3.bp.blogspot.com/-MOQCugs8bDk/WL9gOpLqywI/AAAAAAAAD0M/TTSzybGkMFkQ4ruLTFRK9w_Lo-i2-stfwCLcB/s400/some_ulam2steps.png" width="395" /></a></div><br />Above are some of the nice images generated by a cellular automata described in one of Martin Gardner's essays about Conway's Game of Life (you can find the essays <a href="http://www.maa.org/sites/default/files/pdf/pubs/focus/Gardner_GameofLife10-1970.pdf">here</a>). Cells have four neighbours (north, south, east, west), and follow only two rules that are applied at each step: if a cell has one live neighbour it turns on, and if a cell is on it turns off after two steps. The images above start happening around step 100 after turning on a single cell at the centre of a 61 by 61 grid.<br /><br />You can play with these <a href="https://dmackinnon1.github.io/svgpixel/ulam.html">here</a>. Eventually, these will start to repeat or disappear completely (I suspect they will oscillate, but have not found out when yet). On a 5 by 5 board, a single central cell will lead to a pattern that dies out in 10 generations; once you get to the uniform checkerboard state, the next is an empty board.<br /><div><br /></div><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-XXLkyY2ZNmI/WL9sj5MpbtI/AAAAAAAAD0c/FoJ27hMDFxc_8MmUVS8rzGpRfW-iumBtwCLcB/s1600/5x5_grid.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://4.bp.blogspot.com/-XXLkyY2ZNmI/WL9sj5MpbtI/AAAAAAAAD0c/FoJ27hMDFxc_8MmUVS8rzGpRfW-iumBtwCLcB/s320/5x5_grid.png" width="318" /></a></div><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/GCo8HhYCc38" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/03/ulams-two-step-cellular-automata.htmltag:blogger.com,1999:blog-5008879105295771159.post-60393519478539772832017-03-06T14:02:00.000-08:002017-03-06T14:02:46.843-08:00the ants go marching...<br />It's not exactly pride or satisfaction, but some related feeling, when you see your <a href="https://en.wikipedia.org/wiki/Langton's_ant">little ant</a> marching off on the highway that emerges from the initial chaos it seemed lost in. Keep marching little buddy.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-iAlJhc8erFE/WL3YjN-O9lI/AAAAAAAADz8/t9MpYOUGxWEGqyEOygFzJ6k6FGNRCvICgCLcB/s1600/ant.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://3.bp.blogspot.com/-iAlJhc8erFE/WL3YjN-O9lI/AAAAAAAADz8/t9MpYOUGxWEGqyEOygFzJ6k6FGNRCvICgCLcB/s320/ant.PNG" width="313" /></a></div><br />You can create a small ant farm <a href="https://dmackinnon1.github.io/svgpixel/langton.html">here</a>, if you'd like.<img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/X3007mw3nA8" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/03/the-ants-go-marching.htmltag:blogger.com,1999:blog-5008879105295771159.post-71538568774656515622017-02-11T13:32:00.001-08:002017-02-20T10:19:22.606-08:00fibonacci foolery<span style="font-size: large;">Some misleading dissections</span><br /><br />Consider a square whose sides are 5 units in length. We are going to dissect the square by cutting it as shown below. We can then re-arrange the pieces to form a rectangle.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-e5bx_bh11fE/WJ4Bvu-t6hI/AAAAAAAADxQ/BY8STa8Ms5Uh-5e0lkFgZnjlTDnNy4wpACLcB/s1600/235_illusion.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="166" src="https://1.bp.blogspot.com/-e5bx_bh11fE/WJ4Bvu-t6hI/AAAAAAAADxQ/BY8STa8Ms5Uh-5e0lkFgZnjlTDnNy4wpACLcB/s400/235_illusion.JPG" width="400" /></a></div><br />But wait, the square has area 5 * 5 = 25, while the rectangle has area 8 * 3 = 24... somewhere we lost one square unit. This paradoxical result tells us that something is wrong, but what is it?<br /><br />Let's look at another very similar dissection, this time using a square with sides length 8 units, sliced up and re-assembled in a similar way:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-UBH0S6VJIX0/WJ4DqHJp9gI/AAAAAAAADxc/IwsXdABWGKUhAxqcOktb0Mzj9MT0rRKsQCLcB/s1600/358_illusion.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="160" src="https://1.bp.blogspot.com/-UBH0S6VJIX0/WJ4DqHJp9gI/AAAAAAAADxc/IwsXdABWGKUhAxqcOktb0Mzj9MT0rRKsQCLcB/s400/358_illusion.JPG" width="400" /></a></div><br />Here the square has area 8 * 8 = 64, but the rectangle has area 13 * 5 = 65. In this case we have gained one square unit (maybe borrowed from puzzle above?).<br /><br />In both cases, the discrepancy in the areas tells us that we are doing something illegal when we re-assemble the square into the rectangle. You can see where the problem is if you look at the triangles within the rectangles. Consider the first problem, where we split up the length 5 into lengths 2 and 3. Can we really put those pieces together? Apparently not - if we try to fit one of the triangles and quadrilaterals pieces together, we find that they don't actually form a right-triangle - the hypotenuse is not straight, it bumps out a bit:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-9OKl3N1M6rg/WKsyFSSZPdI/AAAAAAAADzc/Uov2fRAi2BgZ4Wfh7qRDC356G_EgaU7tACLcB/s1600/235_problemA1.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="140" src="https://1.bp.blogspot.com/-9OKl3N1M6rg/WKsyFSSZPdI/AAAAAAAADzc/Uov2fRAi2BgZ4Wfh7qRDC356G_EgaU7tACLcB/s320/235_problemA1.JPG" width="320" /></a></div><br /><br />In the (2,3,5) problem, if the figure did line up properly, the large triangle with base 8 and height 3 would be <a href="https://en.wikipedia.org/wiki/Similarity_(geometry)#Similar_triangles">similar</a> to the smaller triangle with base 5 and height 2. This would mean that 2/5 equals 3/8, which is not true. If we place the original triangle of base on top of the larger triangle, the pieces would not line up:<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-d9MWfFkq9c4/WJ4E9VeSwqI/AAAAAAAADxo/koshV-cidG4SnfbgFFL1olQ2N1BG7aoRQCLcB/s1600/235_problem.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="144" src="https://1.bp.blogspot.com/-d9MWfFkq9c4/WJ4E9VeSwqI/AAAAAAAADxo/koshV-cidG4SnfbgFFL1olQ2N1BG7aoRQCLcB/s320/235_problem.JPG" width="320" /></a></div><br /><br /><span style="font-size: large;">The Fibonacci connection</span><br /><br />You may have noticed something familiar in the numbers used in the dissections above. Both triples (2, 3, 5), used in the first dissection, and (3, 5, 8), used in the second, are successive terms in the Fibonacci sequence:<br /><br /><div style="text-align: center;"><span style="font-size: large;">0, 1, 1, 2, 3, 5, 8, 13, 21, ..</span></div><div style="text-align: center;"><br /></div>The Fibonacci sequence is defined recursively by:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-h1PypimbvP0/WJ46Hnun_iI/AAAAAAAADyY/ThRh3K1xkg8epf4IOPxwwA03dPAiMQLkACLcB/s1600/fib_def.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="48" src="https://3.bp.blogspot.com/-h1PypimbvP0/WJ46Hnun_iI/AAAAAAAADyY/ThRh3K1xkg8epf4IOPxwwA03dPAiMQLkACLcB/s400/fib_def.png" width="400" /></a></div><br /><br />Can we construct another misleading dissection using the next Fibonacci triple (5, 8, 13)? Let's see:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-_SYER2WfsxI/WJ4GXxA0gcI/AAAAAAAADx0/520tZc6u5dQ1MewM8IhXBtBs48J5wlLcQCLcB/s1600/5813_illusion.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="168" src="https://1.bp.blogspot.com/-_SYER2WfsxI/WJ4GXxA0gcI/AAAAAAAADx0/520tZc6u5dQ1MewM8IhXBtBs48J5wlLcQCLcB/s400/5813_illusion.JPG" width="400" /></a></div><br />Our square in this case has area 13 * 13 = 169, while our rectangle has area 21 * 8 = 168. So we are back to losing a square unit when we re-assemble the dissected square into the rectangle.<br /><br />It turns out that Fibonacci triples like these will always generate these "off by one" illusions, because three successive terms in the Fibonacci sequence always obey the <a href="https://en.wikipedia.org/wiki/Cassini_and_Catalan_identities">Cassini identity</a>, which expresses the situation shown in these diagrams: if you have a Fibonacci triple (<i>a</i>, <i>b</i>, <i>c</i>), then the product of <i>a</i> times <i>c</i> is going to be either one more or one less than the square of <i>b</i>. More precisely, Cassini tells us:<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-1QVB3h_S-O4/WJ47IwYqBnI/AAAAAAAADyk/9hmHAA1VmXk7sF9gQwXlI2a8nA23PPCqgCLcB/s1600/cassini_def.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://1.bp.blogspot.com/-1QVB3h_S-O4/WJ47IwYqBnI/AAAAAAAADyk/9hmHAA1VmXk7sF9gQwXlI2a8nA23PPCqgCLcB/s1600/cassini_def.png" /></a></div><br />The Cassini identity can be proved in a variety of ways, including induction. For <i>n = </i>1, we have 0*1-1 = -1, so the identity is satisfied. If we assume the relationship holds for <i>n</i> = <i>k </i>- 1, we can prove the <i>n</i> = <i>k</i> case as follows:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-D3jDMMTdCCc/WJ457zidtMI/AAAAAAAADyU/V0bOxlaRGAECl09XRHH4DHflBnMuiJU9gCLcB/s1600/cassini_induction.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="301" src="https://4.bp.blogspot.com/-D3jDMMTdCCc/WJ457zidtMI/AAAAAAAADyU/V0bOxlaRGAECl09XRHH4DHflBnMuiJU9gCLcB/s400/cassini_induction.png" width="400" /></a></div><br />See some more proofs of the Cassini identity <a href="http://www.cut-the-knot.org/arithmetic/algebra/CassinisIdentity.shtml">here</a>.<br /><br /><span style="font-size: large;">A Golden Solution</span><br /><br />This dissection and re-assembly of the square into a rectangle looks like a nice one, and we'd like to find a case where it works: we want to find where to cut so that the square pieces fit correctly into the rectangle and the areas of the figures match up. Clearly basing the cut on the Fibonacci numbers won't work...<br /><br />Let's start with a square whose sides are length 1. We would like to find two numbers <i>a</i> and <i>b</i> such that we can perform the dissection and assembly as shown below.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-hNmy5eKQe9I/WJ4MtHFd9DI/AAAAAAAADyE/fI-y2XIAgSU7SZ3276HQfYrSYrpBHtLHACLcB/s1600/abc_problem.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="171" src="https://1.bp.blogspot.com/-hNmy5eKQe9I/WJ4MtHFd9DI/AAAAAAAADyE/fI-y2XIAgSU7SZ3276HQfYrSYrpBHtLHACLcB/s400/abc_problem.JPG" width="400" /></a></div><br />What we would like is the area of the rectangle to equal that of the square:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-9FSFfaG1lhE/WJ4-4vkUzOI/AAAAAAAADyw/Ph2mc320wXAChHm48xRrt-gAPEYcw2dBACLcB/s1600/equal_area.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-9FSFfaG1lhE/WJ4-4vkUzOI/AAAAAAAADyw/Ph2mc320wXAChHm48xRrt-gAPEYcw2dBACLcB/s1600/equal_area.png" /></a></div><br />And taking the positive solution from the quadratic formula, we get:<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-wAO-t-cUC34/WJ4_JK7xlWI/AAAAAAAADy0/kQfX5LMbk_MPH2YIy9zs9pvI2hYESa6QACLcB/s1600/Phi.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-wAO-t-cUC34/WJ4_JK7xlWI/AAAAAAAADy0/kQfX5LMbk_MPH2YIy9zs9pvI2hYESa6QACLcB/s1600/Phi.png" /></a></div><br />We used the capital Greek letter Phi here because this quantity is known as the <a href="https://en.wikipedia.org/wiki/Golden_ratio#Golden_ratio_conjugate">golden ratio conjugate</a>, making the base of our rectangle, 1 + <i>b,</i> equal to the golden ratio.<br /><br />This is a nice surprise because of the close association between Fibonacci numbers and the golden ratio - the quotient of consecutive Fibonacci numbers becomes closer and closer to the golden ratio as the Fibonacci numbers get larger.<br /><br />So, while using Fibonacci numbers in the dissection always yields nice deceptions which alternate between gaining and loosing a square unit, slicing the square using the golden ratio (or golden ratio conjugate) gives us a perfect re-assembly of the square into a rectangle.<br /><br /><br /><img src="http://feeds.feedburner.com/~r/Mathrecreation/~4/lrM53mEDkXM" height="1" width="1" alt=""/>Dan MacKinnonhttps://plus.google.com/100029769408149043814noreply@blogger.comhttp://www.mathrecreation.com/2017/02/fibonacci-foolery.html