Flip-8

Here's a game, which I'll call Flip-8. We'll flip a coin 8 times, and we'll count the number of heads. The number of heads could be 0, 1, 2, through 8. That is, there are 9 possible outcomes.

I'll give you a dollar if it comes up 0,1,2,6,7, or 8. You give me a dollar if it comes up 3,4, or 5. You have twice as many outcomes as me, so you should make out like a bandit!

Q: Why would I play flip-8?

What are the odds of heads coming up 0 times. This is n-choose-m again. 8 choose 0 is 1. There are 256 ways to flip 8 coins, and 1 way to get a zero.

To get 1, it's 8 choose 1 = 8.

To get 2, it's 8 choose 2 = 28.

To get 6 it's 28. To get 7 it's 8. To get 8 it's 1.

It all adds up to 1+8+28+28+8+1 = 74. So the expected payoff for you is 74/256, or 0.2890625.

Since 8 choose 3 is 56, and 8 choose 4 is 70, my chances of winning are (56+70+56)/256 = 182/256 = 0.7109375.

Seems like I could make a lot of money of this game if I could convince someone to play...

n choose m

If I have 3 kids and I want to form a team of 2 kids, how many different teams could I create? [3]

If I have 4 kids, how many different teams of 2 kids? [6]

If I have 5 kids, how many different 2-kid teams? [10]

If I have 6 kids, how many different 2-kid teams? [15]

[At this point they recognized the sum of the numbers from 1 to n-1, which they know the formula for: n kids can form n(n-1)/2 teams of 2.

What about 2 kids? [1]

What about 6 kids forming teams of 3?

[The kids weren't sure how to enumerate the teams of 3.] What about 3 kids forming a team of 1? [3]

What about 3 kids forming a team of 3? [1]

What about 3 kids forming a team of 2? [3. It's like forming a team of 1 kid who is not on the team.]

What about 3 kids forming a team of 0? [1. The immediate response is 0, but the right answer is 1. There is one team with no one on it.]

If you have n kids forming teams of size m then

• the first kid could be any of n,
• the second kid could be any of (n-1),
• the third kid could be any of (n-2),
• ...
• the mth kid could be any of (n-m+1).

This is n!/(n-m)!.

Those all get multiplied together. Now the problem is that the same combination of kids gets counted more than once. How many times does a team of m kids get counted?

• the first kid could have ended up in any of m positions (being chose first, second, third, etc.),
• the second kid could have ended up in any of m-1 positions,
• ...
• the mth kid can only end up in one position.

So the formula is n!/((n-m)! m!).

Cardinality

The size of a set is called its cardinality. It's clear when two finite sets have the same cardinality, they have the same number of elements. What do we mean when we say to infinite sets have the same cardinality?

For example, is the set of even integers {..., -4, -2, 0, 2, 4, ...} smaller than the set of all integers {...,-4,-3,-2,-1,0,1,2,3,4,....} ?

Our intuition says that removing an element from a set makes the set smaller, so removing an infinite number of elements should make it a lot smaller. That intuition is wrong though.

We say that two sets have the same cardinality if we can make a 1-to-1 correspondence between them. A 1-to-1 correspondance between A and B is a pairing of elements of A and B where every element of A is in exactly one pair, and every element B is in exactly one pair.

Here's a 1-to-1 correspondence between the integers and the even integers: k pairs with 2k. Every integer is on the left side (the k's) and every even integer is on the right side (the 2k's).

The 1-to-100 Game

Let's analyze a two-person game. Fred picks two distinct integers between 1 and 100 inclusive. Fred writes the numbers down on two cards (one red card and one blue card), and places them face down on the table. Ginger picks a card, and looks at the number. Now she must decide whether to keep her card ("stand"), or swap with the other card (which is still face down). She wins $1 if she picks the greater number, and wins $0 otherwise.

Can she do better than an expected value of $0.50? What is Fred's best strategy? What is Ginger's?

[It turns out that the kids have actually been playing this game in math class at school, but apparently haven't analyzed it.]

They said, Ginger should look (at which card? not specified) and if the card is less than 50 then swap, otherwise stand. I said, what if Fred always writes down 2 on the red card, and 1 on the blue card. If Ginger always looks at the red card she will be fooled.

[There's another variant of the game, where Fred gets to choose which number Ginger gets to look at, which is even worse for Ginger.]

But then Ginger, if she knows Fred will do that, will always swap if she sees a two.

But then Fred will sometimes feed Ginger a 2 and a 3.

So how to fix this? We made a rule that Ginger must write down her algorithm, and then Fred can exploit any loopholes in her algorithm.

I gave them a hint. Ginger should flip a coin to determine which card to look at. (The kids said "no fair, you didn't say we could flip a coin!". I said "I'm telling you now. Coin flipping is sometimes the best way to make decisions that can handle certain adversaries.")

How to get started on analyzing the game? What if we play the 1-2 game. Fred picks two distinct numbers in the range 1 to 2. Ginger picks one number. The kids immediately saw that if Ginger sees 1 then swap, otherwise she stands, and she always wins. Fred's has no choice.

What if we play the 1-2-3 game. Fred picks two distinct numbers in the range 1 to 3. The kids argued that Fred should never pick the pair 1 and 3, because if Ginger ever sees a 1 she swaps, and if she ever sees a 3 she stands, so 1 and 3 is a loser for Fred. So Fred should always pick a 2. It took a little bit of thinking for the kids to convince themselves that Fred should sometimes pick 1 and sometimes 3 for the other number. They concluded that a coin flip is good, and that Ginger can get $0.75 expected value.

At this point the 5-minutes ran out, and one kid wanted to proceed to analyze the 1-2-3-4 game, so the other went to read about vampires or something.... The 1-2-3-4 game was a tough nut to crack for a 12-year old. The only reasonable choices for Fred are 1-2, 2-3, or 3-4. But what odds should Fred use to choose? We guessed that 2-3 should be chosen 1/2 the time, and the others 1/4 of the time each. That gave Ginger a $0.75 expected value. Then we tried choosing each pair 1/3 of the time, and that gave Ginger a $2/3 expected value. We argued that any deviation from equal odds gave Ginger more money.

√(2 + √(2 + √(2 + ... )))

What is the value of this infinitely recursive expression?

The kids all guessed it is two by successive approxmation:

√2 = 1.414
√(2 + √2) = √ 3.414 = 1.874
√(2 + √(2 + √2)) = √3.874 = 1.9615

Algebraically we can write set x= √(2 + √(2 + √(2 + ...))). Then we observe that the inner expression is also x, so we have x=√(2+x).

Solving for x we get
x² = 2 + x,
or
x² - x -2 = 0.

You could use the quadratic equation or you could guess the factorization. Somehow, by hook or by crook you get
(x-2)(x+1)=0.
And so x=2, as the kids guessed. The kids observed that it's the same trick for solving a geometric series:
1+1/2+1/4+1/8+ ... = x,
so
1 + x/2 = x,
which has solution x=2.

√2 is irrational

Here's an old proof that √2 is irrational. It is a proof by contradiction, and the fundamental theorem of arithmetic (which says that factorization into primes is unique). Suppose that √2 = p/q, where p and q are relatively prime. Then
(p/q)² = 2
so
p² = 2 q²
so p² has 2 as a factor, which means that p must have 2 has a factor. So p=2r for some r.

We now have
(2r)² = 2 q²
so
4r² = 2 q²
so
2r² = q²
and therefore q has 2 as a factor.

So both p and q have 2 as a factor, but we assumed that they were relatively prime, which is a contradiction.

The kids didn't really think much of this one. They seem take it for granted that √2 is irrational, so why do they need a proof. Or maybe they don't like proof by contradiction. (Maybe they are constructionist mathematicians...)