So what is the correct answer?

[ShiraiJunichi]

Today's hard problem: Come up with a method for coin flipping over the phone, that's better than:

Tom: Call it.
You: Heads!
Tom: Sorry, it was tails. Better luck next time!

You don't need cryptography for this. Just use the cell phone to take a time-stamped picture of the coin. Email the photo while I guess heads or tails.

[PyTom]

It strikes me as a time-stamped picture would be hard to make work. Either I send it early, which means that you might know what it is, or late, and I can just send the right picture. It's basically impossible to send them at the same time, without use of a trusted third party, which I'd like to avoid, since it's not necessary.

The crypto-solution is actually elegant.

[Akimaru]

I had a very tough math problem today...
let's see if any geniusses can figure this out
there are 3 unknown numbers
the sum of them equals 8
3 times number 1, plus, 2 times number 2, plus, number 3 equals 20.
And also number 1 minus number 2 equals 9.
What are the 3 numbers?

[PyTom]

7, -2, 3

You simply create a matrix of coefficents for each of the equations, and a vector with the equation values. Then you multiply the vector by the inverse of the matrix, and out comes the result. It's almost too simple.*

* Especially when you have scipy to do all the hard work for you.

BTW, I ask people not show more mundane ways of getting the solution. This isn't the homework help forum, after all, and if you show all work, it would be.

[Akimaru]

^what's scipi?
...and well it's not homework....it appeared on my test today and I figured out the answer later on.
My class doesn't work with 'matrixes' yet and I couldnt use a calc or whatever.

[PyTom]

SciPy ( http://www.scipy.org ) is a set of python packages that make doing mathematic and scientific computations with Python fairly easy. For example, to solve your problem, I simply typed:

Code: Select all

>>> from scipy import mat
>>> A = mat('[1 1 1 ; 3 2 1 ; 1 -1 0]')
>>> b = mat('[8;20;9]')
>>> A.I * b
Matrix([[ 7.],
       [-2.],
       [ 3.]])
>>> 

(With the lines beginning with >>> being what I typed, not including the >>>)

I actually think I remember how to do it without a calc, but it's enough work that I couldn't be bothered. (And it's been a decade or more since I've needed to... if you want to solve systems of equations, use a computer.)

[Beta]

While you're doing a case analysis, which is good, you're doing it wrong, which is bad. You're assuming that all of the six outcomes that you've listed have the same possibility, which isn't the case. Let's consider a sport which has a best-of-three championship series, but which, for whatever reason, demands that they play all three games, even if the outcome is preordained. We'd get the following possible outcomes:

HHH *
HHT *
HTH
HTT
THH
THT
TTH *
TTT *

The lines I've starred are the ones in which the games are won in two flips. All of the lines have the same probability, so the chance of someone winning in 2 games is 4/8 == 1/2.

however, the problem explicitly asks for the probability of it ending (not nessisarily being won) after two games. so, following your work, the probability is zero. also, if I recall correctly, the marlins play baseball (and the expos used to), and in a 2-out-of-3 match, if one team wins the first two games, the third isn't played.

Zeta, could you possibly get your math sensei over here to help out with trying to explain this one?

akimaru's problem>>as far as a simpler approach, try a system of equations.

A+B+C=8
3A+2B+C=20
A-B=9

[PyTom]

Yes, but our point is that the outcome of the third game does not affect if the series ends in 2 games or not. Your case analysis is therefore wrong, the probability of the series ending in two games is 1/2.

To drive the point home, I've written a simulator that plays 1000 rounds of this game each time you visit:

http://www.bishoujo.us/tmp/coinflip.cgi

[Quin]

It strikes me as a time-stamped picture would be hard to make work. Either I send it early, which means that you might know what it is, or late, and I can just send the right picture. It's basically impossible to send them at the same time, without use of a trusted third party, which I'd like to avoid, since it's not necessary.

The crypto-solution is actually elegant.

The first thing that occurred to me -- and I've heard reference to the problem years ago -- was for A to snap the photo, encrypt or password-protect the image (at a complexity level high enough to ensure that it can't be brute-force cracked in a few minutes) and send it to B. B, upon receipt of the encrypted image, sends A his call of heads or tails within a predetermined time frame (say, 60 seconds). A then provides the decryption key, and the outcome is determined.

To avoid cheating, if B fails to send A his call within the time frame, the process is restarted with a new image and new encryption key. If A fails to provide the decryption key, B wins by default.

Is the crypto-solution you have in mind more elegant than this, PyTom?

Another variant that just occurred to me... A and B decide between themselves who gets "even" and who gets "odd". Both sides send an encrypted file containing an integer of their choice, within a fixed period of time (again, with enough complexity and a short amount of time, to avoid brute-force cheating). Once the files have been exchanged, both parties provide the keys to decrypt the files. The numbers are added together, and the parity of the sum determines the winner.

[PyTom]

Quin is actually pretty close with the second solution. The canonical solution to this problem, if I remember it correctly, is:

Alice generates a key, and uses that key to encrypt two messages. The first says heads, and the second says tails. Alice sends those two messages over to Bob, who can't read them, since he doesn't have the key yet. Bob picks one at random, and tells Alice that's the one he has chosen. Alice then sends the key over to Bob, and they both decrypt the message, allowing them to both know what the coin-flip read.

(In practice, we can combine the calling with the coin-flip and just encrypt "Alice wins" and "Bob wins". Not like there's really much call for this in practice.)

IIRC, I got this from Bruce Schneider's "Applied Cryptography".

[Counter Arts]

ooo... mathie/CS type stuff!

Makes me want to prove and disprove stuff!

Okay... I'll disprove Beta's theory by contradiction.

Assume Beta's theory is true. Then the possiblity for the outcomes are...

( 1 )

HHX = 1/6
HTH = 1/6
HTT = 1/6
THT = 1/6
THH = 1/6
TTX = 1/6

I'm sure we all can agree that...

( 2 )

HH = 1/4
TH = 1/4
HT = 1/4
TT = 1/4

We can derive from ( 1 ) the following

HHX = 1/6 = HH
HTX = 2/6 = HT
THX = 2/6 = TH
TTX = 1/6 = TT

This contradicts ( 2 ) therefore Beta's theory is inconsistent.

Not quite a formal arguement but good enough.

[Beta]

Assume Beta's theory is true. Then the possiblity for the outcomes are...

( 1 )

HHX = 1/6
HTH = 1/6
HTT = 1/6
THT = 1/6
THH = 1/6
TTX = 1/6

I'm sure we all can agree that...

( 2 )

HH = 1/4
TH = 1/4
HT = 1/4
TT = 1/4

We can derive from ( 1 ) the following

HHX = 1/6 = HH
HTX = 2/6 = HT
THX = 2/6 = TH
TTX = 1/6 = TT

This contradicts ( 2 ) therefore Beta's theory is inconsistent.

and your proof conflicts with the original problem. HTX and THX cannot occur because no team had won two games at that point, and the series only ends AFTER one team accumulates two victories. no sooner, no later. my solution is still valid at this point unless someone can point out the explicit wording in the original problem that contradicts this.

while you're at it, map out all the possible "routes" that a best two-out-of-three match can go when it ends immediately after one side wins two games.

[Megaman Z]

*reads everything he hasn't read yet*

well, as an originally unintended side result, we've got some insight on how some people around here think. this could very well influence some of the NaNoRenO projects when March rolls around.

...and in case it's needed around here...

*sets fire extinguisher in middle of room*

[PyTom]

while you're at it, map out all the possible "routes" that a best two-out-of-three match can go when it ends immediately after one side wins two games.

One match:

H = 1/2
T = 1/2

Two matches:

HH = 1/4
HT = 1/4

TH = 1/4
TT = 1/4

Third match, if necessary.

HH = 1/4

HTH = 1/8
HTT = 1/8

THH = 1/8
THT = 1/8

TT = 1/4

P(TT) + P(HH) = 2/4 = 1/2

Remember that the probabilty of two independent events A and B occuring is P(A) * P(B), when figuring out how I got those numbers. Specifically, P(HTH) = P(HT) * P(H) = 1/4 * 1/2 = 1/8.

I should point out to Beta that I think we've shown our analysis to be correct, through multiple means. We've given a number of case analyses, all of which come to the same result. I've even written a program that simulates the game. A number of us have advanced degrees, and we've all come to the same conculsion.

Your focus should be less on defending your (incorrect) result, and more on understanding why you were wrong. That way lies understanding.

[ShiraiJunichi]

Here's another way to think about it. Someone HAS to win the first game (assuming no ties). For the next round, there is a 50% chance a given team will win. If you choose that "given team" to be the team that won the first round, then that means that there is a 50% chance that one team will win the first two games.