The Universe of DiscourseThe Universe of Discourse (Mark Dominus Blog)tag:blog.plover.com,2005:/mathBlosxomhttp://perl.plover.com/favicon.ico2015-07-28T14:48:00Ztag: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. It is possible to pack them into a 3×3x3 box? (There
will, of course, be some space left over.)</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_%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_%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_%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_2%24"> for which it is exactly doubling every <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24t_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/testblog/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 _did_ do this. 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
_What is the Name of this Book?_ 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 that ahead of time, 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>
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
theroem 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 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 different
problem entirely. 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>
tag:blog.plover.com,2014:/math/algebraWithin this instrument, resides the Universe2014-11-22T17:38:00Z2014-11-22T17:38:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>When opportunity permits, I have been trying to teach my ten-year-old
daughter Katara rudiments of algebra and group theory. Last night I posed
this problem:</p>
<blockquote>
<p>Mary and Sue are sisters. Today, Mary is three times as old as Sue;
in two years, she will be twice as old as Sue. How old are they
now?</p>
</blockquote>
<p>I have tried to teach Katara that these problems have several
phases. In the first phase you translate the problem into algebra, and
then in the second phase you manipulate the symbols, almost
mechanically, until the answer pops out as if by magic.</p>
<p>There is a third phase, which is pedagogically and practically
essential. This is to check that the solution is correct by
translating the results back to the context of the original problem.
It's surprising how often teachers neglect this step; it is as if a
magician who had made a rabbit vanish from behind a screen then
forgot to take away the screen to show the audience that the rabbit
had vanished.</p>
<p>Katara set up the equations, not as I would have done, but using four
unknowns, to represent the two ages today and the two ages in the
future:</p>
<p>$$\begin{align}
MT & = 3ST \\
MY & = 2SY \\
\end{align}
$$</p>
<p>(<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24MT%24"> here is the name of a single variable, not a product of <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=%24T%24">; the others should be understood similarly.)</p>
<p>“Good so far,” I said, “but you have four unknowns and only two
equations. You need to find two more relationships between the
unknowns.” She thought a bit and then wrote down the other two
relations:</p>
<p>$$\begin{align}
MY & = MT + 2 \\
SY & = ST + 2
\end{align}
$$</p>
<p>I would have written two equations in two unknowns:</p>
<p>$$\begin{align}
M_T & = 3S_T\\
M_T+2 & = 2(S_T + 2)
\end{align}
$$</p>
<p>but one of the best things about mathematics is that there are many
ways to solve each problem, and no method is privileged above any
other except perhaps for reasons of practicality. Katara's translation
is different from what I would have done, and it requires more work in
phase 2, but it is correct, and I am not going to tell her to do it my
way. The method works <em>both</em> ways; this is one of its best features.
If the problem can be solved by thinking of it as a problem in two
unknowns, then it can <em>also</em> be solved by thinking of it as a problem
in four or in eleven unknowns. You need to find more relationships,
but they must exist and they can be found.</p>
<p>Katara may eventually want to learn a technically easier way to do it,
but to teach that right now would be what programmers call a premature
optimization. If her formulation of the problem requires more symbol
manipulation than what I would have done, that is all right; she needs
practice manipulating the symbols anyway.</p>
<p>She went ahead with the manipulations, reducing the system of four
equations to three, then two and then one, solving the one equation to
find the value of the single remaining unknown, and then substituting
that value back to find the other unknowns. One nice thing about these
simple problems is that when the solution is correct you can see it at
a glance: Mary is six years old and Sue is two, and in two years they
will be eight and four. Katara loves picking values for the unknowns
ahead of time, writing down a random set of relations among those
values, and then working the method and seeing the correct answer pop
out. I remember being endlessly delighted by almost the same thing
when I was a little older than her. In <em>The Dying Earth</em> Jack Vance
writes of a wizard who travels to an alternate universe to learn from
the master “the secret of renewed youth, many spells of the ancients,
and a strange abstract lore that Pandelume termed ‘Mathematics.’”</p>
<blockquote>
<p>“I find herein a wonderful beauty,” he told
Pandelume. “This is no science, this is art, where equations fall
away to elements like resolving chords, and where always prevails a
symmetry either explicit or multiplex, but always of a crystalline
serenity.”</p>
</blockquote>
<p>After Katara had solved this problem, I asked if she was game for
something a little weird, and she said she was, so I asked her:</p>
<blockquote>
<p>Mary and Sue are sisters. Today, Mary is three times as old as Sue;
in two years, they will be the same age. How old are they
now?</p>
</blockquote>
<p>“WHAAAAAT?” she said. She has a good number sense, and immediately
saw that this was a strange set of conditions. (If they aren't the
same age now, how can they be the same age in two years?) She asked
me what would happen. I said (truthfully) that I wasn't sure, and
suggested she work through it to find out. So she set up
the equations as before and worked out the solution, which is obvious
<em>once you see it</em>: Both girls are zero years old today, and zero is
three times as old as zero. Katara was thrilled and delighted, and
shared her discovery with her mother and her aunt.</p>
<p>There are some powerful lessons here. One is that the method works
even when the conditions seem to make no sense; often the results pop
out just the same, and can sometimes make sense of problems that seem
ill-posed or impossible. Once you have set up the equations, you can
just push the symbols around and the answer will emerge, like a
familiar building approached through a fog.</p>
<p>But another lesson, only hinted at so far, is that mathematics has its
own way of understanding things, and this is not always the way that
humans understand them. Goethe famously said that whatever you say to
mathematicians, they immediately translate it into their own language
and then it is something different; I think this is exactly what he
meant.</p>
<p>In this case it is not too much of a stretch to agree that Mary is
three times as old as Sue when they are both zero years old. But in
the future I plan to give Katara a problem that requires Mary and Sue
to have negative ages—say that Mary is twice as old as Sue today, but
in three years Sue will be twice as old—to demonstrate that the answer
that pops out may not be a reasonable one, or that the original
translation into mathematics can lose essential features of the
original problem. The solution that says that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24M_T%3d%2d2%2c%20S_T%3d%2d1%20%24"> is
mathematically irreproachable, and if the original problem had been
posed as “Find two numbers such that…” it would be perfectly correct.
But translated back to the original context of a problem that asks
about the ages of two sisters, the solution is unacceptable. This is
the point of the joke about the spherical cow.</p>
tag:blog.plover.com,2014:/math/ddWhen do n and 2n have the same digits?2014-07-23T13:39:00Z2014-07-23T13:39:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>[This article was published last month on <a href="http://math.blogoverflow.com/">the math.stackexchange
blog</a>, which seems to have died young,
despite many earnest-sounding promises beforehand from people who
claimed they would contribute material. I am repatriating it here.]</p>
<p>A <a href="http://math.stackexchange.com/questions/782334/interview-question-asked-in-yahoo?">recent question on math.stackexchange</a> asks for the smallest positive integer <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> for which the number <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242A%24"> has the same
decimal digits in some other order.</p>
<p>Math geeks may immediately realize that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24142857%24"> has this property, because it is the first 6 digits of the decimal expansion of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%2017%24">, and the cyclic behavior of the decimal expansion of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%20n7%24"> is well-known. But is this the <em>minimal</em> solution? It is not. Brute-force enumeration of the solutions quickly reveals that there are 12 solutions of 6 digits each, all permutations of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24142857%24">, and that larger solutions, such as 1025874 and 1257489 seem to follow a similar pattern. What is happening here?</p>
<p>Stuck in Dallas-Fort Worth airport one weekend, I did some work on the problem, and although I wasn't able to solve it completely, I made significant progress. I found a method that allows one to hand-calculate that there is no solution with fewer than six digits, and to enumerate all the solutions with 6 digits, including the minimal one. I found an explanation for the surprising behavior that solutions tend to be permutations of one another. The short form of the explanation is that there are fairly strict conditions on which <em>sets</em> of digits can appear in a solution of the problem. But once the set of digits is chosen, the conditions on that <em>order</em> of the digits in the solution are fairly lax.</p>
<p>So one typically sees, not only in base 10 but in other bases, that the solutions to this problem fall into a few classes that are all permutations of one another; this is exactly what happens in base 10 where all the 6-digit solutions are permutations of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24124578%24">. As the number of digits is allowed to increase, the strict first set of conditions relaxes a little, and other digit groups appear as solutions.</p>
<h3>Notation</h3>
<p>The property of interest, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P_R%28A%29%24">, is that the numbers <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%3d2A%24"> have exactly the same base-<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%24"> digits. We would like to find numbers <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> having property <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P_R%24"> for various <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%24">, and we are most interested in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%3d10%24">. Suppose <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> is an <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24">-digit numeral having property <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P_R%24">; let the (base-<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%24">) digits of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> be <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_%7bn%2d1%7d%5cldots%20a_1a_0%24"> and similarly the digits of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%20%3d%202A%24"> are <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b_%7bn%2d1%7d%5cldots%20b_1b_0%24">. The reader is encouraged to keep in mind the simple example of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%3d8%2c%20n%3d4%2c%20A%3d%5cmathtt%7b1042%7d%2c%20B%3d%5cmathtt%7b2104%7d%24"> which we will bring up from time to time.</p>
<p>Since the digits of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> are the same, in a different order, we may say that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b_i%20%3d%20a_%7bP%28i%29%7d%24"> for some permutation <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">. In general <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> might have more than one cycle, but we will suppose that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is a single cycle. All the following discussion of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> will apply to the individual cycles of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> in the case that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is a product of two or more cycles. For our example of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%3d%5cmathtt%7b1042%7d%2c%20b%3d%5cmathtt%7b2104%7d%24">, we have <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%20%3d%20%280%5c%2c1%5c%2c2%5c%2c3%29%24"> in cycle notation. We won't need to worry about the details of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">, except to note that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24i%2c%20P%28i%29%2c%20P%28P%28i%29%29%2c%20%5cldots%2c%20P%5e%7bn%2d1%7d%28i%29%24"> completely exhaust the indices <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%2e%20%5cldots%20n%2d1%24">, and that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%5en%28i%29%20%3d%20i%24"> because <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is an <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24">-cycle.</p>
<h3>Conditions on the set of digits in a solution</h3>
<p>For each <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24i%24"> we have $$a_{P(i)} = b_{i} \equiv 2a_{i} + c_i\pmod R
$$ where the ‘carry bit’ <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c_i%24"> is either 0 or 1 and depends on whether there was a carry when doubling <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_%7bi%2d1%7d%24">. (When <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24i%3d0%24"> we are in the rightmost position and there is never a carry, so <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c_0%3d%200%24">.) We can then write:</p>
<p>$$\begin{align}
a_{P(P(i))} &= 2a_{P(i)} + c_{P(i)} \\
&= 2(2a_{i} + c_i) + c_{P(i)} &&= 4a_i + 2c_i + c_{P(i)}\\
a_{P(P(P(i)))} &= 2(4a_i + 2c_i + c_{P(P(i)})) + c_{P(i)} &&= 8a_i + 4c_i + 2c_{P(i)} + c_{P(P(i))}\\
&&&\vdots\\
a_{P^n(i)} &&&= 2^na_i + v
\end{align}
$$</p>
<p>all equations taken <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbmod%20R%24">. But since <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is an <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24">-cycle, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%5en%28i%29%20%3d%20i%24">, so we have
$$a_i \equiv 2^na_i + v\pmod R$$ or equivalently $$\big(2^n-1\big)a_i + v \equiv 0\pmod
R\tag{$\star$}$$ where <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%5cin%5c%5c%7b0%2c%5cldots%202%5en%2d1%5c%5c%7d%24"> depends only on the values of the carry bits <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c_i%24">—the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c_i%24"> are precisely the binary digits of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24">.</p>
<p>Specifying a particular value of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_0%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> that satisfy this equation completely determines all the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%24">. For example, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_0%20%3d%202%2c%20v%20%3d%20%5ccolor%7bdarkblue%7d%7b0010%7d_2%20%3d%202%24"> is a solution when <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%3d8%2c%20n%3d4%24"> because <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbigl%282%5e4%2d1%5cbigr%29%5ccdot2%20%2b%202%5cequiv%200%5cpmod%208%24">, and this solution allows us to compute</p>
<p>$$\def\db#1{\color{darkblue}{#1}}\begin{align}
a_0&&&=2\\
a_{P(0)} &= 2a_0 &+ \db0 &= 4\\
a_{P^2(0)} &= 2a_{P(0)} &+ \db0 &= 0 \\
a_{P^3(0)} &= 2a_{P^2(0)} &+ \db1 &= 1\\ \hline
a_{P^4(0)} &= 2a_{P^3(0)} &+ \db0 &= 2\\
\end{align}$$</p>
<p>where the carry bits <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c_i%20%3d%20%5clangle%200%2c0%2c1%2c0%5crangle%24"> are visible in the third column, and all the sums are taken <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cpmod%208%24">. Note that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_%7bP%5en%280%29%7d%20%3d%20a_0%24"> as promised. This derivation of the entire set of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%24"> from a single one plus a choice of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> is crucial, so let's see one more example. Let's consider <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%3d10%2c%20n%3d3%24">. Then we want to choose <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_0%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> so that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cleft%282%5e3%2d1%5cright%29a_0%20%2b%20v%20%5cequiv%200%5cpmod%7b10%7d%24"> where <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%5cin%5c%5c%7b0%5cldots%207%5c%5c%7d%24">. One possible solution is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5c_0%20%3d%205%2c%20v%3d%5ccolor%7bdarkblue%7d%7b101%7d%5c_2%20%3d%205%24">. Then we can derive the other <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%24"> as follows:</p>
<p>$$\begin{align}
a_0&&&=5\\
a_{P(0)} &= 2a_0 &+ \db1 &= 1\\
a_{P^2(0)} &= 2a_{P(0)} &+ \db0 &= 2 \\\hline
a_{P^3(0)} &= 2a_{P^2(0)} &+ \db1 &= 5\\
\end{align}$$</p>
<p>And again we have <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_%7bP%5en%280%29%7d%3d%20a_0%24"> as required.</p>
<p>Since the bits of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> are used cyclically, not every pair of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%20a_0%2c%20v%5crangle%24"> will yield a different solution. Rotating the bits of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> and pairing them with different choices of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_0%24"> will yield the same cycle of digits starting from a different place. In the first example above, we had <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_0%20%3d%202%2c%20v%20%3d%200010_2%20%3d%202%24">. If we were to take <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_0%20%3d%204%2c%20v%20%3d%200100_2%20%3d%204%24"> (which also solves <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28%5cstar%29%24">) we would get the same cycle of values of the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%24"> but starting from <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%24"> instead of from <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%24">, and similarly if we take <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_0%3d0%2c%20v%20%3d%201000_2%20%3d%208%24"> or <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_0%20%3d%201%2c%20v%20%3d%200001_2%24">. So we can narrow down the solution set of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28%5cstar%29%24"> by considering only the so-called <a href="https://en.wikipedia.org/wiki/Bracelet_%28combinatorics%29">bracelets</a> of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> rather than all <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%5en%24"> possible values. Two values of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> are considered equivalent as bracelets if one is a rotation of the other. When a set of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24">-values are equivalent as bracelets, we need only consider one of them; the others will give the same cyclic sequence of digits, but starting in a different place. For <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d4%24">, for example, the bracelets are <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240000%2c%200001%2c%200011%2c%200101%2c%200111%2c%20%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241111%24">; the sequences <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240110%2c%201100%2c%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241001%24"> being equivalent to <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240011%24">, and so on.</p>
<h4>Example</h4>
<p>Let us take <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%3d9%2c%20n%3d3%24">, so we want to find 3-digit numerals with property <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P_9%24">. According to <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28%5cstar%29%24"> we need <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%247a_i%20%2b%20v%20%5cequiv%200%5cpmod%7b9%7d%24"> where <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%5cin%5c%5c%7b0%5cldots%0a7%5c%5c%7d%24">. There are 9 possible values for <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%24">; for each one there is at most one possible value of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> that makes the sum zero:</p>
<p>$$\begin{array}{rrr}
a_i & 7a_i & v \\ \hline
0 & 0 & 0 \\
1 & 7 & 2 \\
2 & 14 & 4 \\
3 & 21 & 6 \\
4 & 28 & \\
5 & 35 & 1 \\
6 & 42 & 3 \\
7 & 49 & 5 \\
8 & 56 & 7 \\
\end{array}
$$</p>
<p>(For <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%3d4%24"> there is no solution.) We may disregard the non-bracelet values of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24">, as these will give us solutions that are the same as those given by bracelet values of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24">. The bracelets are:</p>
<p>$$\begin{array}{rl} 000 & 0 \\ 001 & 1 \\ 011 & 3 \\ 111 & 7 \end{array}$$</p>
<p>so we may disregard the solutions exacpt when <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%3d0%2c1%2c3%2c7%24">. Calculating the digit sequences from these four values of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> and the corresponding <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%24"> we find:</p>
<p>$$\begin{array}{ccl}
a_0 & v & \text{digits} \\ \hline
0 & 0 & 000 \\
5 & 1 & 512 \\
6 & 3 & 637 \\
8 & 7 & 888 \
\end{array}
$$</p>
<p>(In the second line, for example, we have <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%3d1%20%3d%20001_2%24">, so <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%20%3d%202%5ccdot%205%20%2b%200%3b%202%20%3d%201%5ccdot%202%20%2b%200%3b%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%245%20%3d%202%5ccdot%202%20%2b%201%24">.)</p>
<p>Any number <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> of three digits, for which <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242A%24"> contains exactly the same three digits, in base 9, must therefore consist of exactly the digits <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24000%2c%20125%2c%20367%2c%24"> or <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24888%24">.</p>
<h4>A warning</h4>
<p>All the foregoing assumes that the permutation <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is <em>a single cycle</em>. In general, it may not be. Suppose we did an analysis like that above for <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%3d10%2c%20n%3d5%24"> and found that there was no possible digit set, other than the trivial set <code>00000</code>, that satisfied the governing equation <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%282%5e5%2d1%29a_0%20%2b%20v%5cequiv%200%5cpmod%7b10%7d%24">. This would <em>not</em> completely rule out a base-10 solution with 5 digits, because the analysis only rules out a <em>cyclic</em> set of digits. There could still be a solution where <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> was a product of a <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%24"> and a <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%24">-cycle, or a product of still smaller cycles.</p>
<p>Something like this occurs, for example, in the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d4%2c%20R%3d8%24"> case. Solving the governing equation <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%282%5e5%2d1%29a_0%20%2b%20v%20%5cequiv%200%5cpmod%208%24"> yields only four possible digit cycles, namely <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b0%2c1%2c2%2c4%5c%5c%7d%2c%20%5c%5c%7b1%2c3%2c6%2c4%5c%5c%7d%2c%20%5c%5c%7b2%2c5%2c2%2c5%5c%5c%7d%24">, and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b3%2c7%2c6%2c5%5c%5c%7d%24">. But there are several additional solutions: <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242500_8%5ccdot%202%20%3d%205200_8%2c%202750_8%5ccdot%202%20%3d%20%20%205720_8%2c%20%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242775_8%5ccdot%202%20%3d%205772_8%24">. These correspond to permutations <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> with more than one cycle. In the case of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242750_8%24">, for example, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> exchanges the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%245%24"> and the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%24">, and leaves the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%24"> and the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%247%24"> fixed.</p>
<p>For this reason we cannot rule out the possibility of an <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24">-digit solution without first considering all smaller <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24">.</p>
<h4>The Large Equals Odd rule</h4>
<p>When <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%24"> is even there is a simple condition we can use to rule out certain sets of digits from being single-cycle solutions. Recall that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%3da_%7bn%2d1%7d%5cldots%20a_0%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%3db_%7bn%2d1%7d%5cldots%20b_0%24">. Let us agree that a digit <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24d%24"> is <em>large</em> if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24d%5cge%20%5cfrac%20R2%24"> and <em>small</em> otherwise. That is, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24d%24"> is large if, upon doubling, it causes a carry into the next column to the left.</p>
<p>Since <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b_i%20%3d%282a_i%20%2b%20c_i%29%5cbmod%20R%24">, where the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c_i%24"> are carry bits, we see that, except for <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b_0%24">, the digit <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b_i%24"> is odd precisely when there is a carry from the next column to the right, which occurs precisely when <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_%7bi%2d1%7d%24"> is large. Thus the number of odd digits among <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b_1%2c%5cldots%20b_%7bn%2d1%7d%24"> is equal to the number of large digits among <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_1%2c%5cldots%20a_%7bn%2d2%7d%24">.
This leaves the digits <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b_0%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_%7bn%2d1%7d%24"> uncounted. But <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b_0%24"> is never odd, since there is never a carry in the rightmost position, and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_%7bn%2d1%7d%24"> is always small (since otherwise <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%24"> would have <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%2b1%24"> digits, which is not allowed). So the number of large digits in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> is exactly equal to the number of odd digits in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%24">. And since <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"> have exactly the same digits, the number of large digits in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> is equal to the number of odd digits in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">. Observe that this is the case for our running example <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241042_8%24">: there is one odd digit and one large digit (the 4).</p>
<p>When <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%24"> is odd the analogous condition is somewhat more complicated, but since the main case of interest is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%3d10%24">, we have the useful rule that:</p>
<blockquote>
For <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%24"> even, the number of odd digits in any solution <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> is equal to the number of large digits in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">.
</blockquote>
<h1>Conditions on the order of digits in a solution</h1>
<p>We have determined, using the above method, that the digits <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b5%2c1%2c2%5c%5c%7d%24"> might form a base-9 numeral with property <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P_9%24">. Now we would like to arrange them into a base-9 numeral that actually does have that property. Again let us write <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%20%3d%20a_2a_1a_0%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%3db_2b_1b_0%24">, with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%3d2A%24">. Note that if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%20%3d%201%24">, then <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b_i%20%3d%203%24"> (if there was a carry from the next column to the right) or <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%24"> (if there was no carry), but since <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b_i%3d3%24"> is impossible, we must have <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%20%3d%202%24"> and therefore <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_%7bi%2d1%7d%24"> must be small, since there is no carry into position <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24i%24">. But since <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_%7bi%2d1%7d%24"> is also one of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b5%2c1%2c2%5c%5c%7d%24">, and it cannot also be <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%24">, it must be <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%24">. This shows that the 1, unless it appears in the rightmost position, must be to the left of the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%24">; it cannot be to the left of the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%245%24">. Similarly, if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%20%3d%202%24"> then <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b_i%20%3d%205%24">, because <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%24"> is impossible, so the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%24"> must be to the left of a large digit, which must be the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%245%24">. Similar reasoning produces no constraint on the position of the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%245%24">; it could be to the left of a small digit (in which case it doubles to <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%24">) or a large digit (in which case it doubles to <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%24">). We can summarize these findings as follows:</p>
<p>$$\begin{array}{cl}
\text{digit} & \text{to the left of} \\ \hline
1 & 1, 2, \text{end} \\
2 & 5 \\
5 & 1,2,5,\text{end}
\end{array}$$</p>
<p>Here “end” means that the indicated digit could be the rightmost.</p>
<p>Furthermore, the left digit of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> must be small (or else there would be a carry in the leftmost place and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242A%24"> would have 4 digits instead of 3) so it must be either 1 or 2. It is not hard to see from this table that the digits must be in the order <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24125%24"> or <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24251%24">, and indeed, both of those numbers have the required property: <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24125_9%5ccdot%202%20%3d%20251_9%24">, and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24251_9%5ccdot%202%20%3d%20512_9%24">.</p>
<p>This was a simple example, but in more complicated cases it is helpful to draw the order constraints as a graph. Suppose we draw a graph with one vertex for each digit, and one additional vertex to represent the end of the numeral. The graph has an edge from vertex <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> to <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%27%24"> whenever <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> can appear to the left of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%27%24">. Then the graph drawn for the table above looks like this:</p>
<p><img src="http://pic.plover.com/math-se-blog/double-digits/huhooa.png" alt="Graph for 125 base 9" /></p>
<p>A 3-digit numeral with property <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P_9%24"> corresponds to a path in this graph that starts at one of the nonzero small digits (marked in blue), ends at the red node marked ‘end’, and visits each node exactly once. Such a path is called <em><a href="https://en.wikipedia.org/wiki/Hamiltonian_path">hamiltonian</a></em>. Obviously, self-loops never occur in a hamiltonian path, so we will omit them from future diagrams.</p>
<p>Now we will consider the digit set <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24637%24">, again base 9. An analysis similar to the foregoing allows us to construct the following graph:</p>
<p><img src="http://pic.plover.com/math-se-blog/double-digits/ovecmp.png" alt="Graph for 367 base 9" /></p>
<p>Here it is immediately clear that the only hamiltonian path is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%2d7%2d6%2d%5ctext%7bend%7d%24">, and indeed, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24376_9%5ccdot%202%20%3d%20763_9%24">.</p>
<p>In general there might be multiple instances of a digit, and so multiple nodes labeled with that digit. Analysis of the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%2c0%2c0%24"> case produces a graph with no legal start nodes and so no solutions, unless leading zeroes are allowed, in which case <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24000%24"> is a perfectly valid solution. Analysis of the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%248%2c8%2c8%24"> case produces a graph with no path to the end node and so no solutions. These two trivial patterns appear for all <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%24"> and all <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24">, and we will ignore them from now on.</p>
<p>Returning to our ongoing example, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241042%24"> in base 8, we see that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%24"> must double to <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=%244%24">, so must be to the left of small digits, but <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%24"> can double to either <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%24"> or <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%24"> and so could be to the left of anything. Here the constraints are so lax that the graph doesn't help us narrow them down much:</p>
<p><img src="http://pic.plover.com/math-se-blog/double-digits/mludlo.png" alt="Graph for 1024 base 8" /></p>
<p>Observing that the only arrow into the 4 is from 0, so that the 4 must follow the 0, and that the entire number must begin with 1 or 2, we can enumerate the solutions:</p>
<pre>
1042
1204
2041
2104
</pre>
<p>If leading zeroes are allowed we have also:</p>
<pre>
0412
0421
</pre>
<p>All of these are solutions in base 8.</p>
<h3>The case of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%3d10%24"></h3>
<p>Now we turn to our main problem, solutions in base 10.</p>
<p>To find <em>all</em> the solutions of length 6 requires an enumeration of smaller solutions, which, if they existed, might be concatenated into a solution of length 6. This is because our analysis of the digit sets that can appear in a solution assumes that the digits are permuted <em>cyclically</em>; that is, the permutations <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> that we considered had only one cycle each.</p>
<p>There are no smaller solutions, but to prove that the length 6 solutions are minimal, we must analyze the cases for smaller <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> and rule them out. We now produce a complete analysis of the base 10 case with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%3d10%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%5cle%206%24">. For <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d1%24"> there is only the trivial solution of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%24">, which we disregard. (The question asked for a positive number anyway.)</p>
<h4><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d2%24"></h4>
<p>For <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d2%24">, we want to find solutions of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243a_i%20%2b%20v%20%5cequiv%200%5cpmod%7b10%7d%24"> where <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> is a two-bit bracelet number, one of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2400_2%2c%2001_2%2c%20%24"> or <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2411_2%24">. Tabulating the values of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%5cin%5c%5c%7b0%2c1%2c3%5c%5c%7d%24"> that solve this equation we get:</p>
<p>$$\begin{array}{ccc}
v& a_i \\ \hline
0 & 0 \\
1& 3 \\
3& 9 \\
\end{array}$$</p>
<p>We can disregard the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%3d0%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%3d3%24"> solutions because the former yields the trivial solution <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2400%24"> and the latter yields the nonsolution <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2499%24">. So the only possibility we need to investigate further is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%20%3d%203%2c%20v%20%3d%201%24">, which corresponds to the digit sequence <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2436%24">: Doubling <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%24"> gives us <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%246%24"> and doubling <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%246%24">, plus a carry, gives us <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%24"> again.</p>
<p>But when we tabulate of which digits must be left of which informs us that there is no solution with just <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%246%24">, because the graph we get, once self-loops are eliminated, looks like this:</p>
<p><img src="http://pic.plover.com/math-se-blog/double-digits/xthkmc.png" alt="graph for 36 base 10" /></p>
<p>which obviously has no hamiltonian path. Thus there is no solution for <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%3d10%2c%20n%3d2%24">.</p>
<h4><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d3%24"></h4>
<p>For <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d3%24"> we need to solve the equation <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%247a_i%20%2b%20v%20%5cequiv%200%5cpmod%7b10%7d%24"> where <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> is a bracelet number in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b0%2c%5cldots%207%5c%5c%7d%24">, specifically one of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%2c1%2c3%2c%24"> or <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%247%24">. Since <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%247%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2410%24"> are relatively prime, for each <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> there is a single <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%24"> that solves the equation.
Tabulating the possible values of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_i%24"> as before, and this time omitting rows with no solution, we have:</p>
<p>$$\begin{array}{rrl}
v & a_i & \text{digits}\\ \hline
0& 0 & 000\\
1& 7 & 748 \\
3& 1 & 125\\
7&9 & 999\\
\end{array}$$</p>
<p>The digit sequences <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%2c0%2c0%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%249%2c9%2c9%24"> yield trivial solutions or nonsolutions as usual, and we will omit them in the future. The other two lines suggest the digit sets <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%2c2%2c5%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%2c7%2c8%24">, both of which fails the “odd equals large” rule.</p>
<p>This analysis rules out the possibility of a digit set with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a_0%20%5cto%20a_1%20%5cto%20a_2%20%5cto%20a_1%24">, but it does not <em>completely</em> rule out a 3-digit solution, since one could be obtained by concatenating a one-digit and a two-digit solution, or three one-digit solutions. However, we know by now that no one- or two-digit solutions exist. Therefore there are no 3-digit solutions in base 10.</p>
<h4><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d4%24"></h4>
<p>For <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d4%24"> the governing equation is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2415a_i%20%2b%20v%20%5cequiv%200%5cpmod%7b10%7d%24"> where <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> is a 4-bit bracelet number, one of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b0%2c1%2c3%2c5%2c7%2c15%5c%5c%7d%24">. This is a little more complicated because <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cgcd%2815%2c10%29%5cne%201%24">. Tabulating the possible digit sets, we get:</p>
<p>$$\begin{array}{crrl}
a_i & 15a_i& v & \text{digits}\\ \hline
0 & 0 & 0 & 0000\\
1 & 5 & 5 & 1250\\
1 & 5 & 15 & 1375\\
2 & 0 & 0 & 2486\\
3 & 5 & 5 & 3749\\
3 & 5 & 15 & 3751\\
4 & 0 & 0 & 4862\\
5 & 5 & 5 & 5012\\
5 & 5 & 5 & 5137\\
6 & 0 & 0 & 6248\\
7 & 5 & 5 & 7493\\
7 & 5 & 5 & 7513\\
8 & 0 & 0 & 8624 \\
9 & 5 & 5 & 9874\\
9 & 5 & 15 & 9999 \\
\end{array}$$</p>
<p>where the second column has been reduced mod <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2410%24">. Note that even restricting <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> to bracelet numbers the table still contains duplicate digit sequences; the 15 entries on the right contain only the six basic sequences <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240000%2c%200125%2c%201375%2c%202486%2c%203749%2c%204987%24">, and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%249999%24">. Of these, only <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240000%2c%209999%2c%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243749%24"> obey the odd equals large criterion, and we will disregard <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%240000%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%249999%24"> as usual, leaving only <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243749%24">. We construct the corresponding graph for this digit set as follows: <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%24"> must double to <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%247%24">, not <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%246%24">, so must be left of a large number <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%247%24"> or <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%249%24">. Similarly <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%24"> must be left of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%247%24"> or <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%249%24">. <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%249%24"> must also double to <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%249%24">, so must be left of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%247%24">. Finally, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%247%24"> must double to <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%24">, so must be left of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%2c4%24"> or the end of the numeral. The corresponding graph is:</p>
<p><img src="http://pic.plover.com/math-se-blog/double-digits/wmelxc.png" alt="graph for 3749 base 10" /></p>
<p>which evidently has no hamiltonian path: whichever of 3 or 4 we start at, we cannot visit the other without passing through 7, and then we cannot reach the end node without passing through 7 a second time. So there is no solution with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%3d10%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d4%24">.</p>
<h4><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d5%24"></h4>
<p>We leave this case as an exercise. There are 8 solutions to the governing equation, all of which are ruled out by the odd equals large rule.</p>
<h4><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d6%24"></h4>
<p>For <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d6%24"> the possible solutions are given by the governing equation <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2463a_i%20%2b%20v%20%5cequiv%200%5cpmod%7b10%7d%24"> where <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24v%24"> is a 6-bit bracelet number, one of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b0%2c1%2c3%2c5%2c7%2c9%2c11%2c13%2c15%2c21%2c23%2c27%2c31%2c63%5c%5c%7d%24">. Tabulating the possible digit sets, we get:</p>
<p>$$\begin{array}{crrl}
v & a_i & \text{digits}\\ \hline
0 & 0 & 000000\\
1 & 3 & 362486 \\
3 & 9 & 986249 \\
5 & 5 & 500012 \\
7 & 1 & 124875 \\
9 & 7 & 748748 \\
11 & 3 & 362501 \\
13 & 9 & 986374 \\
15 & 5 & 500137 \\
21 & 3 & 363636 \\
23 & 9 & 989899 \\
27 & 1 & 125125 \\
31 & 3 & 363751 \\
63 & 9 & 999999 \\
\end{array}$$</p>
<p>After ignoring <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24000000%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24999999%24"> as usual, the large equals odd rule allows us to ignore all the other sequences except <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24124875%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24363636%24">. The latter fails for the same reason that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%2436%24"> did when <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d2%24">. But <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24142857%24"> , the lone survivor, gives us a complicated derived graph containing many hamiltonian paths, every one of which is a solution to the problem:</p>
<p><img src="http://pic.plover.com/math-se-blog/double-digits/uswkfz.png" alt="graph for 124578 base 10" /></p>
<p>It is not hard to pick out from this graph the minimal solution <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24125874%24">, for which <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24125874%5ccdot%202%20%3d%20251748%24">, and also our old friend <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24142857%24"> for which <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24142857%5ccdot%202%20%3d%20285714%24">.</p>
<p>We see here the reason why all the small numbers with property <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P_%7b10%7d%24"> contain the digits <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24124578%24">. The constraints on <em>which</em> digits can appear in a solution are quite strict, and rule out all other sequences of six digits and all shorter sequences. But once a set of digits passes these stringent conditions, the constraints on it are much looser, because <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%24"> is only required to have the digits of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> in <em>some</em> order, and there are many possible orders, many of which will satisfy the rather loose conditions involving the distribution of the carry bits. This graph is typical: it has a set of small nodes and a set of large nodes, and each node is connected to either <em>all</em> the small nodes or <em>all</em> the large nodes, so that the graph has many edges, and, as in this case, a largish clique of small nodes and a largish clique of large nodes, and as a result many hamiltonian paths.</p>
<h3>Onward</h3>
<p>This analysis is tedious but is simple enough to perform by hand in under an hour. As <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> increases further, enumerating the solutions of the governing equation becomes very time-consuming. I wrote a simple computer program to perform the analysis for given <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24R%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24">, and to emit the possible digit sets that satisfied the large equals odd criterion. I had wondered if <em>every</em> base-10 solution contained equal numbers of the digits <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%2c2%2c4%2c8%2c5%2c%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%247%24">. This is the case for <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d7%24"> (where the only admissible digit set is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b1%2c2%2c4%2c5%2c7%2c8%5c%5c%7d%5ccup%5c%5c%7b9%5c%5c%7d%24">), for <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d8%24"> (where the only admissible sets are <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b1%2c2%2c4%2c5%2c7%2c8%5c%5c%7d%5ccup%20%5c%5c%7b3%2c6%5c%5c%7d%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b1%2c2%2c4%2c5%2c7%2c8%5c%5c%7d%5ccup%5c%5c%7b9%2c9%5c%5c%7d%24">), and for <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d9%24"> (where the only admissible sets are <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b1%2c2%2c4%2c5%2c7%2c8%5c%5c%7d%5ccup%5c%5c%7b3%2c6%2c9%5c%5c%7d%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b1%2c2%2c4%2c5%2c7%2c8%5c%5c%7d%5ccup%5c%5c%7b9%2c9%2c9%5c%5c%7d%24">). But when we reach <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d10%24"> the increasing number of bracelets has loosened up the requirements a little and there are 5 admissible digit sets. I picked two of the promising-seeming ones and quickly found by hand the solutions <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%244225561128%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241577438874%24">, both of which wreck any theory that the digits <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%2c2%2c4%2c5%2c8%2c7%24"> must all appear the same number of times.</p>
<h3>Acknowledgments</h3>
<p>Thanks to <a href="http://math.stackexchange.com/users/67848/karl-kronenfeld">Karl
Kronenfeld</a>
for corrections and many helpful suggestions.</p>
tag:blog.plover.com,2014:/math/IL-contradictionProof by contradiction2014-03-01T00:00:00Z2014-03-01T00:00:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>Intuitionistic logic is deeply misunderstood by people who have not
studied it closely; such people often seem to think that the
intuitionists were just a bunch of lunatics who rejected the law of
the excluded middle for no reason. One often hears that
intuitionistic logic rejects proof by contradiction. This is only half
true. It arises from a typically classical misunderstanding of
intuitionistic logic.</p>
<p>Intuitionists are perfectly happy to accept a reductio ad absurdum
proof of the following form:</p>
<p>$$(P\to \bot)\to \lnot P$$</p>
<p>Here <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cbot%24"> means an absurdity or a contradiction; <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%5cto%20%5cbot%24"> means that assuming
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> leads to absurdity, and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28P%5cto%20%5cbot%29%5cto%20%20%5clnot%20P%24"> means that if assuming <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">
leads to absurdity, then you can conclude that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is false. This
is a classic proof by contradiction, and it is intuitionistically
valid. In fact, in many formulations of intuitionistic logic, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24"> is
<em>defined</em> to mean <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%5cto%20%5cbot%24">.</p>
<p>What is rejected by intuitionistic logic is the similar-seeming claim
that:</p>
<p>$$(\lnot P\to \bot)\to P$$</p>
<p>This says that if assuming <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24"> leads to absurdity, you can conclude
that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is true. This is <em>not</em> intuitionistically valid.</p>
<p>This is where people become puzzled if they only know classical
logic. “But those are the same thing!” they cry. “You just have to
replace <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24"> in the first one, and you get the second.”</p>
<p>Not quite. If you replace <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> with <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24"> in the first one, you do not get the second
one; you get:</p>
<p>$$(\lnot P\to \bot)\to \lnot \lnot P$$</p>
<p>People familiar with classical logic are so used to shuffling the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%24">
signs around and treating <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24"> the same as <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> that they often don't
notice when they are doing it. But in intuitionistic logic, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24">
are not the same. <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24"> is weaker than <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">, in the sense that
from <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> one can always conclude <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24">, but not always vice versa. Intuitionistic logic
is happy to agree that if <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24"> leads to absurdity, then <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24">. But it
does not agree that this is sufficient to conclude <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">.</p>
<p>As is often the case, it may be helpful to try to understand
intuitionistic logic as talking about provability instead of truth.
In classical logic, <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> means that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is true and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24">
means that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is false. If <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is not false it is true, so <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">
mean the same thing. But in intuitionistic logic <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> means that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is
<em>provable</em>, and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20P%24"> means that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is not provable. <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24"> means that it is
impossible to prove that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is not provable.</p>
<p>If <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is provable, it is certainly impossible to prove that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is not
provable. So <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> implies <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24">. But just because it is impossible to
prove that there is no proof of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> does not mean that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> itself is
provable, so <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clnot%20%5clnot%20P%24"> does not imply <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">.</p>
<p>Similarly,</p>
<p>$$(P\to \bot)\to \lnot P $$</p>
<p>means that if a proof of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> would lead to absurdity, then we may conclude
that there cannot be a proof of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">. This is quite valid. But</p>
<p>$$(\lnot P\to \bot)\to P$$</p>
<p>means that if assuming that a proof of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> is impossible leads to
absurdity, there must be a proof of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">. But this itself isn't a
proof of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">, nor is it enough to prove <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24">; it only shows that
there is no proof that proofs of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24P%24"> are impossible.</p>
<p>[ Addendum 20141124: <a href="http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/">This article by Andrej Bauer</a> says much the same thing. ]</p>
tag:blog.plover.com,2014:/math/CauchyCauchy and the continuum2014-01-04T13:43:00Z2014-01-04T13:43:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>There is a famous mistake of Augustin-Louis Cauchy, in which he is
supposed to have "proved" a theorem that is false. I have seen this
cited many times, often in very serious scholarly literature, and as
often as not Cauchy's purported error is completely misunderstood, and
replaced with a different and completely dumbass mistake that nobody
could have made.</p>
<p>The claim is often made that Cauchy's <em>Course d'analyse</em> of 1821
contains a "proof" of the following statement: a convergent sequence
of continuous functions has a continuous limit. For example, <a href="https://en.wikipedia.org/w/index.php?title=Uniform_convergence&oldid=583507328#History">the
Wikipedia article on "uniform
convergence"</a>
claims:</p>
<blockquote>
<p>Some historians claim that Augustin Louis Cauchy in 1821 published a
false statement, but with a purported proof, that the pointwise
limit of a sequence of continuous functions is always continuous…</p>
</blockquote>
<p><a href="http://ncatlab.org/nlab/show/Cauchy+sum+theorem#statements">The nLab article on "Cauchy sum theorem"</a> states:</p>
<blockquote>
<p>Non-theorem (attributed to Cauchy, 1821). Let <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%3d%28f_1%2cf_2%2c%5cldots%29%24">
be an infinite sequence of continuous functions from the real line
to itself. Suppose that, for every real number <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24">, the sequence
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28f_1%28x%29%2c%20f_2%28x%29%2c%20%5cldots%29%24"> converges to some (necessarily unique)
real number <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_%5cinfty%28x%29%24">, defining a function <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_%5cinfty%24">; in
other words, the sequence <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f%24"> converges pointwise? to
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_%5cinfty%24">. Then <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_%5cinfty%24"> is also continuous.</p>
</blockquote>
<p>Cauchy never claimed to have proved any such thing, and it beggars
belief that Cauchy could have made such a claim, because the
counterexamples are so many and so easily located. For example, the
sequence <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%20f_n%28x%29%20%3d%20x%5en%24"> on the interval <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5b%2d1%2c1%5d%24"> is a sequence of
continuous functions that converges everywhere on <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5b0%2c1%5d%24"> to a
discontinuous limit. You would have to be a mathematical ignoramus to
miss this, and Cauchy wasn't. </p>
<p>Another simple example, one that converges everywhere in <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cmathbb%0aR%24">, is any sequence of functions <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_n%24"> that are everywhere zero,
except that each has a (continuous) bump of height 1 between
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%2d%5cfrac1n%24"> and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac1n%24">. As <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%5cto%5cinfty%24">, the width of the
bump narrows to zero, and the limit function <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_%5cinfty%24"> is
everywhere zero except that <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_%5cinfty%280%29%3d1%24">. Anyone can think of
this, and certainly Cauchy could have. A concrete example of this type
is <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=f_n%28x%29%20%3d%20e%5e%7b%2dx%5e%7b2%7d%2fn%7d"> which converges to 0
everywhere except at <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%20x%3d0%20%24">, where it converges to 1.</p>
<p>Cauchy's controversial theorem is not what Wikipedia or nLab claim.
It is that that the pointwise limit of a convergent <strong>series</strong> of
continuous functions is always continuous. Cauchy is not claiming that
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=f_%5cinfty%28x%29%20%3d%20%5clim_%7bi%5cto%5cinfty%7d%20f_i%28x%29"> must be continuous if the
limit exists and the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_i%24"> are continuous. Rather, he claims that
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=S%28x%29%20%3d%20%5csum_%7bi%3d1%7d%5e%5cinfty%20f_i%28x%29"> must be continuous if
the sum converges and the <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24f_i%24"> are continuous. This is a
completely different claim. It premise, that the sum converges, is
much stronger, and so the claim itself is much weaker, and so much
more plausible. </p>
<p>Here the counterexamples are not completely trivial. Probably the
best-known counterexample is that a square wave (which has a jump
discontinuity where the square part begins and ends) can be
represented as a Fourier series.</p>
<p>(Cauchy was aware of this too, but it was new mathematics in 1821.
Lakatos and others have argued that the theorem, understood in the way
that continuity was understood in 1821, is not actually erroneous, but
that the idea of continuity has changed since then. One piece of
evidence strongly pointing to this conclusion is that nobody
complained about Cauchy's controversial theorem until 1847. But had
Cauchy somehow, against all probability, mistakenly claimed that a
<em>sequence</em> of continuous functions converges to a continuous limit,
you can be sure that it would not have taken the rest of the
mathematical world 26 years to think of the counterexample of
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%5en%24">.)</p>
<p>The confusion about Cauchy's controversial theorem arises from a
perennially confusing piece of mathematical terminology: a convergent
<em>sequence</em> is not at all the same as a convergent <em>series</em>. Cauchy
claimed that a convergent <em>series</em> of continuous functions has a
continuous limit. He did not ever claim that a convergent <em>sequence</em>
of continuous functions had a continuous limit. But I have often
encountered claims that he did that, even though such such claims are
extremely implausible.</p>
<p>The claim that Cauchy thought a sequence of continuous functions
converges to a continuous limit is not only false but is manifestly
so. Anyone making it has at best made a silly and careless error, and
perhaps doesn't really understand what they are talking about, or
hasn't thought about it.</p>
<p>[ I had originally planned to write about this controversial theorem
in <a href="http://blog.plover.com/math/major-screwups.html">my series of articles about major screwups in
mathematics</a>, but the
longer and more closely I looked at it the less clear it was that
Cauchy had actually made a mistake. ]</p>