The Universe of DiscourseThe Universe of Discourse (Mark Dominus Blog)tag:blog.plover.com,2005:/mathBlosxomhttp://perl.plover.com/favicon.ico2014-11-22T00:00:00Ztag:blog.plover.com,2014:/math/algebraWithin this instrument, resides the Universe2014-11-22T00:00:00Z2014-11-22T00:00:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>When opportunity permits, I have been trying to teach my ten-year-old
daughter 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 Ms. 10 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>Ms. 10 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. Ms. 10'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>Ms. 10 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. Ms. 10 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 Ms. 10 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. Ms. 10 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 Ms. 10 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-23T00:00:00Z2014-07-23T00:00: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%7b0%2c%5cldots%202%5en%2d1%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%7b0%5cldots%207%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%7b0%5cldots%0a7%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>$$\pi \approx 3 $$</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%7b0%2c1%2c2%2c4%5c%7d%2c%20%5c%7b1%2c3%2c6%2c4%5c%7d%2c%20%5c%7b2%2c5%2c2%2c5%5c%7d%24">, and <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%7b3%2c7%2c6%2c5%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=%245720_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%7b5%2c1%2c2%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%7b5%2c1%2c2%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%7b0%2c1%2c3%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%7b0%2c%5cldots%207%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%7b0%2c1%2c3%2c5%2c7%2c15%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%7b0%2c1%2c3%2c5%2c7%2c9%2c11%2c13%2c15%2c21%2c23%2c27%2c31%2c63%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,2013:/math/affine-spaceAffine spaces in programming2013-12-23T15:22:00Z2013-12-23T15:22:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>In <a href="http://blog.plover.com/prog/Moonpig.html">my long article about Moonpig</a> I said
that date-time values form an <em>affine space</em>, and that this should
remind C programmers of pointer arithmetic, because the C address
space is also an affine space. This concept shows up surprisingly
often in programming, and deserves to be better known among
programmers. I will take the date-time values as my main example.</p>
<h3>Affine spaces</h3>
<p>An affine space contains two kinds of things, which are generically
called <em>points</em> and <em>vectors</em>. Vectors represent displacements
between points, some sort of “what you have to do to get from point
<em>a</em> to point <em>b</em>”. In the example of dates, the dates are the
points. The vectors in this case are <em>time intervals</em>, things like
"three days" and "142 hours".</p>
<p>The key thing about an affine space is that points can be subtracted,
but not added. Subtracting two points does not yield a point; instead
it yields a <em>vector</em> that says how you have to go to get from the
second point to the first. In the example of dates, the result of
subtracting two dates is the time interval that elapses between
them. For example, if you subtract 10 January 2014 from 14 January
2014, the result is the time interval of 4 days. If you subtract 14
January 2014 from 10 January 2014, the result is -4 days.</p>
<p>Suppose that <em>a</em> and <em>b</em> are points and that <em>u</em> is a vector and that
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%2da%20%3d%20u%24">. Then
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%20%3d%20a%2bu%24">, which means that if you start at point <em>a</em> and
then make the motion described by vector <em>u</em>, you arrive at <em>b</em>. You
could also start at <em>b</em> and do <em>u</em> backwards to arrive at <em>a</em>; this is
written <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%3d%20b%20%2b%20%28%2du%29%24">. Here -<em>u</em> is shorthand for
<img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28%2d1%29%5ccdot%20u%24">.</p>
<p>For the addition and subtraction to make sense, they should obey some
laws also:</p>
<p><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%0a%5cbegin%7balign%7d%0a%28a%20%2b%20u%29%20%2b%20v%20%26%20%3d%20a%20%2b%20%28u%2bv%29%20%5c%5c%5c%5c%0a0%20%2b%20u%20%26%3d%20u%0a%5cend%7balign%7d%0a"></p>
<p>Also, for every points <em>a</em> and <em>b</em>, there must be <em>exactly one</em> vector
<em>v</em> for which <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%2b%20v%20%3d%20b%24">. This unique <em>v</em> is the
subtraction of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%20%2da%24">.</p>
<p>What you <em>cannot</em> do is add two points. You can add two vectors as
usual, but points don't add. That is what makes it an affine space.</p>
<p>That was all very abstract, so let's have an example. I promised that
date-time values would form an affine space. The points of this space
are particular date-time values, such as “April 2, 1969 at 02:38:00
Eastern Standard Time”. The vectors are time <em>intervals</em>, such as
"three hours, nine minutes and 12 seconds" or "86400 seconds". The
scalars are just numbers. You can add a time interval to any point in
time. For example, April 2, 1969 at 02:38:00 Eastern Standard Time
plus 86400 seconds is April 3, 1969 at 02:38:00 Eastern Standard Time.</p>
<p>You can also subtract an interval from a point, which is the same as
adding its negative. Adding negative 86400 seconds to the point
“April 2, 1969 at 02:38:00 Eastern Standard Time” yields the point
“April 1, 1969 at 02:38:00 Eastern Standard Time”.</p>
<p>You can <em>subtract</em> two points, which yields the interval of time that
separates them. For example,
“April 2, 1969 at 02:38:00
Eastern Standard Time” minus “April 2, 1969 at 02:38:46
Eastern Standard Time” is the interval -46 seconds.</p>
<h3>Vector spaces</h3>
<p>First we should discuss vector spaces, which may be more familiar, and
are one of the key ingredients of affine spaces. The elements of a
vector space are called <em>vectors</em>, and there are two important
operations on vectors:</p>
<ol>
<li>Two vectors can be <em>added</em>, to yield a new vector</li>
<li>A vector can be <em>scaled</em>, which means it can be multiplied by a
<em>scalar</em> value, which is just an ordinary number. This yields a new
vector.</li>
</ol>
<p>There is also one special vector, called the <em>zero vector</em>, denoted
0. If <em>u</em>, <em>v</em>, and <em>w</em> are vectors, and <em>s</em> and <em>t</em> are scalars, then the
following laws must hold:</p>
<p align=center><img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%0a%24%24%5cbegin%7balign%7d%0au%20%2b%20%28v%20%2b%20w%29%20%26%20%3d%20%28u%2bv%29%20%2b%20w%20%5c%5c%5c%5c%0au%20%2b%20v%20%26%20%3d%20v%20%2b%20u%20%5c%5c%5c%5c%0as%5ccdot%28u%20%2b%20v%29%20%26%20%3d%20%28s%5ccdot%20u%29%20%2b%20%28s%5ccdot%20v%29%20%5c%5c%5c%5c%0a%28s%2bt%29%5ccdot%20u%20%26%20%3d%20%28s%5ccdot%20u%29%20%2b%20%28t%5ccdot%20u%29%20%5c%5c%5c%5c%20%5chline%0as%5ccdot%28t%5ccdot%20u%29%20%26%20%3d%20st%5ccdot%20u%20%5c%5c%5c%5c%0a1%5ccdot%20u%20%26%3d%20u%20%5c%5c%5c%5c%0a0%20%2b%20u%20%3d%20u%20%2b%200%20%26%3d%20u%0a%5cend%7balign%7d%24%24%0a"></p>
<p>Vectors represent some sort of uniform motion in some direction. The
zero vector represents no motion. Adding two vectors means moving one
way, then another. Scaling a vector <em>u</em> by a scalar <em>s</em> means
computing the motion that moves the same direction as <em>u</em>, but <em>s</em>
times as far.</p>
<h3>More examples</h3>
<p>Temperatures are affine spaces. The points are particular absolute
temperatures, such as 26 degrees Celsius, absolute zero, and the
melting point of platinum. The vectors are temperature intervals,
such as 13 kelvins or 273 kelvins. You can add an interval to a
temperature and get a different temperature, or you can subtract two
temperatures and find the interval between them, but adding
temperatures is meaningless.</p>
<p>Notice that The Celsius and the absolute Kelvin spaces have different
points, but the same vectors. 100°C and 50°C are not at all the
same as 100 Kelvins and 50 Kelvins. But nevertheless, 100°C-50°C =
100K-50K! They are not only numerically equal, they are <em>the same
thing</em>.</p>
<p>This is analogous to the way times can exist in many
different calendars, and may not be directly comparable, and yet we
can say that the <em>difference</em> between two times in one calendar might
be equal to the difference of two times in another calendar. Days in
the Hebrew calendar do not match up exactly with days in the
conventional civil
calendar; they start and end at sunset, whereas the civil calendar
starts and ends at midnight. But you can still say that a certain
Hebrw calendar day laster exactly 86,400 seconds, and if you do, it is
the same length as an 86,400-second conventional calendar day.</p>
<p>A C array is an affine space. The points are pointers to array
elements. The vectors are integers. You can subtract one pointer
from another to find the integer number of array elements between
them. You can add an integer to a pointer to get a pointer to a
different element. But adding pointers is meaningless and is a
compiler error.</p>
tag:blog.plover.com,2013:/math/CauchyCauchy and the continuum2013-01-02T00:00:00Z2013-01-02T00:00: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>
tag:blog.plover.com,2012:/math/russellElaborations of Russell's paradox2012-01-10T18:46:00Z2012-01-10T18:46:00ZMark Dominushttp://www.plover.com/mjd@plover.com
When Iris was five or six, I told her about Russell's paradox in the
following form: in a certain library, some books are catalogs that
contain lists of other books. For example, there is a catalog of all
the books on the second floor, and a catalog of all the books about
birds. Some catalogs might include themselves. For example, the
catalog of all the books in the library certainly includes itself.
Such catalogs have red covers; the other catalogs, which do not
include themselves, such as the catalog of all the plays of
Shakespeare, have blue covers. Now is there a catalog of all the
catalogs with blue covers?<p>
I wasn't sure she would get this, but it succeeded much better than I
expected. After I prompted her to consider what color cover it would
have, she thought it out, first ruling out one color, and then, when
she got to the second color, she just started laughing.<p>
A couple of days ago she asked me if I could think of anything that
was like that but with three different colors. Put on the spot, I
suggested she consider what would happen if there could be green
catalogs that might or might not include themselves. This is
somewhat interesting, because you now <i>can</i> have a catalog of
all the blue catalogs; it can have a green cover. But I soon thought
of a much better extension.<p>
I gave it to Iris like this: say you have a catalog, let's call it
<i>X</i>. If <i>X</i> mentions a catalog that mentions <i>X</i>, it
has a gold stripe on the spine. Otherwise, it has a silver stripe.
Now:<p>
<ol>
<li>Could there be a red catalog with a gold stripe?
<li>Could there be a red catalog with a silver stripe?
<li>Could there be a blue catalog with a gold stripe?
<li>Could there be a blue catalog with a silver stripe?
</ol>
And more interesting:<p>
<ol start=5>
<li>Is there a catalog of all the catalogs with gold stripes?
<li>Is there a catalog of all the catalogs with silver stripes?
</ol>
I knew that early 20th century logicians, trying to repair the Russell paradox,
first tried a very small patch: since comprehension over the predicate
<i>X</i>∉<i>X</i> causes problems, just forbid that
predicate. This unfortunately doesn't solve the problem at all; there
are an infinite number of equally problematic predicates. (Whitehead
and Russell's theory of types is an attempt to fix this; Quine's New
Foundations is a different attempt.) One of these predicates is
¬∃Y.X∈Y and Y∈X. You can't construct the set of all
<i>X</i> such that ¬∃Y.X∈Y and Y∈X because there is no
such set, for reasons similar to the reason why there's no set of all
<i>X</i> such that <i>X</i>∉<i>X</i>, so that's where I got the
silver stripe predicate.<p>
Translating this into barber language is left as an exercise for the
reader.<p>
tag:blog.plover.com,2011:/math/concertsConcerts2011-06-11T17:35:00Z2011-06-11T17:35:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<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">Unknown book with tag 'Tao problems'</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/0000000000"></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/0000000000"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/0000000000"><font size="-1">no kickback</font></a>
</td></tr></table></div>
At a book sale I recently picked up Terence Tao's little book on
problem solving for 50¢. One of the exercises
(pp. 85–86) is the following little charmer: There are six
musicians who will play a series of concerts. At each concert, some
of the musicians will be on stage and some will be in the audience.
What is the fewest number of concerts that can be played to that each
musician gets to see the each of the others play?<p>
Obviously, no more than six concerts are required. (I have a new
contribution to the long-debated meaning of the mathematical jargon
term "obviously": if my six-year-old daughter could figure out the
answer, so can you.) And an easy argument shows that four are
necessary: let's say that when a musician views another, that is a
"viewing event"; we need to arrange at least 5×6 = 30 viewing
events. A concert that has <i>p</i> performers and 6-<i>p</i>
in the audience arranges <i>p</i>(6 - <i>p</i>) events, which must be
5, 8, or 9. Three concerts yield no more than 27 events, which is
insufficient. So there must be at least 4 concerts, and we may as
well suppose that each concert has three musicians in the audience and
three onstage, to maximize the number of events at 9·4 =
36. (It turns out there there is no solution otherwise, but that is a
digression.)<p>
Each musician must attend at least 2 concerts, or else they would see
only 3 other musicians onstage. But 6 musicians attending 2 concerts
each takes up all 12 audience spots, so every musician is at exactly 2
concerts. Each musician thus sees exactly six musicians onstage, and
since five of them must be different, one is a repeat, and the viewing
event is wasted. We knew there would be some waste, since there are
36 viewing avents available and only 30 can be useful, but now we know
that each spectator wastes exactly one event.<p>
A happy side effect of splitting the musicians evenly between the
stage and the audience in every concert is that we can exploit the
symmetry: if we have a solution to the problem, then we can obtain a
dual solution by exchanging the performers and the audience in each
concert. The conclusion of the previous paragraph is that in any
solution, each spectator wastes exactly one event; the duality tells
us that each performer is the subject of exactly one wasted event.<p>
Now suppose the same two musicians, say <i>A</i> and <i>B</i>, perform
together twice. We know that some spectator must see <i>A</i> twice;
this spectator sees <i>B</i> twice also, this wasting two events. But
each spectator wastes only one event. So no two musicians can share
the stage twice; each two musicians share the stage exactly once. By
duality, each two spectators are in the same audience together exactly
once.<p>
So we need to find four 3-sets of the elements { A, B, C, D, E, F }, with
each element appearing in precisely two sets, and such that each two
sets have exactly one element in common.<p>
Or equivalently, we need to find four triangles in <i>K</i><sub>4</sub>, none of which
share an edge.<p>
The solution is not hard to find:<p>
<p align=center>
<table cellpadding=2>
<tr><td > <td bgcolor="pink" align="center">1<td bgcolor="white" align="center">2<td bgcolor="pink" align="center">3<td bgcolor="white" align="center">4
<tr><td align="center">On stage<td bgcolor="pink" align="center">A B C<td bgcolor="white" align="center">C D E<td bgcolor="pink" align="center">E F A<td bgcolor="white" align="center">B D F
<tr><td align="center">In audience<td bgcolor="pink" align="center">D E F<td bgcolor="white" align="center">A B F<td bgcolor="pink" align="center">B C D<td bgcolor="white" align="center">A C E
</table>
</p>
And in fact this solution is essentially unique.<p>
If you generalize these arguments to 2<i>m</i> musicians, you find
that there is a lower bound of <img src="https://chart.googleapis.com/chart?chf=bg,s,00000000&cht=tx&chl=%5cleft%5clceil%7b4m%5e2%20%2d%202m%20%5cover%20m%5e2%20%7d%5cright%5crceil"> concerts,
which is 4. And indeed, even with as few as 4 musicians, you still need four
concerts. So it's tempting to wonder if 4 concerts is really
sufficient for all even numbers of musicians. Consider 8 musicians,
for example. You need 56 viewing events, but a concert with half
the musicians onstage and half in the audience provides 16 events, so you
might only need as few as 4 concerts to provide the necessary
events.<p>
The geometric formulation is that you want to find four
disjoint <i>K</i><sub>4</sub>s in a <i>K</i><sub>4</sub>; or alternatively, you want to find four
4-element subsets
of { 1,2,3,4,5,6,7,8 }, such that each element appears in exactly two
sets and no two elements are in the same. There seemed to be no immediately obvious
reason that this wouldn't work, and I spent a while tinkering around
looking for a way to do it and didn't find one. Eventually I did an
exhaustive search and discovered that it was impossible.<p>
But the tinkering and the exhaustive search were a waste of time,
because there <i>is</i> an obvious reason why it's impossible. As
before, each musician must be in exactly two audiences, and can share
audiences with each other musician at most once. But there are only 6
ways to be in two audiences, and 8 musicians, so some pair of
musicians must be in precisely the same pair of audiences, this wastes
too many viewing events, and so there's no solution. Whoops!<p>
It's easy to find solutions for 8 musicians with 5 concerts, though.
There is plenty of room to maneuver and you can just write one down
off the top of your head. For example:<p>
<p align=center>
<table cellpadding=2 >
<tr><td align="center"> <td bgcolor="pink" align="center">1<td bgcolor="white" align="center">2<td bgcolor="pink" align="center">3<td bgcolor="white" align="center">4<td bgcolor="pink" align="center">5
<tr><td " align="center">On stage <td bgcolor="pink" align="center">E F G H<td bgcolor="white" align="center">B C D H<td bgcolor="pink" align="center">A C D F G<td bgcolor="white" align="center">A B D E G<td bgcolor="pink" align="center">A B C E F H
<tr><td align="center">In audience<td bgcolor="pink" align="center">A B C D<td bgcolor="white" align="center">A E F G<td bgcolor="pink" align="center">B E H <td bgcolor="white" align="center">C F H <td bgcolor="pink" align="center">D G
</table>
</p>
Actually I didn't write this one down off the top of my head; I have a
method that I'll describe in a future article. But this article has
already taken me several weeks to get done, so I'll stop here for
now.<p>
[ Addendum: For <i>n</i> = 1…10 musicians, the least number of
concerts required is 0, 2, 3, 4, 4, 4, 5, 5, 5, 5; beyond this, I only
have bounds. ]<p>
tag:blog.plover.com,2010:/math/topology-docA draft of a short introduction to topology2010-11-15T18:31:00Z2010-11-15T18:31:00ZMark Dominushttp://www.plover.com/mjd@plover.com
One of my ongoing projects is to figure out how to explain topology
briefly. For example, <a href="http://blog.plover.com/math/metric.html">What is
Topology?</a>, putatively part 1 of a three-part series that I have
not yet written parts 2 or 3 of yet.<p>
CS grad students often have to take classes in category theory. These
classes always want to use groups and topological spaces as examples,
and my experience is that at this point many of the students shift
uncomfortably in their seats since they have not had undergraduate
classes in group theory, topology, analysis, or anything else
relevant. But you do not have to know much topology to be able to
appreciate the example, so I tried to write up the minimal amount
necessary. Similarly, if you already understand intuitionistic logic,
you do not need to know much topology to understand the way in which
topological spaces are natural models for intuitionistic
logic—but you do need to know more than zero.<p>
So a couple of years ago I wrote up a short introduction to topology
for first-year computer science grad students and other people who
similarly might like to know the absolute minimum, and only the
absolute minimum, about topology. It came out somewhat longer than I
expected, 11 pages, of which 6 are the introduction, and 5 are about
typical applications to computer science. But it is a very light,
fluffy 11 pages, and I am generally happy with it.<p>
I started writing this shortly after my second daughter was born, and
I have not yet had a chance to finish it. It contains many errors.
Many, many errors. For example, there is a section at the end about
the <a
href="http://en.wikipedia.org/wiki/Compactness_theorem">compactness
principle</a>, which can only be taken as a sort of pseudomathematical
lorem ipsum. This really is a draft; it is only three-quarters
finished.<p>
But I do think it will serve a useful function once it is finished,
and that finishing it will not take too long. If you have any
interest in this project, I invite you to help.<p>
The current draft is version <b>0.6</b> of <b>2010-11-14</b>. I do
not want old erroneous versions wandering around confusing people in
my name, so please do not distribute this draft after
<b>2010-12-15</b>. I hope to have an improved draft available here
before that.<p>
Please do send me corrections, suggestions, questions, advice,
patches, pull requests, or anything else.<p>
<ul>
<li><a href="http://pic.blog.plover.com/math/topology-doc/topology-draft-0.6.pdf">PDF</a><br>
<li><a href="http://pic.blog.plover.com/math/topology-doc/topology-draft-0.6.tex">LaTeX source</a>
<li><a href="https://github.com/mjdominus/topology-doc">Github git
repository</a> (<tt>git://github.com/mjdominus/topology-doc.git</tt>)
</ul>
tag:blog.plover.com,2010:/math/semiSemi-boneless ham2010-11-08T18:11:00Z2010-11-08T18:11:00ZMark Dominushttp://www.plover.com/mjd@plover.com
The Math Project on Wikipedia is having a discussion about whether or
not to have an article about the jargon term "semi-infinite", which I
have long considered one of my favorite jargon terms, because it
sounds so strange, but makes so much sense. A structure is
semi-infinite when it is infinite in one direction but not in the
other. For example, the set of positive integers is semi-infinite,
since it possesses a least element (1) but no greatest element.
Similarly rays in geometry are semi-infinite.<p>
The term is informal, however, and it's not clear just what it should
mean in all cases. For example, consider the set <i>S</i> of
1/<i>n</i> for every positive integer <i>n</i>. Is this set
semi-infinite? It is bounded in both directions, since it is
contained in [0, 1]. But as you move left through the set, you
ancounter an infinite number of elements, so it ought to be
semi-infinite in the same sense that <i>S</i> ∪ { 1-<i>x</i> :
<i>x</i> ∈ <i>S</i> } is fully-infinite. Whatever sense that is.<p>
Informal and ill-defined it may be, but the term is widely used; one
can easily find mentions in the literature of semi-infinite paths,
semi-infinite strips, semi-infinite intervals, semi-infinite
cylinders, and even semi-infinite reservoirs and conductors.<p>
<img src="http://pic.blog.plover.com/math/semi/Sextant.png" align="left"/> <img
src="http://pic.blog.plover.com/math/semi/hyperbola.png" align="right"/> The term has spawned an
offshoot, the even stranger-sounding "quarter-infinite". This seems
to refer to a geometric object that is unbounded in the same way that
a quarter-plane is unbounded, where "in the same way" is left rather
vague. Consider the set (depicted at left) of all points of the plane
for which 0 ≤ |<i>y</i>/<i>x</i>| ≤ √3, for example; is
this set quarter-infinite, or only 1/6-infinite? Is the set of points
(depicted at right) with <i>xy</i> > 1 and <i>x</i>, <i>y</i> >
0 quarter-infinite? I wouldn't want to say. But the canonical
example is simple: the product of two semi-infinite intervals is a
quarter-infinite set.<p>
I was going to say that I had never seen an instance of the obvious
next step, the eighth-infinite solid, but in researching this article I
did run into a few. I can't say it trips off the tongue, however.
And if we admit that a half of a quarter-infinite plane segment is
also eighth-infinite, we could be getting ourselves into trouble.<p>
(This all reminds me of the complaint of J.H. Conway of the
increasing use of the term "biunique". Conway sarcastically asked if
he should expect to see "triunique" and soforth, culminating in the
idiotic "polyunique".)<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">General Topology</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/0387901256"><IMG SRC="http://www.powells.com/cgi-bin/imageDB.cgi?isbn=0387901256" BORDER="0" ALIGN="center" ALT="General Topology" ></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/0387901256"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/0387901256"><font size="-1">no kickback</font></a>
</td></tr></table></div>
Sometimes "semi" really does mean exactly one-half, as in "semimajor
axis" (the longest segment from the center of an ellipse to its
boundary), "semicubic parabola" (determined by an equation with a term
<i>kx</i><sup>3/2</sup>), or "semiperimeter" (half the perimeter of a
triangle). But just as often, "semi" is one of the dazzling supply of
mathematical pejoratives. ("Abnormal, irregular, improper,
degenerate, inadmissable, and otherwise undesirable", says Kelley's
<cite>General Topology</cite>.) A semigroup, for example, is not half of a
group, but rather an algebraic structure that possesses less structure
than a group. Similarly, one has semiregular polyhedra and semidirect
products.<p>
I was planning to end with a note that mathematics has so far avoided
the "demisemi-" prefix. But alas! Google found this 1971 paper on <a
href="http://www.springerlink.com/content/r225012888j46612/">Demi-semi-primal
algebras and Mal'cev-type conditions</a>.<p>
tag:blog.plover.com,2009:/math/GdlAnother short explanation of Gödel's theorem2009-12-14T15:27:00Z2009-12-14T15:27:00ZMark Dominushttp://www.plover.com/mjd@plover.com
In <a href="http://blog.plover.com/math/Gdl-Smullyan.html">yesterday's article</a>, I
said:<p>
<blockquote>
A while back I started writing up an article titled "World's shortest
explanation of Gödel's theorem". But I didn't finish it...
</blockquote><p> <!-- I started it on 2008-01-09 -->
I went and had a look to see what was wrong with it, and to my
surprise, there seemed to be hardly anything wrong with it. Perhaps I
just forgot to post it. So if you disliked yesterday's brief
explanation of Gödel's theorem—and many people did—you'll probably
dislike this one even more. Enjoy!<p>
<hr>
A reader wrote to question my characterization of Gödel's theorem in <a href="http://blog.plover.com/math/major-screwups.html">the
previous article</a>. But I think I characterized it correctly; I
said:<p>
<blockquote>
The only systems of mathematical axioms strong enough to prove all
true statements of arithmetic, are those that are so strong that they
also prove all the false statements of arithmetic.
</blockquote>
I'm going to explain how this works.<p>
You start by choosing some system of mathematics that has some
machinery in it for making statements about things like numbers and for
constructing proofs of theorems like 1+1=2. Many such systems exist.
Let's call the one we have chosen
<i>M</i>, for "mathematics". <p>
Gödel shows that if <i>M</i> has enough mathematical machinery in it to
actually do arithmetic, then it is possible to produce a statement
<i>S</i> whose meaning is essentially "Statement <i>S</i> cannot be
proved in system <i>M</i>."<p>
It is not at all obvious that this is possible, or how it can be done,
and I am not going to get into the details here. Gödel's contribution
was seeing that it <i>was</i> possible to do this.<p>
So here's <i>S</i> again:<p>
<blockquote>
<i>S</i>: Statement <i>S</i> cannot be
proved in system <i>M</i>.
</blockquote><p>
Now there are two possibilities. Either <i>S</i> is in fact provable
in system <i>M</i>, or it is not. One of these must hold.<p>
If <i>S</i> is provable in system <i>M</i>, then it is false, and so
it is a false statement that can be proved in system <i>M</i>.
<i>M</i> therefore proves some false statements of arithmetic.<p>
If <i>S</i> is not provable in system <i>M</i>, then it is true, and
so it is a true statement that cannot be proved in system <i>M</i>.
<i>M</i> therefore fails to prove some true statements of
arithmetic.<p>
So something goes wrong with <i>M</i>: either it fails to prove some
true statements, or else it succeeds in proving some false
statements. <p>
List of topics I deliberately omitted from this article, that
mathematicians should not write to me about with corrections:
Presburger arithmetic. Dialetheism. Inexhaustibility.
ω-incompleteness. Non-RE sets
of axioms.<p>
<hr>
<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">Godel's Theorem: An Incomplete Guide to Its Use and Abuse</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/9781568812388"><IMG SRC="http://pic.blog.plover.com/covers/FranzenGodel.jpg" BORDER="0" ALIGN="center" ALT="Godel's Theorem: An Incomplete Guide to Its Use and Abuse" ></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/9781568812388"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/9781568812388"><font size="-1">no kickback</font></a>
</td></tr></table></div><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">Inexhaustibility: A Non-Exhaustive Treatment</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/9781568811756"><IMG SRC="http://www.powells.com/cgi-bin/imageDB.cgi?isbn=9781568811756" BORDER="0" ALIGN="center" ALT="Inexhaustibility: A Non-Exhaustive Treatment" ></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/9781568811756"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/9781568811756"><font size="-1">no kickback</font></a>
</td></tr></table></div>
Well, I see now that left out the step where I go from "<i>M</i>
proves a false statement" to "<i>M</i> proves all false statements".
Oh well, another topic for another post. <p>
If you liked this post, you may
enjoy Torkel Franzén's books <cite>Godel's Theorem: An Incomplete
Guide to Its Use and Abuse</cite> and <cite>Inexhaustibility: A
Non-Exhaustive Treatment</cite>. If you disliked this post, you are
even more likely to enjoy them.<p>
<br clear=all>
<hr>
Many thanks to Robert Bond for his contribution.<p>
tag:blog.plover.com,2009:/math/Gdl-SmullyanWorld's shortest explanation of Gödel's theorem2009-12-13T10:05:00Z2009-12-13T10:05:00ZMark Dominushttp://www.plover.com/mjd@plover.com
A while back I started writing up an article titled "World's shortest
explanation of Gödel's theorem". But I didn't finish it, and
later I encountered Raymond Smullyan's version, which is much shorter
anyway. So here, shamelessly stolen from Smullyan, is the World's
shortest explanation of Gödel's theorem.<p>
We have some sort of machine that prints out statements in some sort
of language. It needn't be a statement-printing machine exactly; it
could be some sort of technique for taking statements and deciding if
they are true. But let's think of it as a machine that prints out
statements. <p>
In particular, some of the statements that the machine might (or might
not) print look like these:<p>
<table align=center>
<tr><td align=right><tt>P*</tt><i>x</i>
<td>(which means that
<td>the machine will print <i>x</i>)
<tr><td align=right><tt>NP*</tt><i>x</i>
<td>(which means that
<td>the machine will never print <i>x</i>)
<tr><td align=right><tt>PR*</tt><i>x</i>
<td>(which means that
<td>the machine will print <i>xx</i>)
<tr><td align=right><tt>NPR*</tt><i>x</i>
<td>(which means that
<td>the machine will never print <i>xx</i>)
</table><p>
For example, <tt>NPR*FOO</tt> means that the machine will never print
<tt>FOOFOO</tt>. <tt>NP*FOOFOO</tt> means the same thing. So far, so
good.<p>
Now, let's consider the statement <tt>NPR*NPR*</tt>. This statement
asserts that the machine will never print <tt>NPR*NPR*</tt>.<p>
Either the machine prints <tt>NPR*NPR*</tt>, or it never prints
<tt>NPR*NPR*</tt>.<p>
If the machine prints <tt>NPR*NPR*</tt>, it has printed a false
statement. But if the machine never prints <tt>NPR*NPR*</tt>, then
<tt>NPR*NPR*</tt> is a true statement that the machine never
prints.<p>
So either the machine sometimes prints false statements, or there are
true statements that it never prints.<p>
So any machine that prints only true statements must fail to print
some true statements.<p>
Or conversely, any machine that prints every possible true statement
must print some false statements too.<p>
<hr>
<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">5000 B.C. and Other Philosophical Fantasies</font></cite><br>
<A HREF="http://www.powells.com/partner/29575/biblio/9780312295170"><IMG SRC="http://pic.blog.plover.com/covers/5000BC.jpg" BORDER="0" ALIGN="center" ALT="5000 B.C. and Other Philosophical Fantasies" ></a><BR>
<A HREF="http://www.powells.com/partner/29575/biblio/9780312295170"><font size="-1">with kickback</font></a><br>
<A HREF="http://www.powells.com/biblio/9780312295170"><font size="-1">no kickback</font></a>
</td></tr></table></div>
The proof of Gödel's theorem shows that there are statements of
pure arithmetic that essentially express <tt>NPR*NPR*</tt>; the trick
is to find some way to express <tt>NPR*NPR*</tt> as a statement about
arithmetic, and most of the technical details (and cleverness!) of
Gödel's theorem are concerned with this trick. But once the
trick is done, the argument can be applied to any machine or other
method for producing statements about arithmetic.<p>
The conclusion then translates directly: any machine or method that
produces statements about arithmetic either sometimes produces false
statements, or else there are true statements about arithmetic that it
never produces. Because if it produces something like
<tt>NPR*NPR*</tt> then it is wrong, but if it fails to produce
<tt>NPR*NPR*</tt>, then that is a true statement that it has failed to
produce.<p>
So any machine or other method that produces only true statements
about arithmetic must fail to produce some true statements.<p>
Hope this helps!<p>
(This explanation appears in Smullyan's book <cite>5000 BC and Other
Philosophical Fantasies</cite>, chapter 3, section 65, which is where
I saw it. He discusses it at considerable length in Chapter 16 of
<cite>The Lady or the Tiger?</cite>, "Machines that Talk About
Themselves". It also appears in <cite>The Mystery of
Scheherezade</cite>.)<p>
<br clear=all>
<hr>
I gratefully acknowledge Charles Colht for his generous donation to
this blog.<p>
<hr>
[ Addendum 20091214: <a href="http://blog.plover.com/math/Gdl.html">Another article
on the same topic</a>. ]<p>
tag:blog.plover.com,2009:/math/gray-codesGray code at the pediatrician's office2009-06-21T15:14:00Z2009-06-21T15:14:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<img style="float: left; margin-right: 2em;" src="http://pic.blog.plover.com/math/gray-codes/bin.png">
<img style="float: right; margin-left: 2em;" src="http://pic.blog.plover.com/math/gray-codes/gray.png">
Last week we took Iris to the pediatrician for a checkup, during which
they weighed, measured, and inoculated her. The measuring device,
which I later learned is called a stadiometer, had a bracket on a slider that went up and down on a
post. Iris stood against the post and the nurse adjusted the bracket
to exactly the top of her head. Then she read off Iris's height from
an attached display.<p>
How did the bracket know exactly what height to report? This was done
in a way I hadn't seen before. It had a
photosensor looking at the post, which was printed with this
pattern:<p>
<p align=center><a href="http://pic.blog.plover.com/math/gray-codes/index200.html"><img
src="http://pic.blog.plover.com/math/gray-codes/17895976833.jpg" border=0></a></p>
(Click to view the other pictures I took of the post.)<p>
The pattern is binary numerals. Each numeral is a certain fraction of
a centimeter high, say 1/4 centimeter. If the sensor reads the number
433, that means that the bracket is 433/4 = 108.25 cm off the ground,
and so that Iris is 108.25 cm tall.<p>
The patterned strip in the left margin of this article is a
straightforward translation of binary numerals to black and white
boxes, with black representing 1 and white representing 0:<p>
<blockquote>
0000000000<br>
0000000001<br>
0000000010<br>
0000000011<br>
0000000100<br>
0000000101<br>
0000000101<br>
...<br>
1111101000<br>
1111101001<br>
...<br>
1111111111<br>
</blockquote>
If you are paying attention, you will notice that although the strip
at left is similar to the pattern in the doctor's office, it is not
the same. That is because the numbers on the post are Gray-coded.<p>
Gray codes solve the following problem with raw binary numbers.
Suppose Iris is close to 104 = 416/4 cm tall, so that the photosensor is in
the following region of the post:<p>
<blockquote>
...<br>
0110100001 (417)<br>
0110100000 (416)<br>
0110011111 (415)<br>
0110011110 (414)<br>
...<br>
</blockquote>
But suppose that the sensor (or the post) is slightly mis-aligned, so
that instead of properly reading the (416) row, it reads the first
half of the (416) row and last half of the (415) row. That makes
0110111111, which is 447 = 111.75 cm, an error of almost 7.5%.
(That's three inches, for my American and Burmese readers.) Or the
error could go the other way: if the sensor reads the first half of
the (415) and the second half of the (416) row, it will see 0110000000
= 384 = 96 cm.<p>
Gray code is a method for encoding numbers in binary so that each
numeral differs from the adjacent ones in only one position:<p>
<blockquote>
0000000000<br>
000000000<b>1</b><br>
00000000<b>1</b>1<br>
000000001<b>0</b><br>
0000000<b>1</b>10<br>
000000011<b>1</b><br>
00000001<b>0</b>1<br>
000000010<b>0</b><br>
000000<b>1</b>100<br>
...<br>
100001<b>1</b>100<br>
100001110<b>1</b><br>
...<br>
100000000<b>0</b><br>
</blockquote>
This is the pattern from the post, which you can also see at the right
of this article.<p>
Now suppose that the mis-aligned sensor reads part of the (416) line and
part of the (417) line. With ordinary binary coding, this could
result in an error of up to 7.75 cm. (And worse errors for children
of other heights.) But with Gray coding no error results from the
misreading: <p>
<blockquote>
...<br>
0101110000 (417)<br>
0101010000 (416)<br>
0101010001 (415)<br>
0101010011 (414)<br>
...<br>
</blockquote>
No matter what parts of 0101110000 and 0101110001 are stitched
together, the result is always either 416 or 417. <p>
Converting from Gray code to standard binary is easy: take the binary
expansion, and invert every bit that is immediately to the right of a
1 bit. For example, in 1<font color="red">1</font><font color="red">1</font><font color="red">1</font><font color="red">1</font><font color="red">0</font>1<font color="red">0</font>00, each red bit is to the right of a
1, and so is inverted to obtain the Gray code 1<font color="red">0</font><font color="red">0</font><font color="red">0</font><font color="red">0</font><font color="red">1</font>1<font color="red">1</font>00. <p>
Converting back is also easy:
of the Gray code. Replace every sequence of the form 1000...01
with 1111...10; also replace 1000... with 1111... if it appears at the
end of the code. For
example, Gray code <font color="red">100001</font><font
color="blue">11</font>00 contains two such sequences, <font
color="red">100001</font> and <font color="blue">11</font>, which are
replaced with <font color="red">111110</font> and <font
color="blue">10</font>, to give <font color="red">111110</font><font
color="blue">10</font>00. <p>
[ Addendum 20110525: Every so often someone asks why the stadiometer
is so sophisticated. <a href="http://blog.plover.com/tech/stadiometer.html">Here is
the answer</a>. ]<p>