You're absolutely right! I didn't express myself very well. The "standard" solutions to this puzzle will seem mysterious when seen as just sequences of integers 0,1,4,5, ... 0,2,8,10, ... Only when rendered in some representation, in this case base-2, does the scheme emerge. By the way, a solution to this puzzle gives a bijection between rationals and integers and would have fit nicely in the set theory chapter of my new math book. On Sep 29, 2010, at 1:23 PM, Andy Latto wrote:
On Wed, Sep 29, 2010 at 12:11 PM, Veit Elser <ve10@cornell.edu> wrote:
Your solution was exactly what I was looking for.
As a participant in the new math experiment in California schools in the 1960s my reaction to doing arithmetic in base-5 was similar to Tom Lehrer's. A problem such as this one, I imagine, would have stimulated my interest because the binary representation enables you to do something you wouldn't have been able to do otherwise (unlike computing sums).
How so? Can't you do the same thing with decimal representations?
a_n are the numbers with 0 in every even place in their decimal representation. b_n are the numbers with 0 in every odd place in their decimal representation.
Doesn't that work just as well, with no need for binary?
Andy
Here's a slightly more general solution.
We are interested in factoring 1/(1 - x) into two infinite Taylor series that have only 0/1 coefficients. We generate such a factorization given an arbitrary sequence of primes,
p_0, p_1, p_2, ... .
Start by defining
f_0(x) = 1 s_0 = 1,
and then evaluate the recursion
f_(n+1)(x) = f_n(x) c_(p_n)(x^s_n) s_(n+1) = s_n p_n,
where
c_p(x) = 1+x+ ... x^(p-1)
is the p-th cyclotomic polynomial.
Your example was derived from the prime sequence
2,2,2, ... .
Here's what you get for the sequence
2,3,2,3,2,3, ...
f_1 = (1+x) f_2 = (1+x)(1+x^2+x^4) f_3 = (1+x)(1+x^2+x^4)(1+x^6) f_4 = (1+x)(1+x^2+x^4)(1+x^6)(1+x^12+x^24) etc.
You can now form factorizations 1/(1-x) = g(x)h(x) as before, by assigning an infinite subset of the factors of f to g and the complement to h.
Veit
On Sep 28, 2010, at 11:36 PM, Tom Karzes wrote:
Cute problem. Here's the most obvious solution: Have one sequence contain all integers whose binary representation contains zero in all odd bit positions, and the other sequence contain all integers whose binary representation contains zero in all even bit positions:
a: 000000 000001 000100 000101 010000 010001 010100 010101 ... b: 000000 000010 001000 001010 100000 100010 101000 101010 ...
In decimal:
a: 0 1 4 5 16 17 20 21 ... b: 0 2 8 10 32 34 40 42 ...
For this solution, the values in one sequence are double the values in the other.
For any integer, there will clearly be a unique choice from sequence "a" and a unique choice from sequence "b".
I believe any partitioning of the bits will work, as long as each bit is allowed to be non-zero in one and only one sequence.
This easily generalizes to as many sequences as you want. For example, for three, you would simply partition the bits into three sequences.
Tom
Here's a puzzle I made up. In the 1960's it might have been used to get kids interested in "new math".
Find two infinite sequences of non-negative integers
a0, a1, a2, ... b0, b1, b2, ...
such that a0 = b0 = 0, and every non-negative integer can be uniquely expressed as the sum of two integers, one from each sequence.
Veit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun