wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Transcendental binary game
        
(Message started by: Aryabhatta on Jul 26^th, 2004, 12:49am)

Title: Transcendental binary game
Post by Aryabhatta on Jul 26^th, 2004, 12:49am

This problem if from the book: "A problem Seminar", by Donald J Newman.

We alternate writing down binary digits after a decimal point therby producing a real number in the interval [0,1]. You win if this number is transcendental. Can you force a win?

I don't think this appeared before in this forum. If it has, my apologies.

Title: Re: Transcendental binary game
Post by towr on Jul 26^th, 2004, 2:13am

::[hide]No you can't win, a transcendental number has an infinite number of digits. So it would take an infinite amount of time to write down the number, and thus an infinite amount of time before you could win. The universe will come to an end before you can win and will take you (being a part of said universe) with it..[/hide]::
But I'm sure that's not the answer you were looking for :P

Title: Re: Transcendental binary game
Post by Grimbal on Jul 26^th, 2004, 7:01am

I think if you just write down the binary digits of pi, whatever the other person writes, you end up with a transcendental number. No proof, though.
Only that non-transcendental number are countable. So, the set of odd digits belonging to a transcendental number is countable, while the set of odd digits you could write is not countable. So, by just writing random digits, you have 100% chance to end up with a transcendental digit. And pi digits are kind of random, aren't they?

Title: Re: Transcendental binary game
Post by towr on Jul 26^th, 2004, 7:13am

Depends on what you call random, there is a formula to determine the nth digit (in hexadecimal) of pi without first calculating the first n-1 digits..

Title: Re: Transcendental binary game
Post by Eigenray on Jul 26^th, 2004, 8:48am

on 07/26/04 at 07:01:57, Grimbal wrote:

So, by just writing random digits, you have 100% chance to end up with a transcendental digit. And pi digits are kind of random, aren't they?

Just because the probability of something happening is 0, it doesn't mean that it can't happen, just that it won't.
And the digits of pi are certainly not random. Calculate the 17th digit of [pi] as many times as you want, you (should) get 3 every time.

But the idea is correct. To make it a bit more rigorous:

Define an independent strategy to be a map t:[bbn][to]{0,1,...,9}. Let IS be the set of all independent strategies, except the one that sends everything to 9, for convenience. Note IS is uncountable.
For t [in] IS, define
S_t = { x [in] [0,1) | [forall]k[in][bbn] d_2k(x) = t(k) },
where d_n(x) = floor(10ⁿ*x) mod 10 is the n-th decimal digit of x. That is, S_t is the set of all the possible outcomes when I play strategy t, picking the decimal digits for the even places.
Let A be the set of algebraic numbers in [0,1) (if I play a strategy in IS, the outcome can't be exactly 1).
Now, [cup]_t S_t = [0,1), so [cup]_t (S_t[cap]A) = A.
Since the RHS is countable, and the union is of uncountably many disjoint sets, there must exist t' [in] IS such that S_t' [cap] A = [emptyset]. Thus, if I play strategy t', the number formed when we play will be transcendental, no matter what your strategy is.

Title: Re: Transcendental binary game
Post by Aryabhatta on Jul 26^th, 2004, 11:46pm

on 07/26/04 at 02:13:24, towr wrote:

::No you can't win, a transcendental number has an infinite number of digits. So it would take an infinite amount of time to write down the number, and thus an infinite amount of time before you could win. The universe will come to an end before you can win and will take you (being a part of said universe) with it..::
But I'm sure that's not the answer you were looking for :P

Not if you play this game with Zeno. ;D

Title: Re: Transcendental binary game
Post by Aryabhatta on Jul 26^th, 2004, 11:51pm

Doesn't it remind you of the Sink the Sub puzzle? (Found in the hard riddles)

bw, Eigenray, the problem talked about binary representation, so your solution makes no sense ;D

Title: Re: Transcendental binary game
Post by Eigenray on Jul 27^th, 2004, 5:11am

Whoops. I guess I was thrown off by seeing the word 'decimal' in the problem statement. Oh well, back to the drawing board...