Flipping coins

Alright, as my first ´real´ post, I want to talk about a problem I solved yesterday. I read it on a blog this week, and since I´m not able to track down the site on which I found it, read the comments of other people to see how they solved it and compare their solutions to mine, I am just going to talk about my own thought process, my solution and 2 generalizations of it. The initial problem was:

Problem 1). Make up a game that you can play with just a (fair) coin, such that you have \displaystyle \frac{1}{3} chance of actually winning.

Before you read any further, I would propose that you think about the problem yourself for a time. First of all, because it’s a fun problem. Second of all, and I’m not saying this to mathematicians only (!), it’s not that hard to start; there should at least be 1 or 2 ways of tackling this problem that come natural to you. So, stop reading. Start thinking.

Aight, now that you found a solution on your own (congrats!), I can talk about my own thought process and solution.

The first thing I did, that I think a lot of people would do, was to underestimate this question. And even if you didn’t, admit it, it sounds like an awfully simple problem. So I was like, let’s use the probability mass function of the binomial distribution, add some suitably chosen k’s together and we have our solution. More specific; I thought that the chance of, say, throwing less than 5 times heads out of a total of 11 flips, should be reasonably close to \displaystyle \frac{1}{3}. And if I’m wrong, than use some other parameters. At first sight it seems reasonable that there should be at least some parameters that will yield a total chance of \displaystyle \frac{1}{3}. But, quickly you’ll notice that this is, in fact, not the case. Why not? Because the possibility of some event or condition, say A, when you flip n times, is equal to the number of outcomes that satisfy A, let’s call that a, divided by the total number of outcomes. Clearly a is positive and integral. And the total number of outcomes is just 2^n. So P(A) = \displaystyle \frac{a}{2^n}. And this equals \displaystyle \frac{1}{3} iff a = \displaystyle \frac{2^n}{3}, which is not integral; contradiction. And notice that my constraints on A where not restrictive at all; A is just some condition, whatever it is. So that idea is out of the window and we’re back at square one? No! When you know that an idea, or  way of thinking about a problem, isn’t going to work, it’s usually very helpful to not throw it out of the window, but to examine your idea very carefully to see where it hits a wall. So, let’s climb out of the window, and get our initial idea back. Where did we, or let’s not blame ourselves, where did our idea go wrong? Our idea went horribly wrong, because we always had a sample space that is a power of 2. And a fraction whose denominator is a power of 2, is never equal to \displaystyle \frac{1}{3}. So basically, what we need to do is change our sample space; we have to ‘eliminate’ some possibilities. And once you realise this, it hopefully is straightforward to grasp the following; if you want to eliminate a possibility, all you have to do is just flip the coin again, when that possibility ‘happens’. So after some thinking, you could come up with the following: If we flip the coin 2 times, there are 4 possibilities {HH, HT, TH, TT}. If we eliminate, let’s say, TT, there are 3 possibilities left. So if you win once, and lose the other 2 times, the probability that you win is \displaystyle \frac{1}{3}, which solves our problem. So the following will do the job:

Flip the coin 2 times. If you get both heads, you win. If you get a head and a tail, you lose. If you get two tails, flip again, with the same results. So if you get two tails, you flip the coin again 2 times.

And because we can be ‘quite’ sure that we will flip heads sometimes, this game ends with probability 1. Now, most people are satisfied with this; we saw a problem, we solved it, easy game, let’s do something else. But: I would strongly recommend you to not have this attitude. Because it’s usually a good idea to keep thinking about a problem, even after you solved it! Try to find another way to solve your problem. Find another proof of your theorem. Change some conditions. Try to find and solve a related problem. Try to generalise your result. Etc. Etc. This is a really good mental excercise, which only strengthens your problem-solving ability. So that’s also what I wanted to do with this problem. However, it’s getting kinda late, so I will update this blog later this week, about the following two generalizations of our problem;

Problem 2) Make up a game that you can play with just a (fair) coin, such that you have \displaystyle \frac{p}{q} chance of winning, for given positive integers p, q, with q > p.

Problem 3) Make up a game that you can play with just a (fair) coin, such that you have x chance of winning, for a given real number x, with 0 < x < 1.

Solving problem 2 should be quite straightforward, using the knowledge we already have. Problem 3 is strictly harder. Good luck!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: