Re: [math-fun] Tiling puzzle
while impressed by Salamin's solutions for some abstract notion of "impressed"... (I.e. how much it boggles my mind) they seem to me to be too "nonconstructive." I tried to read http://en.wikipedia.org/wiki/Transfinite_induction but my mind remained boggled. Can we find a "constructive" way to partition the reals into two congruent dense subsets -- i.e. so it is somehow "algorithmic" to tell which set a given real is in? Well, ok, maybe that seems hopeless, but somehow Salamin's solution seems really really nonconstructive to me. Would a Brouwerian "intuitionist" accept it? I think not. (Agree?) Can we reduce the number of "really"s? (I have a lot of sympathy with the Brouwerian point of view at times. Such as now.) So: can we find a solution which happens also to partition the rationals, or quadratic algebraics, or algebraics... into two congruent dense subsets... and then asking for an algorithm is a perfectly sensible thing to do. I guess the biggest subfield of the reals for which we could have this hope, would be the "computable reals." All these subfields are countable. OK, so Salamin's solution can be rewritten to pertain to these countable subfields in a way that I think would not make Brouwer turn over in his grave: H = {0} H' = emptyset for all rational (algebraic, whatever) numbers X in order do if(X is not in H and X is not in H') H = {y + n X where y in old H and n integer} H' = {y + (n+1/2) X where y in old H and n integer} fi od After running that "algorithm" we get that S = H U H' is the full set of rational (algebraic, whatever) numbers, and H is a subgroup of index 2 inside it (additive groups) and H and H+1/2 form the desired partition. Now note that for any particular rational (algebraic, whatever) R this "algorithm" will find out which set R is in (red or blue?), in finite time. However... this won't work for the computable reals since it is uncomputable whether two are equal (right?). I can't help suspecting there is something a lot cleaner waiting to be found. We've just been discussing a super-nice way to order the rationals with Calkin-Wilf tree. Well, maybe there is a comparable super-nice thing just for the red rationals. You need to find it, or Brouwer's going to kick your ass.
Actually, here's another attempted solution way simpler/nicer than yours... but there is a tiny gotcha, some sleaziness, and some appeal to god... Order the positive rational numbers R1, R2, R3, ... (e.g. like we've been discussing on another thread) Now scan thru this order using your random bit generator to color each one red or blue. If R is blue, then -R is red. Voila: we have a 2-coloring of the rationals, and it is dense with probability=1, and the two color sets are congruent (in fact negations). The "tiny gotcha" is: 0 (zero) is not colored. That can be got around via the following sleazy trick. Agree to color X and -1/X opposite always. Stereographically project the real line onto a circle and then 0 is the South and infinity the North pole, and then the red and blue sets are also congruent [mirrored] on that circle, including if we now color 0 and infinity red and blue (or the reverse). And oh yeah, "infinity=-1/0" is now an honorary rational number. This all works for the usual countable sets instead of rationals (algebraics...). Also it should work with appropriate PSEUDOrandom functions of the number, albeit it might be a little tricky to tell whether your function is "random enough." I might suggest the Liouville lambda function... or some suitable function based on hashing the digits... or maybe just (-1)^N... This also works for the full set of real numbers -- that's nonconstructive but still blindingly obvious.
On 11/12/2011 10:12 PM, Warren Smith wrote:
Can we find a "constructive" way to partition the reals into two congruent dense subsets -- i.e. so it is somehow "algorithmic" to tell which set a given real is in?
For each integer n, color the rationals in the interval [2n, 2n + 1) red and color the irrationals blue, then use the reverse coloring in the interval [2n + 1, 2n + 2). -- Fred W. Helenius fredh@ix.netcom.com
participants (2)
-
Fred W. Helenius -
Warren Smith