another very long task

[phil1882]

let heads be 1 and tails be 0. can you flip a coin enough times to form an irrational number?

[bushindo]

let heads be 1 and tails be 0. can you flip a coin enough times to form an irrational number?

This puzzle statement may be undercontrained,

Let f_i be a binary variable representing the i-th coin flip. There is an extra parameter that is required to form a number from the sequence of f_i. Consider the following equation for using f_i to generate the natural numbers, A^_N, from N coin flips

or this equation to use f_i to generate a random number between 0 and 1

Both of these methods return rational numbers for all N, but both of the above implicitly uses a factor of 2 in constructing the number A_N. There is nothing that really requires us to use 2, though. We can easily define a number generating scheme that returns an irrational number as follows

Under the scheme above, we are guaranteed to get an irrational number with any finite number of coin flips.

[superprismatic]

Just put your generated sequence inside the square root function. You'll get an irrational number soon enough!

[phil1882]

okay maybe some clarification is in order.

clearly no finite number of flips will be enough, assuming you're not allowed to apply a function to it.

but can you mathematically flip an infinite number of coins to represent an irrational number?

i guess what I'm asking is, is the digits of a single irrational number countably infinite?

[jim]

Any real number can be expressed by a sign, a finite number of binary digits before a binary point, and then a possibly iinfinite and definitely countable number of binary digits after the binary point. 0.1010010001... would be an example of an irrational number in binary where every run of 0"s countains one more 0 than the previous run and is followed by a single 1.

[TheChad08]

I suspect the answer is in binary.

I'd say 16 flips total to get "Pi"

[phil1882]

I'm very interested in knowing how you get 16 flips for the value pi, since pi is transcendental.

[superprismatic]

I'm very interested in knowing how you get 16 flips for the value pi, since pi is transcendental.

You can make the two ASCII characters "Pi" with 16 bits.

[bonanova]

TheChad:

[EventHorizon]

okay maybe some clarification is in order.

clearly no finite number of flips will be enough, assuming you're not allowed to apply a function to it.

but can you mathematically flip an infinite number of coins to represent an irrational number?

i guess what I'm asking is, is the digits of a single irrational number countably infinite?

As you know, the integers are countably infinite. You can simply map each nth integer to the nth digit after the decimal place to see that the digits of an irrational number are countably infinite.

You ask if you can flip an infinite number of coins to represent an irrational number, and the answer is yes.

If you represent the number in binary and have a coin per decimal place, you'll **always** end up with an irrational number. To be rational, the digits would eventually need to continue to repeat through infinity. By this construction, each digit is random and therefore no repetition can be continued through infinity. In other words, the probability you end up with a rational number is 0%, and the probability you end up with an irrational number after flipping an infinite number of coins representing its digits is 100%.

Can you end up with a rational number using a fair coin and an infinite number of flips? In theory, yes (it could, for example, come up heads every time). In practice, no... it is impossible.

Can you end up with a rational number using a fair coin and an infinite number of flips if you allow reordering of digits/coins? Yes. In fact, you can end up with **any** rational number whose repeated pattern contains at least one one and at least one zero... and you'll still use every coin... eventually... if you want to.

[phil1882]

so i guess the next logical question is this, if every irrational number is countably infinite in it representation, can you represent all irrational numbers in a countably infinite way? that is, we know we can form any individual irrational number with a series of 1's and 0's. there is no individual irrational number we can't form this way. now imagine we have a countably infinite number of people flipping coins. which irrational number won't be hit?

[EventHorizon]

so i guess the next logical question is this, if every irrational number is countably infinite in it representation, can you represent all irrational numbers in a countably infinite way? that is, we know we can form any individual irrational number with a series of 1's and 0's. there is no individual irrational number we can't form this way. now imagine we have a countably infinite number of people flipping coins. which irrational number won't be hit?

This leads exactly to Cantor's diagonalization argument, which can show that between any two distinct numbers are an uncountably infinite number of irrational numbers.

Here it is (for between 0 and 1 at least... though it is trivial from here to any two distinct numbers):

Assume there is a way to list them all in a countably infinite way. Let the list be numbered so Ir1 is the first irrational number listed, Ir2 is the second, etc. Let IrN(M) be the value of the Mth decimal place of the Nth irrational number listed. You can create a missed irrational number whose Nth decimal place's value is different than IrN(N) for all N. Therefore it cannot be listed because if it was, and assuming it is the Kth number, then it would need to differ from itself in the Kth decimal place's value.

So a given irrational number has a countably infinite number of decimal places, but there are 2^aleph₀ number of irrational numbers (and consequently, real numbers) as we have just shown by the coin flip representation, where aleph₀ represents a countably infinite quantity. So we've shown that 2^aleph₀ is greater than aleph₀. And, as speculated by the continuum hypothesis, 2^aleph₀ = aleph₁, which is the next in the hierarchy of infinite sets. This, however, has not been proven, so there may be provably smaller uncountably infinite sets.

Edit: According to wikipedia, it has been shown to be unprovable given the common set axioms. Also, as bonanova points out in the next post, the simple answer to "which irrational number will be missed" is you'll miss 100% of them. Yeah, I overlooked actually answering that question as stated.

Edited August 16, 2012 by EventHorizon

[bonanova]

That was a reply to your question. Is the answer the obvious "almost all" of them?