The Universe of DiscourseThe Universe of Discourse (Mark Dominus Blog)tag:blog.plover.com,2005:/mathBlosxomhttp://perl.plover.com/favicon.ico2016-07-12T19:13:00Ztag:blog.plover.com,2016:/math/17-puzzleA simple but difficult arithmetic puzzle2016-07-12T19:13:00Z2016-07-12T19:13:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>Lately my kids have been interested in puzzles of this type: You are
given a sequence of four digits, say 1,2,3,4, and your job is to
combine them with ordinary arithmetic operations (+, -, ×, and ÷) in any order to
make a target number, typically 24. For example, with 1,2,3,4, you
can go with $$((1+2)+3)×4 = 24$$ or with $$4×((2×3)×1) = 24.$$</p>
<p>We were stumped trying to make 6,6,5,2 total 24, so I hacked up a
solver; then we felt a little foolish when we saw the solutions,
because it is not that hard. But in the course of testing the solver,
I found the most challenging puzzle of this type that I've ever seen.
It is:</p>
<blockquote>
<p>Given 6,6,5,2, make 17.</p>
</blockquote>
<p>There are no underhanded tricks. For example, you may not concatenate
2 and 5 to make 25; you may not say <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%246%c3%b76%3d1%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%245%2b2%3d7%24"> and
concatenate 1 and 7 to make <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2417%24">; you may not interpret the 17 as a
base 12 numeral, etc.</p>
<p>I hope to write a longer article about solvers in the next week or so.</p>
tag:blog.plover.com,2016:/math/horse-puzzleThe sage and the seven horses2016-04-20T02:11:00Z2016-04-20T02:11:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>A classic puzzle of mathematics goes like this:</p>
<blockquote>
<p>A father dies and his will states that his elder daughter should
receive half his horses, the son should receive one-quarter of the
horses, and the younger daughter should receive one-eighth of the
horses. Unfortunately, there are seven horses. The siblings are
arguing about how to divide the seven horses when a passing sage hears
them. The siblings beg the sage for help. The sage donates his own
horse to the estate, which now has eight. It is now easy to portion
out the half, quarter, and eighth shares, and having done so, the
sage's horse is unaccounted for. The three heirs return the surplus
horse to the sage, who rides off, leaving the matter settled fairly.</p>
</blockquote>
<p>(The puzzle is, what just happened?)</p>
<p>It's not hard to come up with variations on this. For example,
picking three fractions at random, suppose the will says that the
eldest child receives half the horses, the middle child receives
one-fifth, and the youngest receives one-seventh. But the estate has
only 59 horses and an argument ensues. All that is required for
the sage to solve the problem is to lend the estate eleven horses.
There are now 70, and after taking out the three bequests, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2470%20%2d%2035%20%2d%0a14%20%2d%2010%20%3d%2011%24"> horses remain and the estate settles its debt to the
sage.</p>
<p>But here's a variation I've never seen before. This time there are 13
horses and the will says that the three children should receive shares
of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac12%2c%20%5cfrac13%2c%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac14%24">. respectively. Now the
problem seems impossible, because <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac12%20%2b%20%5cfrac13%20%2b%20%5cfrac14%20%5cgt%0a1%24">. But the sage is equal to the challenge! She leaps into the
saddle of one of the horses and rides out of sight before the
astonished heirs can react. After a day of searching the heirs write
off the lost horse and proceed with executing the will. There are now
only 12 horses, and the eldest takes half, or six, while the middle
sibling takes one-third, or 4. The youngest heir should get three,
but only two remain. She has just opened her mouth to complain at her
unfair treatment when the sage rides up from nowhere and hands her the
reins to her last horse.</p>
tag:blog.plover.com,2015:/math/se/2015-08Math.SE report 2015-082015-12-18T21:50:00Z2015-12-18T21:50:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>I only posted three answers in August, but two of them were interesting.</p>
<ul>
<li><p>In <a href="http://math.stackexchange.com/a/1381699/25554">why this <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5csigma%5cpi%5csigma%5e%7b%2d1%7d%24"> keeps apearing in my group
theory book? (cycle
decomposition)</a> the
querent asked about the “conjugation” operation that keeps cropping
up in group theory. Why is it important? I sympathize with this;
it wasn't adequately explained when I took group theory, and I had
to figure it out a long time later. Unfortunately I don't think I
picked the right example to explain it, so I am going to try again
now.</p>
<p>Consider the eight symmetries of the square. They are of five types:</p>
<ol>
<li>Rotation clockwise or counterclockwise by 90°.</li>
<li>Rotation by 180°.</li>
<li>Horizontal or vertical reflection</li>
<li>Diagonal reflection</li>
<li>The trivial (identity) symmetry</li>
</ol>
<p>What is meant when I say that a horizontal and a vertical reflection
are of the same ‘type’? Informally, it is that the horizontal
reflection looks just like the vertical reflection, if you turn your
head ninety degrees. We can formalize this by observing that if we
rotate the square 90°, then give it a horizontal flip, then rotate it
back, the effect is exactly to give it a vertical flip. In notation,
we might represent the horizontal flip by <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24H%24">, the vertical flip by
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24V%24">, the clockwise rotation by <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5crho%24">, and the counterclockwise
rotation by <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5crho%5e%7b%2d1%7d%24">; then we have </p>
<p>$$ \rho H \rho^{-1} = V$$</p>
<p>and similarly </p>
<p>$$ \rho V \rho^{-1} = H.$$</p>
<p>Vertical flips do not look like diagonal flips—the diagonal flip leaves two of the corners in the same place, and the vertical flip does not—and indeed there is
no analogous formula with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24H%24"> replaced with one of the <em>diagonal</em>
flips. However, if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24D_1%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24D_2%24"> are the two diagonal flips,
then we <em>do</em> have</p>
<p>$$ \rho D_1 \rho^{-1} = D_2.$$</p>
<p>In general, When <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24"> are
two symmetries, and there is some symmetry <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24"> for which </p>
<p>$$xax^{-1} = b$$</p>
<p>we say that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24"> is <em>conjugate to</em> <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24">.
One can show that
conjugacy is an equivalence relation, which means that the symmetries
of any object can be divided into separate “conjugacy classes” such that two
symmetries are conjugate if and only if they are in the same class.
For the square, the conjugacy classes are the five I listed earlier.</p>
<p>This conjugacy thing is important for telling when two symmetries
are group-theoretically “the same”, and have the same
group-theoretic properties. For example, the fact that the
horizontal and vertical flips move all four vertices, while the
diagonal flips do not. Another example is that a horizontal flip is
self-inverse (if you do it again, it cancels itself out), but a 90°
rotation is not (you have to do it <em>four</em> times before it cancels
out.) But the horizontal flip shares all its properties with the
vertical flip, because it is the same if you just turn your head.</p>
<p>Identifying this sameness makes certain kinds of arguments much
simpler. For example, in <a href="http://blog.plover.com/math/polya-burnside.html">counting
squares</a>, I wanted to
count the number of ways of coloring the faces of a cube, and instead
of dealing with the 24 symmetries of the cube, I only needed to deal
with their 5 conjugacy classes.</p>
<p>The example I gave in my math.se answer was maybe less perspicuous. I
considered the symmetries of a sphere, and talked about how two
rotations of the sphere by 17° are conjugate, regardless of what axis
one rotates around. I thought of the square at the end, and threw it
in, but I wish I had started with it.</p></li>
<li><p><a href="http://math.stackexchange.com/a/1404453/25554">How to convert a decimal to a fraction
easily?</a> was the
month's big winner. OP wanted to know how to take a decimal like
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%2e3760683761%24"> and discover that it can be written as
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%7b44%7d%7b117%7d%24">. The right answer to this is of course to use
continued fraction theory, but I did not want to write a long
treatise on continued fractions, so I stripped down the theory to
obtain an algorithm that is slower, but much easier to understand.</p>
<p>The algorithm is just binary search, but with a twist. If you are looking for a
fraction for <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24">, and you know <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%20ab%20%3c%20x%20%3c%20%5cfrac%20cd%24">, then
you construct the mediant <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%7ba%2bc%7d%7bb%2bd%7d%24"> and compare it with
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24">. This gives you a smaller interval in which to search for
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24">, and the reason you use the mediant instead of using
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac12%5cleft%28%5cfrac%20ab%20%2b%20%5cfrac%20cd%5cright%29%24"> as usual is that if you use the
mediant you are guaranteed to exactly nail all the best rational
approximations of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24">. This is the algorithm I
described a few years ago in <a href="http://blog.plover.com/math/age-fraction-2.html">your age as a fraction,
again</a>; there the binary search proceeds
down the branches of the Stern-Brocot tree to find a fraction close
to <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%2e368%24">.</p></li>
</ul>
<hr />
<p>I did ask a question this month: I was looking for a <a href="http://math.stackexchange.com/q/1405312/25554">simpler version
of the dogbone space
construction</a>. The
dogbone space is a very peculiar counterexample of general topology,
originally constructed by R.H. Bing. <a href="http://blog.plover.com/math/R3-root.html">I mentioned it here in
2007</a>, and said, at the time:</p>
<blockquote>
<p>[The paper] is on my desk, but I have not read this yet, and I may never.</p>
</blockquote>
<p>I did try to read it, but I did not try very hard, and I did not
understand it. So my question this month was if there was a simpler
example of the same type. I did not receive an answer, just a
followup comment that no, there is no such example.</p>
tag:blog.plover.com,2015:/math/se/2015-07Math.SE report 2015-072015-08-16T16:38:00Z2015-08-16T16:38:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>My overall SE posting volume was down this month, and not only did I
post relatively few interesting items, I've already written <a href="http://blog.plover.com/math/ounce-of-theory-2.html">a whole
article about the most interesting
one</a>. So this will be a short
report.</p>
<ul>
<li><p>I already wrote up <a href="http://math.stackexchange.com/questions/1376640">Building a box from smaller
boxes</a> on the blog
<a href="http://blog.plover.com/math/ounce-of-theory-2.html">here</a>. But maybe I have a
couple of extra remarks. First, the other guy's proposed solution
is awful. It's long and complicated, which is forgivable if it had
answered the question, but it doesn't. And the key point is “blah
blah blah therefore code a solver which visits all configurations of
the search space”. Well heck, if this post had just been one
sentence that ended with “code a solver which visits all
configurations of the search space” I would not have any complaints
about that. </p>
<p>As an undergraduate I once gave a talk on this topic. One of my
examples was the problem of packing 31 dominoes into a chessboard
from which two squares have been deleted. There is a simple
combinatorial argument why this is impossible if the two deleted
squares are the same color, say if they are opposite corners: each
domino must cover one square of each color. But if you don't take
time to think about the combinatorial argument you could waste a lot
of time on computer search learning that there is no solution in
that case, and completely miss the deeper understanding that it
brings you. So this has been on my mind for a long time.</p></li>
<li><p>I wrote a few posts this month where I thought I gave good hints.
In <a href="http://math.stackexchange.com/questions/1371330/">How to scale an unit vector <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24u%24"> in such way that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20u%5ccdot%0a%20%20u%3d1%24"> where <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24"> is a
scalar</a> I think I
did a good job identifying the original author's confusion; he was
conflating his original unit vector <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24u%24"> and the scaled, leading
him to write <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24au%5ccdot%20u%3d1%24">. This is sure to lead to confusion. So
I led him to the point of writing <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%28bv%29%5ccdot%28bv%29%3d1%24"> and let him
take it from there. The other proposed solution is much more rote
and mechanical. (“Divide this by that…”)</p>
<p>In <a href="ttp://math.stackexchange.com/questions/1362089/">Find numbers <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5coverline%7babcd%7d%24"> so that
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5coverline%7babcd%7d%2b%5coverline%7bbcd%7d%2b%5coverline%7bcd%7d%2bd%2b1%3d%5coverline%7bdcba%7d%24"></a>
the OP got stuck partway through and I specifically addressed the
stuckness; other people solved the problem from the beginning. I
think that's the way to go, if the original proposal was never going
to work, especially if you stop and say <em>why</em> it was never going to
work, but this time OP's original suggestion was perfectly good and
she just didn't know how to get to the next step. By the way, the
notation <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5coverline%7babcd%7d%24"> here means the number
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241000a%2b100b%2b10c%2bd%24">.</p>
<p>In <a href="http://math.stackexchange.com/questions/1347223">Help finding the limit of this series <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%7b1%7d%7b4%7d%20%2b%20%20%5cfrac%7b1%7d%7b8%7d%20%2b%20%5cfrac%7b1%7d%7b16%7d%20%2b%20%5cfrac%7b1%7d%7b32%7d%20%2b%20%20%5ccdots%24"></a> it would
have been really easy to say “use the formula” or to analyze the
series de novo, but I think I <em>almost</em> hit the nail on the head
here: it's just like <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%2b%5cfrac12%20%2b%20%5cfrac%7b1%7d%7b4%7d%20%2b%20%5cfrac%7b1%7d%7b8%7d%20%2b%0a%20%20%5cfrac%7b1%7d%7b16%7d%20%2b%20%5cfrac%7b1%7d%7b32%7d%20%2b%20%5ccdots%24">, which I bet OP already
knows, except a little different. But I pointed out the wrong
difference: I observed that the first sequence is one-fourth the
second one (which it is) but it would have been simpler to observe
that it's just the second one without the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%2b%5cfrac12%24">. I had to
review it just now to give the simpler explanation, but I sure wish
I'd thought of it at the time. Nobody else pointed it out either.
Best of all, would have been to mention <em>both</em> methods. If you can
notice both of them you can solve the problem <em>without</em> the advance
knowledge of the value of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%2b%5cfrac12%2b%5cfrac14%2b%5cldots%24">, because you
have <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%244S%20%3d%201%2b%5cfrac12%20%2b%20S%24"> and then solve for <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24S%24">.</p>
<p>In <a href="http://math.stackexchange.com/questions/1358933/">Visualization of Rhombus made of Radii and
Chords</a> it seemed
that OP just needed to see a diagram (“I really really don't see how
two circles can form a rhombus?”), so I drew one. </p></li>
</ul>
tag:blog.plover.com,2015:/math/ounce-of-theory-2Another ounce of theory2015-07-28T14:48:00Z2015-07-28T14:48:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>A few months ago I wrote an article here called <a href="http://blog.plover.com/math/ounce-of-theory.html">an ounce of theory
is worth a pound of search</a> and I
have a nice followup.</p>
<p>When I went looking for that article I couldn't find it, because I
thought it was about how an ounce of search is worth a pound of
theory, and that I was writing a counterexample. I am quite surprised
to discover that that I have several times discussed how a little
theory can replace a lot of searching, and not vice versa, but perhaps
that is because the search is my default.</p>
<p>Anyway, the question came up on math StackExchange today:</p>
<blockquote>
<p>John has 77 boxes each having dimensions 3×3×1. Is it possible for
John to build one big box with dimensions 7×9×11?</p>
</blockquote>
<p>OP opined no, but had no argument. The first answer that appeared was
somewhat elaborate and outlined a computer search strategy which
claimed to reduce the search space to only 14,553 items. (I think the
analysis is wrong, but I agree that the search space is not too
large.)</p>
<p>I almost wrote the search program. I have a program around that is
something like what would be needed, although it is optimized to deal
with a few oddly-shaped tiles instead of many similar tiles, and would
need some work. Fortunately, I paused to think a little before diving
in to the programming.</p>
<div class="bookbox"><table align=right width="14%" bgcolor="#ffffdd" border=1><tr><td align=center>
<font size="-1">Order</font><br>
<cite><font size="-1">How to Solve It</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/0691119663"><IMG SRC="http://www.powells.com/cgi-bin/imageDB.cgi?isbn=0691119663" BORDER="0" ALIGN="center" ALT="How to Solve It" ></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/0691119663"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/0691119663"><font size="-1">no kickback</font></a>
</td></tr></table></div>
<p>For there is an easy answer. Suppose John solved the problem. Look
at just one of the 7×11 faces of the big box. It is a 7×11 rectangle
that is completely filled by 1×3 and 3×3 rectangles. But 7×11 is not
a multiple of 3. So there can be no solution.</p>
<p>Now how did I think of this? It was a very geometric line of
reasoning. I imagined a 7×11×9 carton and imagined putting the small
boxes into the carton. There can be no leftover space; every one of
the 693 cells must be filled. So in particular, we must fill up the
bottom 7×11 layer. I started considering how to pack the bottommost
7×11×1 slice with just the bottom parts of the small boxes and quickly
realized it couldn't be done; there is always an empty cell left over
somewhere, usually in the corner. The argument about considering just
one face of the large box came later; I decided it was clearer than
what I actually came up with.</p>
<p>I think this is a nice example of the Pólya strategy “solve a simpler
problem” from <em>How to Solve It</em>, but I was not thinking of that
specifically when I came up with the solution.</p>
<p>For a more interesting problem of the same sort, suppose you have six
2×2x1 slabs and three extra 1×1×1 cubes. Can you pack the nine pieces
into a 3×3x3 box?</p>
tag:blog.plover.com,2015:/math/se/2015-04Math.SE report 2015-042015-07-19T00:28:00Z2015-07-19T00:28:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>[ Notice: I originally published this report at the wrong URL. I
moved it so that I could publish the <a href="http://blog.plover.com/math/se/2015-06.html">June 2015
report</a> at that URL instead. If you're
seeing this for the second time, you might want to read the June
article instead. ]</p>
<p>A lot of the stuff I've written in the past couple of years has been
on Mathematics StackExchange. Some of it is pretty mundane, but some
is interesting. I thought I might have a little meta-discussion in
the blog and see how that goes. These are the noteworthy posts I made
in April 2015.</p>
<ul>
<li><p><a href="http://math.stackexchange.com/questions/1217598/languages-and-their-relation-help/1217609#1217609">Languages and their relation :
help</a>
is pretty mundane, but interesting for one reason: OP was confused
about a statement in a textbook, and provided a reference, which OPs
don't always do. The text used the symbol <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5csubset%5c_%5cne%24">. OP had
interpreted it as meaning <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cnot%5csubseteq%24">, but I think what was
meant was <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5csubsetneq%24">.</p>
<p>I dug up a copy of the text and groveled over it looking for the
explanation of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5csubset%5c_%5cne%24">, which is not standard. There was
none that I could find. The book even had a section with a glossary
of notation, which didn't mention <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5csubset%5c_%5cne%24">. Math professors
can be assholes sometimes.</p></li>
<li><p><a href="http://math.stackexchange.com/questions/1223920/is-there-an-operation-that-takes-ab-and-ac-and-returns-abc">Is there an operation that takes <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5eb%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5ec%24">, and returns
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5e%7bbc%7d%24"></a>
is more interesting. First off, why is this even a reasonable
question? Why should there be such an operation? But note that
there <em>is</em> an operation that takes <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5eb%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5ec%24"> and returns
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5e%7bb%2bc%7d%24">, namely, multiplication, so it's plausible that the
operation that OP wants might also exist.</p>
<p>But it's easy to see that there is no operation that takes <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5eb%24">
and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5ec%24"> and returns <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5e%7bbc%7d%24">: just observe that although
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%5e2%3d2%5e4%24">, the putative operation (call it <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%24">) should take
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%282%5e4%2c%202%5e4%29%24"> and yield <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%5e%7b4%5ccdot4%7d%20%3d%202%5e%7b16%7d%20%3d%2065536%24">, but it
should also take <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%284%5e2%2c%204%5e2%29%24"> and yield <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%5e%7b2%5ccdot2%7d%20%3d%202%5e4%20%3d%0a%20%20256%24">. So the operation is not well-defined. And you can take this
even further: <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%5e4%24"> can be written as <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24e%5e%7b4%5clog%202%7d%24">, so <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%24">
should also take <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%28e%5e%7b2%5clog%204%7d%2c%20e%5e%7b2%5clog%204%7d%29%24"> and yield
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24e%5e%7b4%28%5clog%204%29%5e2%7d%20%5capprox%202180%2e37%24">.</p>
<p>They key point is that the representation of a number, or even an
integer, in the form <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5eb%24"> is not unique. (Jargon:
"exponentiation is not injective".) You can raise <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5eb%24">, but
having done so you cannot look at the result and know what <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24">
and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24"> were, which is what <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%24"> needs to do.</p>
<p>But if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%24"> can't do it, how can multiplication do it when it
multiplies <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5eb%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5ec%24"> and gets <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5e%7bb%2bc%7d%24">? Does it
somehow know what <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24"> is? No, it turns out that it doesn't need
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24"> in this case. There is something magical going on there,
ultimately related to the fact that if some quantity is increasing
by a factor of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24"> every <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24t%24"> units of time, then there is some
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24t%5c_2%24"> for which it is exactly doubling every <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24t%5c_2%24"> units of
time. Because of this there is a marvelous group homomophism $$\log
: \langle \Bbb R^+, \times\rangle \to \langle \Bbb R ,+\rangle$$ which
can change multiplication into addition <em>without</em> knowing what the
base numbers are.</p>
<p>In that thread I had a brief argument with someone who thinks that
operators apply to expressions rather than to numbers. Well, you
can say this, but it makes the question trivial: you can certainly
have an "operator" that takes <em>expressions</em> <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5eb%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5ec%24"> and
yields the <em>expression</em> <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5e%7bbc%7d%24">. You just can't expect to apply
it to numbers, such as <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2416%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2416%24">, because those numbers are
not expressions in the form <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5eb%24">. I remembered the argument
going on longer than it did; I originally ended this paragraph with
a lament that I wasted more than two comments on this guy, but
looking at the record, it seems that I didn't. Good work,
Mr. Dominus.</p></li>
<li><p><a href="http://math.stackexchange.com/questions/1229986/how-1-0-5-is-equal-to-2/">how 1/0.5 is equal to
2?</a>
wants a simple explanation. Very likely OP is a primary school
student. The question reminds me of a similar question, asking <a href="http://math.stackexchange.com/questions/683774/who-invented-division-and-why-we-do-division-in-those-steps-told/683826#683826">why
the long division algorithm is the way it
is</a>. Each
of these is a failure of education to explain what division is
actually doing. The long division answer is that long division is
an optimization for repeated subtraction; to divide <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24450%5cdiv%203%24">
you want to know how many shares of three cookies each you can get
from <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24450%24"> cookies. Long division is simply a notation for
keeping track of removing <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24100%24"> shares, leaving <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24150%24"> cookies,
then <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%245%5ccdot%2010%24"> further shares, leaving none.</p>
<p>In this question there was a similar answer. <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%2f0%2e5%24"> is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%24">
because if you have one cookie, and want to give each kid a share
of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%2e5%24"> cookies, you can get out two shares. Simple enough.</p>
<p>I like division examples that involve giving cookies to kids,
because cookies are easy to focus on, and because the motivation for
equal shares is intuitively understood by everyone who has kids, or
who has been one.</p>
<p>There is a general pedagogical principle that an ounce of examples
are worth a pound of theory. My answer here is a good example of
that. When you explain the theory, you're telling the student how
to understand it. When you give an example, though, if it's the
right example, the student can't help but understand it, and when
they do they'll understand it in their own way, which is better than
if you told them how.</p></li>
<li><p><a href="http://math.stackexchange.com/questions/1229755/how-to-read-a-cycle-graph/">How to read a cycle
graph?</a>
is interesting because hapless OP is asking for an explanation of a
particularly strange diagram from Wikipedia. I'm familiar with the
eccentric Wikipedian who drew this, and I was glad that I was around
to say "The other stuff in this diagram is nonstandard stuff that
the somewhat eccentric author made up. Don't worry if it's not
clear; this author is notorious for that."</p></li>
<li><p>In <a href="http://math.stackexchange.com/questions/1257313/expected-number-of-die-tosses-to-get-something-less-than-5">Expected number of die tosses to get something less than
5</a>,
OP calculated as follows: The first die roll is a winner <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac23%24">
of the time. The second roll is the first winner
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac13%5ccdot%5cfrac23%24"> of the time. The third roll is the first
winner <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac13%5ccdot%5cfrac13%5ccdot%5cfrac23%24"> of the time. Summing the series
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5csum_n%20%5cfrac23%5cleft%28%5cfrac13%5cright%29%5enn%24"> we eventually obtain the
answer, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac32%24">. The accepted answer does it this way also.</p>
<p>But there's a much easier way to solve this problem. What we really
want to know is: how many rolls before we expect to have seen one
good one? And the answer is: the expected number of winners per die
roll is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac23%24">, expectations are additive, so the expected
number of winners per <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> die rolls is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac23n%24">, and so we
need <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d%5cfrac32%24"> rolls to expect one winner. Problem solved!</p>
<p>I first discovered this when I was around fifteen, <a href="http://blog.plover.com/oops/trivial.html">and wrote about
it here a few years ago</a>.</p>
<p><a href="http://blog.plover.com/math/algebra.html">As I've mentioned
before</a>, this is
one of the best things about mathematics: not that it works, but
that you can do it by whatever method that occurs to you and you get
the same answer. This is where mathematics pedagogy goes wrong most
often: it proscribes that you must get the answer by method X,
rather than that you must get the answer by hook or by crook. If
the student uses method Y, and it works (and if it is correct) that
should be worth full credit.</p>
<p>Bad instructors always say "Well, we need to test to see if the
student knows method X." No, we should be testing to see if the
student can solve problem P. If we are testing for method X, that
is a failure of the test or of the curriculum. Because if method X
is useful, it is useful because for some problems, it is the only
method that works. It is the instructor's job to find one of these
problems and put it on the test. If there is no such problem, then
X is useless and it is the instructor's job to omit it from the
curriculum. If Y always works, but X is faster, it is the
instructor's job to explain this, and then to assign a problem for
the test where Y would take more time than is available.</p>
<p>I see now <a href="http://blog.plover.com/math/484848.html">I wrote the same thing in
2006</a>. It bears repeating.
<a href="http://math.stackexchange.com/questions/331231/what-quantifies-as-a-rigorous-proof/331235#comment715387_331235">I also said it again a couple of years ago on math.se
itself</a>
in reply to a similar comment by Brian Scott:</p>
<blockquote>
<p>If the goal is to teach students how to write proofs by induction,
the instructor should damned well come up with problems for which
induction is the best approach. And if even then a student comes
up with a different approach, the instructor should be
pleased. ... The directions <strong>should not begin</strong> [with "prove by
induction"]. I consider it a failure on the part of the instructor
if he or she has to specify a technique in order to give students
practice in applying it.</p>
</blockquote></li>
</ul>
tag:blog.plover.com,2015:/math/logic/annoying-boxes-solutionThe annoying boxes puzzle: solution2015-07-03T12:15:00Z2015-07-03T12:15:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<a href="http://blog.plover.com/math/logic/annoying-boxes.html">I presented this logic puzzle on Wednesday</a>:<p>
<blockquote style="background-color: #ffccff;">
There are two boxes on a table, one red and one green. One contains a
treasure. The red box is labelled "exactly one of the labels is
true". The green box is labelled "the treasure is in this box."<p>
Can you figure out which box contains the treasure?<p>
</blockquote>
It's not too late to try to solve this before reading on. If you
want, you can submit your answer here:<p>
<form method=GET action="http://perl.plover.com/annoying-boxes.cgi">
<input type=radio name="r" value="red">The treasure is in the red box<br>
<input type=radio name="r" value="green">The treasure is in the green box<br>
<input type=radio name="r" value="wut">There is not enough information to determine the answer<br>
<input type=radio name="r" value="other">Something else: <input type=text name="o" size=50><br>
<input type=submit value="Submit Solution">
</form>
<h3>Results</h3>
<blockquote><div style="font-size: 100%"> There were 506 total
responses up to Fri Jul 3 11:09:52 2015 UTC; I kept only the first
response from each IP address, leaving 451. I read all the "something
else" submissions and where it seemed clear I recoded them as votes
for "red", for "not enough information", or as spam. (Several people
had the right answer but submitted "other" so they could explain
themselves.) There was also one post attempted to attack my
(nonexistent) SQL database. Sorry, Charlie; I'm not as stupid as I
look.</div></blockquote><p>
<pre>
66.52% 300 red
25.72 116 not-enough-info
3.55 16 green
2.00 9 other
1.55 7 spam
0.44 2 red-with-qualification
0.22 1 attack
100.00 451 TOTAL
</pre>
<div style="font-size: 150%"><b>One-quarter</b> of respondents got
the <b>right</b> answer, that there is <b>not enough information</b>
given to solve the problem, <b>Two-thirds</b> of respondents said the
treasure was in the <span style="color: red"><b>red</b></span> box.
This is <span style="color: red"><b>wrong</b></span>. <b>The treasure
is in the <span style="color: green">green</span> box.</b></div><p>
<h3>What?</h3>
Let me show you. I stated:<p>
<blockquote> <div style="font-size: 122%">There are two boxes on a
table, one red and one green. One contains a treasure. The red box
is labelled "exactly one of the labels is true". The green box is
labelled "the treasure is in this box."</div></blockquote><p>
<p align=center><a href="http://pic.blog.plover.com/math/logic/annoying-boxes-solution/boxesclosed.jpg"><img src="http://pic.blog.plover.com/math/logic/annoying-boxes-solution/boxesclosed-sm.jpg" border=0 /></a></p>
The labels are as I said. Everything I told you was literally true.<p>
The treasure is definitely not in the red box.<p>
<p align=center><a href="http://pic.blog.plover.com/math/logic/annoying-boxes-solution/redboxopen.jpg"><img src="http://pic.blog.plover.com/math/logic/annoying-boxes-solution/redboxopen-sm.jpg" border=0 /></a></p>
No, it is actually in the green box.<p>
<p align=center><a href="http://pic.blog.plover.com/math/logic/annoying-boxes-solution/boxesopen.jpg"><img src="http://pic.blog.plover.com/math/logic/annoying-boxes-solution/boxesopen-sm.jpg" border=0 /></a></p>
(It's hard to see, but one of the items in the green box is the gold
and diamond ring made in Vienna by my great-grandfather, which is
unquestionably a real treasure.)<p>
So if you said the treasure must be in the red box, you were simply
mistaken. If you had a logical argument why the treasure had to be in
the red box, your argument was fallacious, and you should pause and try
to figure out what was wrong with it.<p>
I will discuss it in detail below.<p>
<h3>Solution</h3>
The treasure is undeniably in the green box. However, correct answer to the
puzzle is "no, you cannot figure out which box contains the
treasure". There is not enough information given. (Notice that the
question was not “Where is the treasure?” but “Can you figure out…?”)
<p>
<h3>(Fallacious) Argument <i>A</i></h3>
Many people erroneously conclude that the treasure is in the red box,
using reasoning something like the following:<p>
<ol>
<li>Suppose the red label is true. Then exactly one label is true,
and since the red label is true, the green label is false. Since it
says that the treasure is in the green box, the treasure must really
be in the red box.
<li>Now suppose that the red label is false. Then the green label
must also be false. So again, the treasure is in the red box.
<li>Since both cases lead to the conclusion that the treasure is in
the red box, that must be where it is.
</ol>
<h3>What's wrong with argument <i>A</i>?</h3>
Here are some responses people commonly have when I tell them that
argument <i>A</i> is fallacious:<p>
<p align=center><b>"If the treasure is in the green box, the red label is lying."</b></p>
Not quite, but argument <i>A</i> explicitly considers the possibility
that the red label was false, so what's the problem?<p>
<p align=center><b>"If the treasure is in the green box, the red label is
inconsistent."</b></p>
It could be. Nothing in the puzzle statement ruled this out. But actually it's not inconsistent, it's just irrelevant.<p>
<p align=center><b>"If the treasure is in the green box, the red label is
meaningless."</b></p>
Nonsense. The meaning is plain: it says “exactly one of these labels is
true”, and the meaning is that exactly one of the labels is true.
Anyone presenting argument <i>A</I> must have understood the label to
mean that, and it is incoherent to understand it that way and then
to turn around and say that it is meaningless! (<a href="http://blog.plover.com/math/logic/contradictions.html">I discussed this point in more detail in 2007.)</a><p>
<p align=center><b>"But the treasure <i>could</i> have been in the red box."</b></p>
True! But it is not, as you can see in the pictures. The puzzle does
not give enough information to solve the problem. If you said that
there was not enough information, then congratulations, you have the
right answer. The answer produced by argument <i>A</i> is
incontestably wrong, since it asserts that the treasure is in the red
box, when it is not.<p>
<p align=center><b>"The conditions supplied by the puzzle statement are inconsistent."</b></p>
They certainly are not. Inconsistent systems do not have models, and
in particular cannot exist in the real world. The photographs above
demonstrate a real-world model that satisfies every condition posed
by the puzzle, and so proves that it is consistent.<p>
<p align=center><b>"But that's not fair! You could have made up any random garbage at all, and then told me afterwards that you had been lying."</b></p>
Had I done that, it <i>would</i> have been an unfair puzzle. For
example, suppose I opened the boxes at the end to reveal that there
was no treasure at all. That would have directly contradicted my
assertion that "One [box] contains a treasure". That would have been
<i>cheating</i>, and I would deserve a kick in the ass.<p>
But I did <i>not</i> do that. As the photograph shows, the boxes,
their colors, their labels, and the disposition of the treasure are
all exactly as I said. I did not make up a lie to trick you; I described a real
situation, and asked whether people they could diagnose the location of
the treasure.<p>
(Two respondents accused me of making up lies. One said:<blockquote>There is no
treasure. Both labels are lying. Look at those boxes. Do you really
think someone put a treasure in one of them just for this logic
puzzle? </blockquote> What can I say? I <i>did</i> put a treasure in a box just for this logic puzzle. Some of us just have higher
standards.)<p>
<p align=center><b>"But what about the labels?"</b></p>
Indeed! What about the labels?<p>
<h3>The labels are worthless</h3>
The labels are red herrings; the provide no information. Consider the
following version of the puzzle:<p>
<blockquote style="background-color: #ffccff;">
There are two boxes on a table, one red and one green. One contains a
treasure. <!-- <s>The red box is labelled "exactly one of the labels is
true". The green box is labelled "the treasure is in this box."</s> --><p>
Which box contains the treasure?<p>
</blockquote>
Obviously, the problem cannot be solved from the information given.<p>
Now consider this version:<p>
<blockquote style="background-color: #ffccff;"> There are two boxes on
a table, one red and one green. One contains a treasure. The red box
is labelled "gcoadd atniy fnck z fbi c rirpx hrfyrom". The green box
is labelled "ofurb rz bzbsgtuuocxl ckddwdfiwzjwe ydtd."</s><p>
Which box contains the treasure?<p>
</blockquote>
One is similarly at a loss here.<p>
(By the way, people who said one label was meaningless: this is what a
meaningless label looks like.)<p>
<blockquote style="background-color: #ffccff;">
There are two boxes on a table, one red and one green. One contains a
treasure. The red box is labelled "exactly one of the labels is
true". The green box is labelled "the treasure is in this box."<p>
But then the janitor happens by. "Don't be confused by those labels,"
he says. "They were stuck on there by the previous owner of the
boxes, who was an illiterate shoemaker who only spoke Serbian. I
think he cut them out of a magazine because he liked the frilly borders."<p>
Which box contains the treasure?<p>
</blockquote>
The point being that in the absence of additional information, there
is no reason to believe that the labels give any information about the
contents of the boxes, or about labels, or about anything at all.
This should not come as a surprise to anyone. It is true not just in
annoying puzzles, but in the world in general. A box labeled “fresh figs” might contain fresh figs, or spoiled figs, or angry hornets, or nothing at all.
<div class="bookbox"><table align=right width="14%" bgcolor="#ffffdd" border=1><tr><td align=center>
<font size="-1">Order</font><br>
<cite><font size="-1">What is the Name of this Book?</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/0671628321"><IMG SRC="http://www.powells.com/cgi-bin/imageDB.cgi?isbn=0671628321" BORDER="0" ALIGN="center" ALT="What is the Name of this Book?" ></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/0671628321"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/0671628321"><font size="-1">no kickback</font></a>
</td></tr></table></div>
<h3>Why doesn't every logic puzzle fall afoul of this problem?</h3>
I said as part of the puzzle conditions that there was a treasure in
one box. For a fair puzzle, I am required to tell the truth about the
puzzle conditions. Otherwise I'm just being a jerk.<p>
Typically the truth or falsity of the labels
<b>is part of the puzzle conditions</b>. Here's a typical example,
which I took from Raymond Smullyan's <cite>What is the name of this
book?</cite> (problem 67a):<p>
<blockquote style="background-color: #ffccff;">
… She had the following inscriptions put on the caskets:
<table>
<tr><th>Gold<th>Silver<th>Lead
<tr>
<td align=center>THE PORTRAIT IS IN THIS CASKET
<td align=center>THE PORTRAIT IS NOT IN THIS CASKET
<td align=center>THE PORTRAIT IS NOT IN THE GOLD CASKET
</table>
<b>Portia explained to the suitor that of the three statements, at most one was true.</b><p> Which casket should the suitor choose [to find the portrait]?<p>
</blockquote>
Notice that the problem condition gives the suitor a certification
about the truth of the labels, on which he may rely. In the quotation
above, the certification is in boldface.<p>
A well-constructed puzzle will always contain such a certification,
something like “one label is true and one is false” or “on this
island, each person always lies, or always tells the truth”. I went to
<cite>What is the Name of this Book?</cite> to get the example above, and found
more than I had bargained for: problem 70 is exactly the annoying boxes problem!
Smullyan says:<p>
<blockquote>
Good heavens, I can take any number of caskets that I please and put
an object in one of them and then write any inscriptions at all on the
lids; these sentences won't convey any information whatsoever.
</blockquote>
(Page 65)<p>
Had I known ahead of time that Smullyan had treated the exact same
topic with the exact same example, I doubt I would have written this
post at all.<p>
<h3>But why is this so surprising?</h3>
I don't know.<p>
<h3>Final notes</h3>
16 people correctly said that the treasure was in the green box. This
has to be counted as a lucky guess, unacceptable as a solution to a
logic puzzle.<p>
One respondent referred me to <a
href="http://lesswrong.com/lw/ne/the_parable_of_the_d/">a similar
post on lesswrong</a>.<p>
I did warn you all that the puzzle was annoying.<p>
I started writing this post in October 2007, and then it sat on the
shelf until I got around to finding and photographing the boxes. A
triumph of procrastination!<p>
[ Addendum 20150911: Steven Mazie has written a blog article about
this topic,
<a href="http://bigthink.com/praxis/a-logic-puzzle-that-teaches-a-life-lesson">A Logic Puzzle That Teaches a Life Lesson</a>. ]
tag:blog.plover.com,2015:/math/logic/annoying-boxesThe annoying boxes puzzle2015-07-01T15:13:00Z2015-07-01T15:13:00ZMark Dominushttp://www.plover.com/mjd@plover.com
Here is a logic puzzle. I will present the solution on Friday.<p>
<blockquote style="background-color: #ffccff;">
There are two boxes on a table, one red and one green. One contains a
treasure. The red box is labelled "exactly one of the labels is
true". The green box is labelled "the treasure is in this box."<p>
Can you figure out which box contains the treasure?<p>
</blockquote>
<form method=GET action="http://perl.plover.com/annoying-boxes.cgi">
<input type=radio name="r" value="red">The treasure is in the red box<br>
<input type=radio name="r" value="green">The treasure is in the green box<br>
<input type=radio name="r" value="wut">There is not enough information to determine the answer<br>
<input type=radio name="r" value="other">Something else: <input type=text name="o" size=50><br>
<input type=submit value="Submit Solution">
</form>
Starting on 2015-07-03, <a
href="http://blog.plover.com/math/logic/annoying-boxes-solution.html">the solution
will be here</a>.<p
tag:blog.plover.com,2015:/math/se/2015-05Math.SE report 2015-052015-06-19T03:01:00Z2015-06-19T03:01:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>A lot of the stuff I've written in the past couple of years has been
on math.StackExchange. Some of it is pretty mundane, but some is
interesting. My summary of April's interesting posts was
well-received, so here are the noteworthy posts I made in May 2015.</p>
<ul>
<li><p><a href="http://math.stackexchange.com/questions/1267062/">What matrix transforms <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%281%2c0%29%24"> into <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%282%2c6%29%24"> and tranforms
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%280%2c1%29%24"> into
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%284%2c8%29%24">?</a> was a
little funny because the answer is $$\begin{pmatrix}2 & 4 \\ 6 & 8
\end{pmatrix}$$ and yeah, it works exactly like it appears to,
there's no trick. But if I just told the guy that, he might feel
unnecessarily foolish. I gave him a method for solving the problem
and figured that when he saw what answer he came up with, he might
learn the thing that the exercise was designed to teach him.</p></li>
<li><p><a href="http://math.stackexchange.com/questions/1118286/is-a-network-topology-a-topological-space/">Is a “network topology'” a topological
space?</a>
is interesting because several people showed up right away to say
no, it is an abuse of terminology, and that network topology really
has nothing to do with mathematical topology. Most of those comments
have since been deleted. My answer was essentially: it is
topological, because just as in mathematical topology you care about
which computers are connected to which, and not about where any of
the computers actually are.</p>
<p>Nobody constructing a token ring network thinks that it has to be a
geometrically circular ring. No, it only has to be a <em>topologically</em>
circular ring. A square is fine; so is a triangle; topologically
they are equivalent, both in networking and in mathematics. The
wires can cross, as long as they don't connect at the crossings.
But if you use something that isn't <em>topologically</em> a ring, like say
a line or a star or a tree, the network doesn't work.</p>
<p>The term “topological” is a little funny. “Topos” means “place”
(like in “topography” or “toponym”) but in topology you don't care
about places.</p></li>
<li><p><a href="http://math.stackexchange.com/questions/1281319/">Is there a standard term for this generalization of the Euler
totient function?</a>
was asked by me. I don't include all my answers in these posts, but
I think maybe I should have a policy of including all my questions.
This one concerned a simple concept from number theory which I was
surprised had no name: I wanted <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cphi_k%28n%29%24"> to be the number of
integers <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24m%24"> that are no larger than <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> for which <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cgcd%28m%2cn%29%20%3d%0a%20%20k%24">. For <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%3d1%24"> this is the famous Euler totient function, written
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cvarphi%28n%29%24">.</p>
<p>But then I realized that the reason it has no name is that it's
simply <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cphi_k%28n%29%20%3d%20%5cvarphi%5cleft%28%5cfrac%20n%20k%5cright%29%24"> so there's no need
for a name or a special notation.</p>
<p>As often happens, I found the answer myself shortly after I asked
the question. I wonder if the reason for this is that my time to
come up with the answer is Poisson-distributed. Then if I set a time
threshold for how long I'll work on the problem before asking about
it, I am likely to find the answer to almost any question that
exceeds the threshold shortly after I exceed the threshold. But if
I set the threshold higher, this would <em>still</em> be true, so there is
no way to win this particular game. Good feature of this theory: I
am off the hook for asking questions I could have answered myself.
Bad feature: no real empirical support.</p></li>
<li><p><a href="http://math.stackexchange.com/questions/1282934/">how many ways can you divide 24 people into groups of
two?</a> displays a
few oddities, and I think I didn't understand what was going on at
that time. OP has calculated the first few special cases:</p>
<blockquote>
<p>1:1 2:1 3:3 4:3 5:12 6:15</p>
</blockquote>
<p>which I think means that there is one way to divide 2 people into
groups of 2, 3 ways to divide 4 people, and 15 ways to divide 6
people. This is all correct! But what could the 1:1, 3:3, 5:12
terms mean? You simply can't divide 5 people into groups of 2.
Well, maybe OP was counting the extra odd person left over as a sort
of group on their own? Then odd values would be correct; I didn't
appreciate this at the time.</p>
<p>But having calculated 6 special cases correctly, why can't OP
calculate the seventh? Perhaps they were using brute force: the
next value is 48, hard to brute-force correctly if you don't have a
enough experience with combinatorics.</p>
<p>I tried to suggest a general strategy: look at special cases, and
not by brute force, but try to <em>analyze</em> them so that you can come
up with a method for solving them. The method is unnecessary for
the small cases, where brute force enumeration suffices, but you can
use the brute force enumeration to check that the method is
working. And then for the larger cases, where brute force is
impractical, you use your method.</p>
<p>It seems that OP couldn't understand my method, and when they tried
to apply it, got wrong answers. Oh well, you can lead a horse to
water, etc.</p>
<p>The other pathology here is:</p>
<blockquote>
<p>I think I did what you said and I got 1.585times 10 to the 21</p>
</blockquote>
<p>for the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d24%24"> case. The correct answer is
$$23\cdot21\cdot19\cdot17\cdot15\cdot13\cdot11\cdot9\cdot7\cdot5\cdot3\cdot1
= 316234143225 \approx 3.16\cdot 10^{11}.$$ OP didn't explain how
they got <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%2e585%5ccdot10%5e%7b21%7d%24"> so there's not much hope of
correcting their weird error.</p>
<p>This is someone who probably could have been helped in person, but
on the Internet it's hopeless. Their problems are Internet
communication problems.</p></li>
<li><p><a href="http://math.stackexchange.com/questions/1289531/">Lambda calculus
typing</a> isn't
especially noteworthy, but I wrote a fairly detailed explanation of
the algorithm that Haskell or SML uses to find the type of an
expression, and that might be interesting to someone.</p></li>
<li><p>I think <a href="http://math.stackexchange.com/questions/1290948/">Special representation of a
number</a> is the
standout post of the month. OP speculates that, among numbers of
the form <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24pq%2brs%24"> (where <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24p%2cq%2cr%2cs%24"> are prime), the choice of
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24p%2cq%2cr%2cs%24"> is unique. That is, the mapping <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%0a%20%20p%2cq%2cr%2cs%5crangle%20%5cto%20pq%2brs%24"> is reversible.</p>
<p>I was able to guess that this was not the case within a couple of
minutes, replied pretty much immediately:</p>
<blockquote>
<p>I would bet money against this representation being unique. </p>
</blockquote>
<p>I was sure that a simple computer search would find
counterexamples. In fact, the smallest is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2411%5ccdot13%20%2b%2019%5ccdot%2029%0a%20%20%3d%2011%5ccdot%2043%20%2b%2013%5ccdot%2017%20%3d%20694%24"> which is small enough that you
could find it without the computer if you are patient.</p>
<p>The obvious lesson to learn from this is that many elementary
conjectures of this type can be easily disproved by a trivial
computer search, and I frequently wonder why more amateur
mathematicians don't learn enough computer programming to
investigate this sort of thing. (I wrote recently on the topic of
<a href="http://blog.plover.com/math/ounce-of-theory.html">An ounce of theory is worth a pound of search
</a>, and this is an interesting
counterpoint to that.)</p>
<p>But the most interesting thing here is how I was able to instantly
guess the answer. I explained in some detail in the post. But the
basic line of reasoning goes like this.</p>
<p>Additive properties of the primes are always distributed more or
less at random unless there is some obvious reason why they can't
be. For example, let <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24p%24"> be prime and consider <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242p%2b1%24">. This
must have exactly one of the three forms <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243n%2d1%2c%203n%2c%24"> or <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243n%2b1%24">
for some integer <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24">. It obviously has the form <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243n%2b1%24"> almost
never (the only exception is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24p%3d3%24">). But of the other two forms
there is no obvious reason to prefer one over the other, and indeed
of the primes up to 10,000, 611 are of the type <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243n%24"> and and 616
are of the type <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243n%2d1%24">.</p>
<p>So we should expect the value <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24pq%2brs%24"> to be distributed more or
less randomly over the set of outputs, because there's no obvious
reason why it couldn't be, except for simple stuff, like that it's
obviously almost always even. <!-- (And some similar analogous
properties; It has the form <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%246n%2b2%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%246n%2b4%24"> equally often, and
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%246n%24"> twice as often as either.) --></p>
<p>So we are throwing a bunch of balls at random into bins, and the
claim is that no bin should contain more than one ball. For that to
happen, there must be vastly more bins than balls. But the bins are
numbers, and primes are not at all uncommon among numbers, so the
number of bins <em>isn't</em> vastly larger, and there ought to be at least
some collisions. </p>
<p>In fact, a more careful analysis, which I wrote up on the site,
shows that the number of <em>balls</em> is vastly larger—to have them be
roughly the same, you would need primes to be roughly as common as
perfect squares, but they are far more abundant than that—so as you
take larger and larger primes, the number of collisions increases
enormously and it's easy to find twenty or more quadruples of primes
that all map to the same result. But I was able to predict this
after a couple of minutes of thought, from completely elementary
considerations, so I think it's a good example of Lower Mathematics
at work.</p>
<p>This is an example of a fairly common pathology of math.se
questions: OP makes a conjecture that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> never occurs or that
there are no examples with property <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24">, when actually <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24">
almost always occurs or <em>every</em> example has property <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24">.</p>
<p>I don't know what causes this. Rik Signes speculates that it's just
wishful thinking: OP is doing some project where it would be useful
to have <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24pq%2brs%24"> be unique, so posts in hope that someone will tell
them that it is. But there was nothing more to it than baseless
hope. Rik might be right.</p></li>
</ul>
<p>[ Addendum 20150619: A previous version of this article included the delightful typo “mathemativicians”. ]</p>
tag:blog.plover.com,2015:/math/se/2015-06Math.SE report 2015-062015-06-14T15:23:00Z2015-06-14T15:23:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>[ This page originally held <a href="http://blog.plover.com/math/se/2015-04.html">the report for April
2015</a>, which has moved. It now contains
the report for June 2015. ]</p>
<ul>
<li><p><a href="http://math.stackexchange.com/q/1310144/25554">Is “smarter than” a transitive
relationship?</a>
concerns a hypothetical "is smarter than" relation with the
following paradoxical-seeming property:</p>
<blockquote>
<p>most X's are smarter than most Y's, but most Y's are such that it
is not the case that most X's are smarter than it.</p>
</blockquote>
<p>That is, if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cmathsf%20Mx%2e%5cPhi%28x%29%24"> means that most <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24"> have property
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cPhi%24">, then we want both $$\mathsf Mx.\mathsf My.S(x, y)$$ and
also $$\mathsf My.\mathsf Mx.\lnot S(x, y).$$</p>
<p>“Most” is a little funny here: what does it mean? But we can pin it
down by supposing that there are an infinite number of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24">es and
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24y%24">s, and agreeing that most <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24"> have property <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> if there
are only a finite number of exceptions. For example, everyone
should agree that most positive integers are larger than 7 and that
most prime numbers are odd. The jargon word here is that we are
saying that a subset contains “most of” the elements of a larger set
if it is <em>cofinite</em>.</p>
<p>There is a model of this property, and OP reports that they asked
the prof if this was because the "smarter than" relation <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24S%28x%2cy%29%24">
could be antitransitive, so that one might have <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24S%28x%2cy%29%2c%20S%28y%2cz%29%24">
but also <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24S%28z%2cx%29%24">. The prof said no, it's not because of that,
but the OP want so argue that it's that anyway. But no, it's not
because of that; there is a model that uses a perfectly simple
transitive relation, and the nontransitive thing nothing but a
distraction. (The model maps the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24">es and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24y%24">s onto numbers,
and says <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24"> is smarter than <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24y%24"> if its number is bigger.)
Despite this OP couldn't give up the idea that the model exists
because of intransitive relations. It's funny how sometimes people
get stuck on one idea and can't let go of it.</p></li>
<li><p><a href="http://math.stackexchange.com/q/1314460/25554">How to generate a random number between 1 and 10 with a six-sided
die?</a> was a lot of
fun and attracted several very good answers. Top-scoring is Jack
D'Aurizio's, which proposes a completely straightforward method:
roll once to generate a bit that selects <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24N%3d0%24"> or <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24N%3d5%24">, and
then roll again until you get <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24M%5cne%206%24">, and the result is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24N%2bM%24">.</p>
<p>But several other answers were suggested, including two by me, <a href="http://math.stackexchange.com/a/1314560/25554">one
explaining the general technique of arithmetic
coding</a>, which I'll
probably refer back to in the future when people ask similar
questions. Don't miss <a href="http://math.stackexchange.com/a/1315056/25554">NovaDenizen's clever simplification of
arithmetic coding</a>,
which I want to think about more, or D'Aurizio's suggestion that if
you threw the die into a V-shaped trough, it would land with one
edge pointing up and thus select a random number from 1 to 12 in a
single throw.</p>
<p>Interesting question: Is there an easy-to-remember mapping from
edges to numbers from 1–12? Each edge is naturally identified by a
pair of distinct integers from 1–6 that do not add to 7.</p></li>
<li><p>The oddly-phrased <a href="http://math.stackexchange.com/q/1320337/25554">Category theory with objects as logical
expressions over <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%7b%5cvee%2c%5cwedge%2c%5cneg%5c%7d%24"> and morphisms
as?</a> asks if there is
a standard way to turn logical expressions into a category, which
there is: you put an arrow from <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%5cto%20B%24"> for each proof that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">
implies <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%24">; composition of arrows is concatenation of proofs, and
identity arrows are empty proofs. The categorial product,
coproduct, and exponential then correspond to <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cland%2c%20%5clor%2c%20%24"> and
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cto%24">. </p>
<p>This got me thinking though. Proofs are properly not lists, they are
trees, so it's not entirely clear what the concatenation operation
is. For example, suppose proof <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> concludes <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> at its root
and proof <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24Y%24"> assumes <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> in more than one leaf. When you
concatenate <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24Y%24"> do you join all the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">'s, or what? I
really need to study this more. Maybe the Lambek and Scott book
talks about it, or maybe the Goldblatt Topoi book, which I actually
own. I somehow skipped most of the Cartesian closed category stuff,
which is an oversight I ought to correct.</p></li>
<li><p>In <a href="http://math.stackexchange.com/q/1321233/25554">Why is the Ramsey`s theorem a generalization of the Pigeonhole
principle</a> I gave
what I thought was a terrific answer, showing how Ramsey's graph
theorem and the pigeonhole principle are both special cases of
Ramsey's hypergraph theorem. This might be my favorite answer of
the month. It got several upvotes, but OP preferred a different
answer, with fewer details.</p>
<p>There was <a href="http://math.stackexchange.com/q/1341922/25554">a thread a while
back</a> about theorems
which are generalizations of other theorems in non-obvious ways. I
pointed out the Yoneda lemma was a generalization of Cayley's
theorem from group theory. I see that nobody mentioned the Ramsey
hypergraph theorem being a generalization of the pigeonhole
principle, but it's closed now, so it's too late to add it.</p></li>
<li><p>In <a href="http://math.stackexchange.com/q/1341842/25554">Why does the Deduction Theorem use
Union?</a> I explained
that the English word <i>and</i> actually has multiple meanings. I know I've
seen this discussed in elementary logic texts but I don't remember
where.</p></li>
<li><p>Finally, <a href="http://math.stackexchange.com/q/1341922/25554">Which is the largest power of natural number that can be
evaluated by
computers?</a> asks if
it's possible for a computer to calculate <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%247%5e%7b120000000000%7d%24">. The
answer is yes, but it's nontrivial and you need to use some tricks.
You have to use the multiplying-by-squaring trick, and for the
squarings you probably want to do the multiplication with DFT. OP
was dissatistifed with the answer, and seemed to have some axe to
grind, but I couldn't figure out what it was.</p></li>
</ul>
tag:blog.plover.com,2015:/math/rectanglesRectangles with equal area and perimeter2015-03-20T20:40:00Z2015-03-20T20:40:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>Wednesday while my 10-year-old daughter Katara was doing her math
homework, she observed with pleasure that a <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%246%c3%973%24"> rectangle has a
perimeter of 18 units and also an area of 18 square units. I
mentioned that there was an infinite family of such
rectangles, and, after a small amount of tinkering, that the only
other such rectangle with integer sides is a <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%c3%974%24"> square, so in a
sense she had found the single interesting example. She was very interested
in how I knew this, and I promised to
show her how to figure it out once she finished her homework. She
didn't finish before bedtime, so we came back to it the following evening.</p>
<p>This is just one of many examples of how she has way too much
homework, and how it interferes with her education.</p>
<p>She had already remarked that she knew how to write an equation
expressing the condition she wanted, so I asked her to do that; she
wrote $$(L×W) = ([L+W]×2).$$ I remember being her age and using all
different shapes of parentheses too. I suggested that she should
solve the equation for <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%24">, getting <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%24"> on one side and a bunch of
stuff involving <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24L%24"> on the other, but she wasn't sure how to do it,
so I offered suggestions while she moved the symbols around,
eventually obtaining $$W = 2L\div (L-2).$$ I would have written it as
a fraction, but getting the right answer is important, and using
the same notation I would use is much less so, so I didn't say anything.</p>
<p>I asked her to plug in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24L%3d3%24"> and observe that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%3d6%24"> popped right
out, and then similarly that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24L%3d6%24"> yields <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%3d3%24">, and then I asked
her to try the other example she knew. Then I suggested that she see
what <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24L%3d5%24"> did: it gives <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%3d%5cfrac%7b10%7d3%24">, This was new, so she
checked it by calculating the area and the perimeter, both
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%7b50%7d3%24">. She was very excited by this time. <a href="http://blog.plover.com/math/algebra.html">As I have
mentioned earlier</a>, algebra is magical in
its ability to mechanically yield answers to all sorts of
questions. Even after thirty years I find it astonishing and
delightful. You set up the equations, push the symbols around, and
all sorts of stuff pops out like magic. Calculus is somehow much less
astonishing; the machinery is all explicit. But how does algebra
work? I've been thinking about this on and off for a long time and
I'm still not sure.</p>
<p>At that point I took over because I didn't think I would be able to
guide her through the next part of the problem without a
demonstration; I wanted to graph the function <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%3d2L%5cdiv%28L%2d2%29%24"> and she
does not have much experience with that. She put in the five points
we already knew, which already lie on a nice little curve, and then
she asked an incisive question: does it level off, or does it keep
going down, or what? We discussed what happens when <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24L%24"> gets close to
2; then <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%24"> shoots up to infinity. And when <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24L%24"> gets big, say a
million, you can see from the algebra that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%24"> is a hair more than
2. So I drew in the asymptotes on the hyperbola. </p>
<p align=center><a href="http://pic.blog.plover.com/math/rectangles/plot.png"><img border=0 src="http://pic.blog.plover.com/math/rectangles/plot-th.png"></a></p>
<p><a href="http://pic.blog.plover.com/math/rectangles/holladay1.jpg"><img border=0 align=right src="http://pic.blog.plover.com/math/rectangles/holladay1-th.jpg"></a></p>
<p>Katara is not yet
familiar with hyperbolas. (She has known about parabolas since she
was tiny. I have a very fond memory of visiting Portland with her
when she was almost two, and we entered Holladay park, which has
fountains that squirt out of the ground. Seeing the water arching up
before her, she cried delightedly “parabolas!”)</p>
<p><br clear=right></p>
<p>Once you know how the graph behaves, it is a simple matter to see that
there are no integer solutions other than <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%203%2c6%5crangle%2c%0a%5clangle%204%2c4%5crangle%2c%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle6%2c3%5crangle%24">. We know that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24L%3d5%24">
does not work. For <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24L%3e6%24"> the value of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%24"> is always strictly
between <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%24">. For <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24L%3d2%24"> there is no value of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%24"> that works at
all. For <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%5clt%20L%5clt%202%24"> the formula says that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%24"> is negative, on the
other branch of the hyperbola, which is a perfectly good <em>numerical</em>
solution (for example, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24L%3d1%2c%20W%3d%2d2%24">) but makes no sense as the width of
a rectangle. So it was a good lesson about how mathematical modeling
sometimes introduces solutions that are wrong, and how you have to
translate the solutions back to the original problem to see if they
make sense.</p>
<p>[ Addendum 20150330: Thanks to Steve Hastings for his plot of the
hyperbola, which is in the public domain. ]</p>
tag:blog.plover.com,2015:/math/ounce-of-theoryAn ounce of theory is worth a pound of search2015-03-19T17:21:00Z2015-03-19T17:21:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>The computer is really awesome at doing quick searches for numbers
with weird properties, and people with an amateur interest in
recreational mathematics would do well to learn some simple
programming. People appear on math.stackexchange quite often with
questions about tic-tac-toe, but there are only 5,478 total positions,
so any question you want to ask can be instantaneously answered by an
exhaustive search. An amateur showed up last fall asking “Is it true
that no prime larger than 241 can be made by either adding or
subtracting 2 coprime numbers made up out of the prime factors 2,3,
and 5?” and, once you dig through the jargon,
the question is easily answered by the computer, which
quickly finds many counterexamples, such as <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24162%2b625%3d787%24"> and
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%5e%7b19%7d%2b3%5e4%3d524369%24">.</p>
<p>But sometimes the search appears too large to be practical, and then
you need to apply theory. Sometimes you can deploy a lot of theory and
solve the problem completely, avoiding the search. But theory is
expensive, and not always available. A hybrid approach often works,
which uses a tiny amount of theory to restrict the search space to the
point where the search is easy.</p>
<p>One of these <a href="http://blog.plover.com/math/excellent.html">I wrote up on this blog back in 2006</a>:</p>
<blockquote>
<p>A number
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> is excellent if it has an even number of digits, and if when
you chop it into a front half <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24"> and a back half <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24">, you have
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%5e2%20%2d%20a%5e2%20%3d%20n%24">. For example, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2448%24"> is excellent, because <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%248%5e2%20%2d%0a%3e%204%5e2%20%3d%2048%24">, and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243468%24"> is excellent, because <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2468%5e2%20%2d%2034%5e2%20%3d%204624%0a%3e%20%2d%201156%20%3d%203468%24">.</p>
</blockquote>
<p>The programmer who gave me thie problem
had tried a brute-force search over all numbers, but to
find all 10-digit excellent numbers, this required an infeasible
search of 9,000,000,000 candidates. With the application of a tiny
amount of algebra, one finds that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2810%5ek%2ba%29%20%3d%20b%5e2%2bb%24"> and it's not
hard to quickly test candidates for <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24"> to see if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2810%5ek%2ba%29%24"> has
this form and if so to find the corresponding value of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24">.
(Details are in <a href="http://blog.plover.com/math/excellent.html">the other post</a>.) This
reduces the search space for 10-digit excellent numbers from
9,000,000,000 candidates to 90,000, which could be done in under a
minute even with last-century technology, and is pretty nearly
instantaneous on modern equipment.</p>
<p>But anyway, the real point of this note is to discuss <a href="http://math.stackexchange.com/q/1196116/25554">a different
problem entirely</a>.
A recreational mathematician on stackexchange
wanted to find distinct integers <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2cb%2cc%2cd%24"> for which <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5e2%2bb%5e2%2c%0ab%5e2%2bc%5e2%2c%20c%5e2%2bd%5e2%2c%20%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24d%5e2%2ba%5e2%24"> were all perfect squares. You
can search over all possible quadruples of numbers, but this takes a
long time. The querent indicated later that he had tried such a
search but lost patience before it yielded anything.</p>
<p>Instead, observe that if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5e2%2bb%5e2%24"> is a perfect square then <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24">
and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24"> are the legs of a right triangle with integer sides; they
are terms in what is known as a <a href="https://en.wikipedia.org/wiki/Pythagorean_triple">Pythagorean
triple</a>. The
prototypical example is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%5e2%20%2b%204%5e2%20%3d%205%5e2%24">, and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%0a3%2c4%2c5%5crangle%24"> is the Pythagorean triple. (The querent was quite
aware that he was asking for Pythagorean triples, and mentioned them
specifically.)</p>
<p>Here's the key point: It has been known since ancient times that if
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%20a%2cb%2cc%5crangle%24"> is a Pythagorean triple, then there exist
integers <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24m%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> such that: $$\begin{align}
\require{align}
a & = n^2-m^2 \\
b & = 2mn \\
c & = n^2 + m^2
\end{align}$$</p>
<p>So you don't have to search for Pythagorean triples; you can just
generate them with no searching:</p>
<pre><code> for my $m (1 .. 200) {
for my $n ($m+1 .. 200) {
my $a = $n*$n-$m*$m;
my $b = 2 * $n * $m;
$trip{$a}{$b} = 1;
$trip{$b}{$a} = 1;
}
}
</code></pre>
<p>This builds a hash table, <code>%trip</code>, with two important properties:</p>
<ol>
<li><p><code>$trip{$a}</code> is a sub-table whose keys are all the numbers that can
form a triple with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24">. For example, <code>$trip{20}</code> is a hash with
three keys: 21, 48, and 99, because <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2420%5e2%2b21%5e2%20%3d%2029%5e2%2c%2020%5e2%2b48%5e2%3d%0a%20%20%2052%5e2%2c%20%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2420%5e2%20%2b%2099%5e2%20%3d%20101%5e2%24">, but 20 is not a participant
in any other triples.</p></li>
<li><p><code>$trip{$a}{$b}</code> is true if and only if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5e2%2bb%5e2%24"> is a perfect
square, and false otherwise.</p></li>
</ol>
<p>The table has only around 40,000 entries. Having constructed it, we
now search it:</p>
<pre><code> for my $a (keys %trip) {
for my $b (keys %{$trip{$a}}) {
for my $c (keys %{$trip{$b}}) {
next if $c == $a;
for my $d (keys %{$trip{$c}}) {
next if $d == $b;
print "$a $b $c $d\n" if $trip{$d}{$a};
}
}
}
}
</code></pre>
<p>The outer loop runs over each <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24"> that is known to be a member of a
Pythagorean triple. (Actually the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24m%2cn%24"> formulas show that
every number bigger than 2 is a member of <em>some</em>
triple, but we may as well skip the ones that are only in triples we
didn't tabulate.) Then the next loop runs over every <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24"> that can
possibly form a triple with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24">; that is, every <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24"> for which
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5e2%2bb%5e2%24"> is a perfect square. We don't have to search for them; we
have them tabulated ahead of time. Then for each such <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24"> (and
there aren't very many) we run over every <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c%24"> that forms a triple
with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24">, and again there is no searching and very few candidates.
Then then similarly <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24d%24">, and if the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24d%24"> we try forms a triple with
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24">, we have a winner.</p>
<p>The <code>next if $c == $a</code> and <code>next if $d == $b</code> tests are to rule out
trivial solutions like <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%3dc%3d3%2c%20b%3dd%3d4%24">, which the querent wasn't
interested in anyway. We don't have to test for equality of any of
ther other pairs because no number can form a Pythagorean triple with
itself (because <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5csqrt2%24"> is irrational).</p>
<p>This runs in less than a second on so-so hardware and produces 11
solutions:</p>
<pre><code> 3472 7296 10400 2175
4312 23520 12008 465
6512 9984 800 6375
12312 666 1288 8415
14592 6944 4350 20800
16830 2576 1332 24624
19968 13024 12750 1600
25500 26048 39936 3200
30192 6175 2400 9856
41600 29184 13888 8700
47040 8624 930 24016
</code></pre>
<p>Only five of these are really different. For example, the last one is
the same as the second, with every element multiplied by 2; the third,
seventh, and eighth are similarly the same. In general if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%0aa%2cb%2cc%2cd%5crangle%24"> is a solution, so is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%20ka%2c%20kb%2ckc%2ckd%5crangle%24">
for any <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%24">. A slightly improved version would require that the
four numbers not have any common factor greater than 1; there are few
enough solutions that the cost of this test would be completely
negligible.</p>
<p>The only other thing wrong with the program is that it produces each
solution 8 times; if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%20a%2cb%2cc%2cd%5crangle%24"> is a solution, then
so are <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%20b%2cc%2cd%2ca%5crangle%2c%20%5clangle%20d%2cc%2cb%2ca%5crangle%2c%24"> and so on.
This is easily fixed with a little post-filtering; pipe the output
through</p>
<pre><code> perl -nle '$k = join " ", sort { $a <=> $b } split; print unless $seen{$k}++ '
</code></pre>
<p>or something of that sort.</p>
<p>The corresponding run with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24m%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> up to 2,000 instead of
only 200 takes 5 minutes and finds 445 solutions, of which 101 are distinct, including <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%0a3614220%2c%20618192%2c%202080820%2c%20574461%5crangle%24">. It would take a very long
time to find this with a naïve search.</p>
<p>[ For a much larger and more complex example of the same sort of
thing, see <a href="http://blog.plover.com/math/dd.html">When do <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242n%24"> have the same
digits?</a>. I took a seemingly-intractable problem
and analyzed it mathematically. I used considerably more than an ounce
of theory in this case, and while the theory was not enough to solve the
problem, it was enough to reduce the pool of candates to the point
that a computer search was feasible. ]<p></p>
<p>[ Addendum 20150728: <a href="http://blog.plover.com/math/ounce-of-theory-2.html">Another
example</a> ]</p>