Tuesday, December 8, 2009

Two math problems

Last weekend, I took the William Lowell Putnam Competition, a national math competition for college students. It consists of twelve problems to prove in six hours. The median score is about zero. Sounds intimidating, huh?

Most of these are a bit more difficult than the kind of puzzles I intend to put on my blog, but here's an easier one which I feel is appropriate.
Problem A1: Let f be a real-valued function on the plane such that for every square ABCD in the plane, f(A) + f(B) + f(C) + f(D) = 0. Does it follow that f(P) = 0 for all points P in the plane?
If you are interested in seeing other Putnam problems, I refer you to the Art of Problem Solving Forum.

And here's another math puzzle, which is completely unrelated.
You play a game with me which involves flipping a coin. I flip the coin repeatedly until I get a heads. Let N be the number of times I flipped the coin. If N is even, we start the game over from the beginning. If N is odd, then you win N dollars. What is a fair price to play this game? (Hint: it's not $3)
If you're wondering how I did on the Putnam, I expect to get four correct, just like last year.

See the solutions


Hemant said...

I once scored a 1 on that test. I bragged the hell out of that one on all future resumes... :)

miller said...

Ahahaha! Scoring a 1 will place you about about 50% of the test takers, and the people who take the test are usually an intelligent group. So it's actually not too bad!

miller said...

Correction: Scoring a 1 places you *above* about 50% of the test takers.

Secret Squïrrel said...

With regard to your coin toss game, if you mean that I lose if you toss a head on an even throw (and I must pay again to start the game over) then I would be happy to pay you any amount up to $1.11 for the privilege of playing.

miller said...

If I toss a head on an even throw, the game starts over at no charge.

Secret Squïrrel said...

In that case I'd pay up to $1.60.

miller said...

That's fair (within 10 cents). Do you have justification?

Secret Squïrrel said...

Yes. I had already summed the infinite series for a single run-thru of the game for my first answer. I ignored even tosses since they (with my original understanding of the game) resulted in a loss for me; ie a return of $0.

My chance of winning on the first toss was obviously 1/2, on the third - 1/8, fifth 1/32, etc. However, less likely outcomes were worth more so the sum total return I could expect over many games is ($1 x 1/2) + ($3 x 1/8) + ($5 x 1/32) + ... which came to $1.11+1/9c.

However, once you clarified the rules for me, I realised that you would also pay me $1 if the coin came up heads after a restart (ie any time you threw a head on an even toss).

This could happen after THH (1/8 chance); TTTHH or THTHH (both 1/32); TTTTTHH or TTTHTHH or THTHTHH (all 1/128) and so on.

Each of these new series of expected returns summed to 1/4 of the preceding series; ie the series beginning with a 1/8 chance of me winning $1 ($3 - 1/32, $5 - 1/128, etc) gives me an expected return of 1.11/4 or about 27.78c, and the series beginning with a 1/32 chance of me winning $1 sums to about 6.94c.

There is only one sequence of coin tosses that can lead to me having a 1/2 chance of winning $1 and the same goes for a 1/8 chance of winning $1. However, there are 2 sequences that give me a 1/32 chance of winning $1 (TTTHH and THTHH), 3 sequences for a 1/128 chance (TTTTTHH or TTTHTHH or THTHTHH), 4 for 1/512 and so on.

So I summed all of those 10/9 + 10/36 + 2x10/144 + 3x10/576 + 4x10/2304 + ...
and got near enough to $1.60.

There's prob a more elegant way of solving it but I didn't look for it once I thought this would work.

Scott said...

I'm not certain this is correct, but my result (1.66) agrees with SS's. Here's what I did:


import math

max = 1000

sum = 0
for n in range(1, max):
sum += (2 * n - 1) * 2 ** (-(2 * n - 1))
print sum
gamereturn = sum

sum = 0
for n in range(1, max):
sum += 2 ** (-(n * 2))
print sum
repeatodds = sum

mult = sum
sum = gamereturn # because the first round happens automatically
for n in range(1, max):
sum += gamereturn * repeatodds ** n
print sum

Scott said...

Also: I have a conviction that the answer to the first problem is "yes" but I don't have a good line of reasoning, other than a vague intuition about performing integrals of coinciding squares across the plane... I would be pleased to be proven wrong.