[superprismatic]

Fred and Mike, two mathematicians, are in a bar.

Fred suddenly feels magnanimous and offers to buy Mike

a beer with probability 1/pi. As good mathematicians,

they would have no trouble calculating 1/pi to any

required accuracy. They agree to decide the matter

using only the results of flipping a fair coin some

number of times. How can they do this? And, on

average, how many coin flips would be required to

decide the matter? Of course, minimizing the number

of average coin flips would be important to them.

[Gmaster479]

Okay, if I'm understanding this correctly, there is a one in pi chance that Mike is getting a free beer.So if you simply divide 1 by pi, you get approx. 32%. So how do you get 32% from flipping coins? I'll get back to you

[superprismatic]

Okay, if I'm understanding this correctly, there is a one in pi chance that Mike is getting a free beer.So if you simply divide 1 by pi, you get approx. 32%. So how do you get 32% from flipping coins? I'll get back to you

No "approximately", we're talking "exactly" here!

[Guest]

Using the exponential equation:

(.5)^x = 1/pi

then translating it to logarithmic form:

log_.5(1/pi) = x

then solving for x:

x ~ 1.651496129

So the above value of x would be the number of coin tosses required to equal that probabilty. I suppose one would then round up, and get 2 coin tosses, and that would mean that the same outcome would have to occur on both tosses in order to achieve that probability.

[Guest]

I am attempting to work on this problem to achieve a more accurate answer, adn i would liek to know how many decimal places would amount to "any required accuracy"? And would it be possible to elaborate on "average"? I am not sure whether that is part of teh problem or just confusing me.

Thank you.

[plasmid]

Take a penny and a red marker, and mark a red spot on its edge. Then toss the penny onto a black ink pad, so the edge that hits the pad will be black. Take a second penny and place it on the table. Place the flipped penny on top of the second penny with the heads facing you and with the red mark pointing down (touching the second penny) on the far left edge of the second penny. Roll the flipped penny to the right, across the diameter of the face of the second penny. If the black mark touched the face of the second penny, Mike wins the beer. (Just taking advantage of the fact that pi = circle's circumference divided by diameter.)

Edit: Oh, wait, that won't work: I forgot that they're mathematicians and not engineers. In that case, they'll come up with some ridiculously complex approach that will require far more flips and might not be accomplishable before the sun burns out.

Edited July 9, 2009 by plasmid

[Guest]

After further deduction, and working with probability, I determined:

It is possible to achieve a probability of .3125 or 10/32 (reduced, 5/16), which is within 6/1000 (~581/100,000 or 1/pi - .3125) of 1/pi.

In this coin toss, exactly 2 of the five tosses would have to result in a single outcome (one of either heads or tails) both times. For example, heads would have to be flipped exactly 2 out of 5 times. This would also work for 3 out of 5 times (as getting heads exactly 3 times is the same as getting tails the other 2 times).

Therefore, I find the most correct answer (so far) to be 5 flips of the coin.

I will continue to work to find a more "exact" answer, but (as my previous post mentions) I am not quite sure precisely how exact the word "exactly" denotes.

[Guest]

nice answer plasmid I would never have worked that out. but you have it backwards the engineer would have organized a team, to designed a device, that would have told them that they needed a mathematicians help. Engineers are notorious for over complicating things, as much as mathematicians are notorious for having to be exactly right.

anyway I am kinda confused about your explanation so let me try. I am using your idea or relations but not your exact process

mark the penny on the edge with two black dots on completely opposite sides. then decide on a certain point on the edge of the table surface that you are spinning on. Spin the penny on the table. when it lands if one of the two dots on the penny is pointing towards the specified point its a win.

now this actually wouldn't work exactly because of human influence and the fact that the dots and spots can not be as small as needed. I also thought of

mark the penny the same way and then draw a line in wet red ink. roll the penny towards the line trying to be perpendicular and if the red ink covers one of the black dots its a win

but also the mathematician could have measured the distance with his head so you would have to do something like spin it first and the point pointing towards you is where the penny is started to roll from (the point touching the table). (or something like that). but since I really doubt there is a true exact answer as human error or these great mathematicians can use there minds to figure out how to spin or roll it, these are pretty good approximations.

anyway once again good idea

[Guest]

No "approximately", we're talking "exactly" here!

You just cant.

[Guest]

Does it have something to do with the Buffon's needle?

In that case, the mathematicians must draw a stripes on a paper with distance between lines = 2 x diameter of coin

Now draw a diameter on the coin as a reference.

Now when the coin is tossed, they would need to check whether the line drawn on the coin intersects a stripe on the paper. Count intersections each time.

They would need to toss the coin 355 times and if in these tosses the diameter line on the coin intersects the stripes on the paper more than or equal to 113 times, Mike would get a free beer.

(If they can settle with 22/7 as approximation for pi, they can toss 22 times (instead of 355) and the criteria of 113 crossings would get reduced to 7.)

Here's a link to find out more about buffon's needle http://en.wikipedia.org/wiki/Buffon%27s_needle

[superprismatic]

This is not a trick question. It is indeed possible to

use the results of ordinary coin flips to decide something

with probability exactly 1/pi. "any required accuracy"

means exactly what it says, so Fred and Mike could determine

any decimal place, no matter how far out it is, if they

required it.

[Guest]

Using Bernoulli Probability, I determined that in 15 flips of a fair coin, it is possible to obtain a probability which is within .0000183 of 1/pi (or (10/32 + 11/2048 + 15/32768) - 1/pi )

The coin flipping scenario is actually quite complicated when conceived, yet not so difficult to carry out.

The outcome must be as follows:

On flips 1-5, exactly 2 heads and 3 tails must be flipped (or 3 heads and 2 tails)

OR

On flips 1-11, exactly 1 head and 10 tails must be flipped (or 10 heads and 1 tail)

OR

On flips 1-15, exactly 1 head, and 14 tails must be flipped (ro 14 heads and 1 tail)

If any of these three outcomes occur, then the beer is bought.

The probability is 10/32 + 11/2048 + 15/32768, or ~.3183288574, as opposed to 1/pi, which is ~.3183098862.

[Guest]

Mark the whole edge of a penny between two points which are exactly one diameter of a penny in distance along the edge of the penny. Mark a single point on the bar. Flip once, if the marked edge is facing the point, then Mike gets a free beer.

[Guest]

to be fair though you have to acknowledge that plasmids response is valid and creative. oh and on my suggestions i forgot some stuff.

For the red line it would have to be the radius thick, but as it is easier to do diameter thick by just setting the penny down to draw. Do that and just use on dot. For the other process It is only an approximation of pi.

To make it better roll the coin across the diameter wide red line. Then spin it with the center of the red pointing at you to start. If you think about it there is a 1/2pr chance it will be pointing at you at any time in the spin but when it lies down there is a 1/p chance as it is similar to

If it was only a point you have 1/2pr chance of the pointing to you when it lies down. But then widen that point 2r distance and done.

If it makes anyone feel better you could flip the coin instead of spinning it.

[CaptainEd]

Check out Buffon's needle.

Draw parallel lines on the table, separated by exactly the diameter of the coin.

Draw a line across the diameter of the coin (one on each side, doesn't matter if they are parallel).

Flip the coin. The coin's line will touch or cross a table line with probability 2/pi.

To scale this down to 1/pi, flip twice. If it comes up heads both times or tails both times, buy the beer. If different, no beer.

[superprismatic]

Check out Buffon's needle.

Draw parallel lines on the table, separated by exactly the diameter of the coin.

Draw a line across the diameter of the coin (one on each side, doesn't matter if they are parallel).

Flip the coin. The coin's line will touch or cross a table line with probability 2/pi.

To scale this down to 1/pi, flip twice. If it comes up heads both times or tails both times, buy the beer. If different, no beer.

AH! But to be exact, the lines would have to have no thickness.

Ya can't do that!

[superprismatic]

I should have added that the method should work

for any probability -- not just 1/pi.

[bushindo]

This will guarantee any desired degree of accuracy

Let heads = 1, let tails = 0. Imagine that every time you flip a coin, you are adding binary digit to a fractional binary number.

So, suppose you flipped head, tail, head, head, that would correspond to the binary number .1011_b, which, in decimal notation is equal to 1/2 + 0/4 + 1/8 + 1/16 = 11/16 = .6725. Suppose we start over and flip tail,tail,head, head, that would correspond to .0011_b in binary, which is .1875 in decimal.

So, 1/pi is 0.3183099 in decimal. To satisfy the OP, let the two mathematicians flip the coins and construct the fractional binary number, call it X. Let the two agree on a predetermined number of flips n. After n flips, convert X to a decimal number. If it is less than 1/pi, then guy A buys guy B a beer. If it is greater than 1/pi, no free beer. You can improve the accuracy of this method by increasing the number of flips. This method is related to the bisection method. The maximum error, or the difference in the produced probability and the threshold, is 1/( 2ⁿ)

This method does not require the full n flips. At any flip, if the number X is greater than the threshold regardless of subsequent flips, then we might as well stop. For instance, for the threshold 1/pi = .31, if the first flip is head, then the number X is guaranteed to be greater than .5, so we might as well stop.

This also works for any arbitrary threshold besides 1/pi.

Edited July 9, 2009 by bushindo

[superprismatic]

This will guarantee any desired degree of accuracy

Let heads = 1, let tails = 0. Imagine that every time you flip a coin, you are adding binary digit to a fractional binary number.

So, suppose you flipped head, tail, head, head, that would correspond to the binary number .1011_b, which, in decimal notation is equal to 1/2 + 0/4 + 1/8 + 1/16 = 11/16 = .6725. Suppose we start over and flip tail,tail,head, head, that would correspond to .0011_b in binary, which is .1875 in decimal.

So, 1/pi is 0.3183099 in decimal. To satisfy the OP, let the two mathematicians flip the coins and construct the fractional binary number, call it X. Let the two agree on a predetermined number of flips n. After n flips, convert X to a decimal number. If it is less than 1/pi, then guy A buys guy B a beer. If it is greater than 1/pi, no free beer. You can improve the accuracy of this method by increasing the number of flips. This method is related to the bisection method. The maximum error, or the difference in the produced probability and the threshold, is 1/( 2ⁿ)

This method does not require the full n flips. At any flip, if the number X is greater than the threshold regardless of subsequent flips, then we might as well stop. For instance, for the threshold 1/pi = .31, if the first flip is head, then the number X is guaranteed to be greater than .5, so we might as well stop.

This also works for any arbitrary threshold besides 1/pi.

Yes! But, in practice you don't really have to agree on an n, after all the, likelihood that n gets big enough to be a pain if you let it grow is very very small. So, just keep flipping until you either get smaller or larger than 1/pi.

But, what about the second part of the question? If you keep flipping until the matter is decided, what is the expected number of flips?

[bushindo]

Yes! But, in practice you don't really have to agree on an n, after all the, likelihood that n gets big enough to be a pain if you let it grow is very very small. So, just keep flipping until you either get smaller or larger than 1/pi.

But, what about the second part of the question? If you keep flipping until the matter is decided, what is the expected number of flips?

Technically, at any flip, it is guaranteed that your number will either be greater than 1/pi or less than 1/pi. The proper early stopping conditions should be if your binary number X is greater than 1/pi, or if X is less than 1/pi regardless of subsequent flips. The second condition makes it messy to calculate the average required number of flips, so Im just going to go out on a limb and estimate the expected number of flips as 1 + 1/2 + 1/4 + 1/8 ... = 2 flips.

[superprismatic]

Technically, at any flip, it is guaranteed that your number will either be greater than 1/pi or less than 1/pi. The proper early stopping conditions should be if your binary number X is greater than 1/pi, or if X is less than 1/pi regardless of subsequent flips. The second condition makes it messy to calculate the average required number of flips, so Im just going to go out on a limb and estimate the expected number of flips as 1 + 1/2 + 1/4 + 1/8 ... = 2 flips.

Ok, I wasn't rigorous enough in my reply, Mea Culpa!