Number Puzzle

Time for another puzzle. This is a somewhat simple one I found somewhere random on the internets:

There exists an natural number, N, for which all of the following statements are true:

1. N has 2 digits XOR N is even
2. N contains the digit "7” XOR N is prime
3. N is the product of two consecutive odd integers XOR N is one more than a perfect square
4. N is divisible by 11 XOR N is one more than a perfect cube
5. N is a perfect square XOR N has 3 digits

What is N?

For the statements where the puzzle refers to digits, it is meant to be digits in a base ten representation of course.

When I found this puzzle, I dismissed it as being stupid and probably not worth the effort. I'm glad I gave it another shot though, the answer is somewhat pleasing to find. I'll admit its not amazing, but it shouldn't take more than 10 minutes and it is nice to work through the details.

Cards and Birthdays

Time for an aside from puzzles that I got from "Games People Don't Play", and an aside from puzzles in general. This post is going to be about the birthday paradox and human intuition on probability.

You are probably familiar with the birthday paradox, but I will state it anyway, just to be clear. The paradox (as with most "paradoxes" it isn't really a paradox, but just something unexpected) is the answer to the question:

How many people do you need to have in a room before there is a greater than 50% chance that two of them have the same birthday?

If you ask this question of an average person, they will probably state something like 100 or so. If they have some basic math behind them, they might guess 365/2, so about 180. The actual answer is around 20 (i'll derive it later). The basic misunderstanding comes from the difference from the question posed and the following question:

How many people do you need to have in a room before there is a greater than 50% chance that one of them shares your birthday?

Note the difference, in the first question you just needed any two people to share a birthday, in the second question you needed somebody to land on a specific birthday. This results in a big difference since in the second case each person has a 1/365 chance of having your birthday, but in the first one each person has a k/365 chance of landing on somebodys birthday, where k is the number of people in the room before them.

I always say that humans have no good sense of probability, evolution never gave us a need to understand things like the Monty Hall scenario on an intuitive level. We also have a bad habit of noticing patterns where none exist, another byproduct of our evolutionary history. It is fortunate that we have developed the mathematical capabilities to handle probability for us, or science would never have gone anywhere.

The birthday paradox came up in a conversation I was having with my officemate the other day. He found a site that asked the question

What are the odds that you will ever see a shuffled deck of cards in the same order twice in your life?

Ignoring the fact that this question isn't really well-posed, it is something of an interesting question. The site basically gave an argument involving 52! (the number of ways to arrange the cards in the deck) and concluded the answer was "very small". Actually, I guess most of the post was on deriving 52! rather than the analysis of what to do with that number. My instinct was to agree with this conclusion, but then a part of my brain said "birthday paradox" and I had to wonder. The other part of me saying back "52! is like 10⁶⁵" was a persuasive counterargument though. It basically depended on what the 20 was to the 365 in the birthday paradox... was it the logarithm? the root? just plain old linear with a coefficient? seems it is time to do the calculation.

Suppose we have a list of N outcomes of some experiment, all equally likely (N=365 for the birthday paradox, or N=52! for this card problem) and we check the experiment k times. What are the odds that we see the same result twice? Alternately, how large does k have to be for the probability we have seen the same result twice to be greater than P?

For the card situation lets assume that k is about 30000, this is an approximation of checking once a day for 80 years. So for approximation purposes, N>>k>>1. Now, what is the probability that none of our experiments ever get the same result? the chance that the first result is new is 1 (or N/N), the chance the second result is new is (N-1)/N, the chance the third one is new is (N-2)/N and so on up to the chance that the k^th one is new is (N-k+1)/N. So the probability that we never see the same one twice is given by

p=N!/((N-k)!N^k)

We can use Stirling's approximation on this (since Stirling's approximation for n! is embarrassingly good by the time n is 10) to get

p=N^Ne^-N√(2π N)/((N-k)^N-ke^-N+k√(2π (N-k))N^k)
=(1-k/N)^k-N-1/2e^-k

This is basically in a form that is ready to solve for the birthday paradox. Setting N=365 you find that for k=20, p=0.589 (remember p is the chance that none of them share a birthday) for k=21 p=0.556, for k=22 p=0.524 for k=23 p=0.492. So we see that at 23 people it is more than 50% that two of them share a birthday.

In the case of N=52! we need a few more approximations. I initially tried to use the fact that (1+x)^m=1+mx for small x (since k/N is certainly small) but there is a problem with that. Writing out the next term it is actually (1+x)^m=1+mx+m(m-1)x²/2, so if m is as big as x is small (specifically m²x² is not negligible compared to mx) then this is not going to be valid. For our problem, x=k/N and m=k-N-1/2, so m²x² is like k² which is not small at all.

We can approximate the term (1-k/N)^k-1/2 as 1-k(k-1/2)/N as long as the next term is small. The terms look like 1, k²/N and k⁴/N², so the third term is small compared to the second as long as k² is small compared to N. This is true for our case, but I'll come back to that later.

Given the approximation (1-k/N)^k-1/2 = 1-k²/N, we have

p=(1-k/N)^-Ne^-k(1-k²/N)

We need to figure out what to do with (1-k/N)^-N, which is a number very slightly smaller than 1 to a very large negative power, so its a bit unpredictable. If you remember your first year calculus course, you will see quickly what to do, the limit as m goes to infinity of (1+x/m)^m is e^x (this is sometimes a definition of the exponential function). So we may approximate (1-k/N)^-N as e^k, giving us

p=1-k²/N

Thus, the probability that you see the same event twice is approximately k²/N. For k=30000 and N=52! this is about 10^-59, so we can confidently say it won't happen. Turns out the human intuition is correct in this case, the birthday paradox won't overcome crazy scenarios like 52!.

Asking the other question of "how large does k have to be to achieve some fixed P" like the birthday paradox's 50%, the answer is a bit funny. You find that to achieve a 50% chance of seeing the same result twice you get k=√(N/2), so it would appear that the birthday paradox goes as the square root on N, rather than the logarithm or something else. However, this is technically mistaken, since we needed k² to be much smaller than N in our approximations, this answer is invalid. It is correct to say that the birthday paradox asymptotes to something similar to √N, since if it is much weaker than that (like logarithm or cube root or something) our approximations become good again and you get the answer of square root.

More Frungy

Time to slack from work, and instead post the solution to the card problem from last time. In standard form, it is easiest to simply solve the simpler case first. For general notation, we will assume the deck has N red cards and N black cards, the final goal is to solve N=26.

First, the N=1 case. There is little point in betting on the first card, the adversary will just make you wrong anyway, so after the first card comes by, you know what the second card is. You bet everything on the second card, are correct, and end with $2.

Now for N=2. There is actually still no point in betting on the first card (this is a pretty general result), so lets say the first card is red. Now there is 1 red and 2 black in the deck. One might be inclined to say there is no point in betting here, but then the adversary will surely show us a black card the second time and we are in the N=1 case. Really, the fact is we would be very happy is the adversary showed us the second red card on the second round, so happy that we might be willing to pay him a small amount of money to make it happen.

Suppose you bet $0.1 on the second card being black, then if it is black, you have $1.1 and are in the N=1 case, so you get to double that to $2.2. If the second card is red, you have $0.9, but now there are only black cards in the deck, so you get to quadruple that and end with $3.6. Clearly the adversary will let you end with $2.2. Now suppose we instead bet $0.5 on the second card being black. If it is black we have $1.5 and get to double that to $3. If it is red we have $0.5 and get to quadruple that to $2. Clearly the adversary will let us have $2.

Alright, we need a middle ground. Bet x on the second card being black. If it is, we have 1+x and we get to double that to 2+2x. If it is not black we have 1-x and we get to quadruple that to 4-4x. The adversary will give us whichever is lower, and since one is an increasing function and the other is a decreasing function, the lowest one is maximized when they are equal. Solving 2+2x=4-4x we have x=1/3. So we should bet 1/3 on the second card being different than the first one and we are guaranteed to end with $8/3.

Note that in the solution to the N=2 case the answer comes out path independent, in that after two black cards and one red card have come by, you have $4/3 no matter if it was BRB or BBR (I'm sort of assuming that the adversary chooses to show black cards rather than red when the situation is symmetric). Naturally it has to be path independent, if the different paths gave different amounts of money, the adversary would send you on the worst path he can find. Due to this, it is a general feature that the solution for general N be path independent.

Now let us try to solve with general N. As we have seen, since the solution is path independent on how the adversary shows us cards, there must be a function f(r,b) that represents how much money we have when r red cards have gone by and b black cards have gone by. Clearly f(r,b) could depend on the specific value of N we use, so it really should be f(r,b,N), but I'm going to suppress that last variable. We also know that f(0,0)=1, and f(r,b) must equal f(b,r) by a similar argument to the one that shows path independence, and f(N,N) is the answer we seek.

Suppose we have see r red cards and b black cards go by, so we have f(r,b) money according to our strategy, and we now bet x on the next card being red (if we are instead betting on black, we just let x run negative). If the next card is red, we have f(r,b)+x money and if it is black we have f(r,b)-x money. This means that:

f(r+1,b)=f(r,b)+x
f(r,b+1)=f(r,b)-x

For some value of x. Eliminating x, we have

2f(r,b)=f(r+1,b)+f(r,b+1)

Similar to the relation for Pascal's triangle. To make it look a bit more familiar, lets define g(r,b) by f(r,b)=2^r+bg(r,b), then g obeys the relation

g(r,b)=g(r+1,b)+g(r,b+1)

Now that looks like the Pascal relation, but its backwards. Next lets define h(r,b)=g(N-r,N-b), so h counts how many cards are left in the deck rather than how many cards we have seen go by. Then h obeys

h(r,b)=h(r-1,b)+h(r,b-1)

Perfect for solving as a previously solved problem. But since we knew f(0,0)=1, this means we know h(N,N)=1, so h is a bit backwards. We simply modify this by defining p(r,b)=h(r,b)/h(0,0). Now p obeys

p(r,b)=p(r-1,b)+p(r,b-1)

and p(0,0)=1, so p is the Pascal function, that is

p(r,b)=(r+b)!/(r!b!)

We can find h(0,0) by noting that p(N,N)=h(N,N)/h(0,0)=1/h(0,0), so h(0,0)=1/p(N,N), giving

h(0,0)=N!N!/(2N)!

so that we have h

h(r,b)=p(r,b)h(0,0)
=(r+b)!N!N!/(r!b!(2N)!)

This gives us g

g(r,b)=h(N-r,N-b)
=(2N-r-b)!N!N!/((N-r)!(N-b)!(2N)!)

Finally, we get f

f(r,b)=2^r+bg(r,b)
=2^r+b(2N-r-b)!N!N!/((N-r)!(N-b)!(2N)!)

ugh.

At least we really only care about 1 thing, f(N,N), its simple enough:

f(N,N)=2^2NN!N!/(2N)!

Which is just 2^2N divided by _2NC_N. For N big enough to use Stirling's approximation (which 26 is), we have

f(N,N)=2^2NN^2Ne^-2N(2π N)/((2N)^2Ne^-2N √(2π 2N))
=√(π N)

Actually comes out quite simple. For N=26 this is about 9.

So this actually is the complete construction of the strategy. At any given time you have seen r red and b black cards come by, you have f(r,b) money left, and you should bet f(r+1,b)-f(r,b) on red (or, equivalently, f(r,b+1)-f(r,b) on black) and you will end with f(N,N) money. Actually performing the strategy can be done in a slightly different way though.

Suppose you have K assistants, where K is the number of possible configurations of the cards in the deck (that is, K=_2NC_N). Each assistant is given 1/K money to start and is told a list of R's and B's that could correspond to the cards in the deck (for N=2, the assistants are told RRBB, RBRB, RBBR, BRRB, BRBR, BBRR), and you let them all bet simply assuming that their own list is correct. Precisely one of them will be correct and will double his money 2N times (once for each card). The rest all lose their money. The correct assistant ends with 2^2N divided by _2NC_N money, exactly f(N,N).

Lets try this for N=2, we have our 6 assistants which will be labeled as follows:

1.RRBB
2.RBRB
3.RBBR
4.BRRB
5.BRBR
6.BBRR

Each assistant is given $1/6.

This game starts, and assistans 1,2,3 bet their $1/6 on red while assistants 4,5,6 bet their $1/6 on black. We (the real holder of the $1) add this up and bet a net zero. Suppose the first card is red. This eliminates assistants 4,5,6 and assistants 1,2,3 now all have doubled their money to $1/3. We have a total money of $1.

Next card, assistant 1 bets his $1/3 on red and assistants 2 and 3 bet their $1/3 on black. We add this up and bet $1/3 on black. Suppose the next card is black. This eliminates assistant 1 and doubles assistants 2 and 3's money to $2/3. We have a total money of $4/3.

Next card, assistant 2 bets his $2/3 on red and assistant 3 bets his $2/3 on black. We add this up and bet nothing. Suppose the card is black. Assistant 2 is eliminated and assistant 3 doubles his money to $4/3. We have a total money $4/3.

Final card, assistant 4 bets his $4/3 on red. We add this up and bet $4/3 on red. We double our money to $8/3.

This game also has one other neat feature if you actually play it. All betting strategies are fair, as long as you never bet on a card that does not remain in the deck. That is to say, in any given position of red and black cards left, no matter what you bet on what card coming next, your expectation of final money (against a shuffled deck, not an adversary) is the same, as long as when the deck is out of one type of card you bet maximally on the card colour that is left.

Card Betting

Continuing on my plan of posting the puzzles I found in the paper "Games People Don't Play", I have a card flipping puzzle this time. Back when I started this blog I posted a card flipping problem that Bart had told me, and the puzzle this time is something of a continuation of that one:

There is a deck of 52 cards, 26 red and 26 black. You will be playing a game where you bet on what is the next card in the deck. You begin with $1 and can make a bet of any real number between zero and the amount of money you have on whether the next card in the deck is red or black. The top card of the deck is then revealed and if you were correct you gain the amount you bet, if you were incorrect you lose the amount you bet. Then the game continues with betting on the next card in the deck. The game ends when there are no cards remaining in the deck to bet on. What is the optimal betting strategy assuming that the deck is being arranged by an adversary?

I really like the sort of puzzle that seems flat out impossible to do anything at first, putting the player up against an adversary seems like a pretty insurmountable obstacle, but you still have some wiggle room.

Alice Wins?

I guess I should put up the solution to the second two numbers problem. The fact that I ask for an equilibrium strategy sort of gives something away I suppose, because in the first one there is no equilibrium strategy (Alice can make Bobs winning chance 1/2+ε for any positive ε so there is no optimal one). To begin, what is the strategy space for Bob? Bob sees a number, x, and must decide if that number is larger or smaller based simply on that number. All Bob can do is select a function f(x) to give him the probability that he says x is the larger number. The solution to the last puzzle strongly suggests that f(x) should be a strictly increasing function, but it is worth noting that if f(x) is simply 1/2 everywhere, then Bob is certain to get 50% on this game, so there is no way Alice can push him lower than that.

Suppose Alice is given f(x) (Bobs strategy) and is given the two numbers y and z from (0,1) (also, we may as well assume z>y). Now, if Alice chooses to show Bob y, Bob has a 1-f(y) chance to win, and if Alice chooses to show z, Bob has a f(z) chance to win. Thus Bobs chance to win (if Alice knows f(x)) is given as:

min(1-f(y),f(z))

Now we must integrate this over all space of y and z. The natural integral would be ∫ ∫ dy dz with both going over (0,1), but this does not work because we have already assumed z is the larger of the two numbers. We should simply restrict the integral to z ∈ (0,1) and y ∈ (0,z) and multiply by 2 to take care of the other half of the region where y happens to be larger. Bobs chance to win is given as

2 ∫ ∫ min(1-f(y),f(z)) dy dz

with y from 0 to z and z from 0 to 1.

The next thing to know is that Bob is trying to maximize this integral. We must select an f(x) to make this as large as possible. Remember we already know that with f(x)=1/2, we trivially get 1/2 for the answer, so really we need only ask if we can make it larger than 1/2. You can try some functions out for a while, but in the end you will see that nothing will integrate to more than 1/2.

We can prove that Bob cannot get better than 1/2 by using 2 features about the min and max functions:

1.min(a,b)+max(a,b)=a+b
2.min(a,b) ≤ max(a,b)

Now we define

P=2 ∫ ∫ min(1-f(y),f(z)) dy dz
Q=2 ∫ ∫ max(1-f(y),f(z)) dy dz

integrated over y from 0 to z and z from 0 to 1 as before. We seek to prove that P ≤ 1/2 for all choices of f.

Fact 2 from before shows us right away that P ≤ Q, and fact 1 gives us

P+Q=2 ∫ ∫ (1-f(y)+f(z)) dy dz
=2 (∫ ∫ 1 dy dz - ∫ ∫ f(y) dy dz + ∫ ∫ f(z) dy dz)

The first integral is simply 1/2 (the area of integration) and in the third integral you can do the y integral separately to get ∫ zf(z) dz integrated from 0 to 1. For the second integral we simply rewrite the integration region from y ∈ (0,z) and z ∈ (0,1) to z ∈ (y,1) and y ∈ (0,1) so we can do the z integral first to get ∫ (1-y)f(y) dy integrated from 0 to 1. We currently have

P+Q=1 - ∫ (1-y)f(y)dy + ∫ zf(z)dz

But using the substitution z=1-y the two integrals are trivially identical for any f(x). Therefore,

P+Q=1

Now since P ≤ Q we have (by adding P to both sides) 2P ≤ P+Q so 2P ≤ 1 therefore P ≤ 1/2 as we sought.

OK great, so if Alice knows Bobs f(x), there is no way Bob can choose an f(x) that guarantees to get any better than 1/2. So if there is an equilibrium strategy, it must be 50/50. But is there one? Can we construct a strategy for Alice that makes sure Bob cannot get better than 1/2 even if we have no idea what f(x) he chose? We can, and its actually what one would instinctively do if one were playing this game.

Consider you are Alice and you are handed the numbers 0.1 and 0.5, which one would you show Bob? The obvious choice is 0.5, 0.1 looks too obviously the low one. How about 0.8 and 0.4? Less obvious, but it would seem the rational guess is 0.4. How about 0.7 and 0.4? again 0.4, 0.7 has less space above it than 0.4 has below it. How about 0.8 and 0.6? 0.6 is pretty clearly better. How about 0.7 and 0.3? now it seems they are symmetric, no good way to choose. How about 0.6 and 0.4? again symmetric.

See what the strategy is? Just show Bob whichever number happens to be closest to 0.5. Now, if we obey this strategy, what is Bobs chance of winning? First let us rescale the numbers down by 0.5 so that the two numbers, y and z, range from -1/2 to 1/2 and we show Bob whichever one is closer to zero.

Consider the y-z plane in the box y ∈ (-1/2,1/2) z ∈ (-1/2,1/2). The numbers we get select a point in this region. Which number is y and which is z doesn't matter here, select which is which at random.

Divide up the region into 4 pieces using the lines y=z (from bottom left to top right) and the line y=-z (from top left to bottom right). The 4 regions are "top" (where z>0 and y is between -z and z) "bottom" (where z<0 -y="" -z="" and="" between="" is="" left="" right="" where="" y="" z="">0 and z is between -y and y). If our two numbers put the point in either "top" or "bottom" we show Bob y. If the point is in "left" or "right", we show Bob z.

Suppose we have a point in "top". We show Bob y and he has to guess that y is the smaller number. The chance of him doing so is 1-f(y). For all points in "top", we would integrate this to get the total probability of Bob winning, given a point in "top". That is, when the point lands in "top", Bobs chance of winning is ∫ 1-f(y) integrated over "top". In "bottom" we show Bob y and he must guess it is the larger number. He does this with probability f(y) so, 1/4 of the time, Bobs chance of winning is ∫ f(y) integrated over "bottom". Note that ∫ f(y) in "top" is the same as ∫ f(y) in "bottom", since they both have the same y values.

Using the same argument for "left" and "right" we get Bobs chance of winning is (∫ 1-f(y) over "top")+(∫ f(y) over "bottom")+(∫ 1-f(z) over "right")+(∫ f(z) over "bottom"). The integrals of unknown functions all cancel, leaving ∫ 1 over "top"+∫ 1 over "bottom" giving 1/4 each (their areas) for a total of 1/2.

Simply put, if Alice shows Bob 0.3 (say), and Bob knows this number is the one that is closer to 1/2, then the other number is equally likely to be in (0,0.3) or (0.7,1) and Bob cannot tell those apart.

Thus if Alice follows the strategy "show Bob whichever number is closer to 1/2", then Bob cannot do better than 1/2 no matter what f(x) he chooses. If Bob uses the strategy f(x)=1/2 (so, "flip a coin") Bob cannot do worse than 1/2 no matter how Alice chooses the number to show. So this gives the equilibrium strategy (or, at least, an equilibrium strategy).

I find it funny that if you do this game with real people, the Alice player will probably typically hit on the correct strategy naively, even though they will then likely try to follow it up by "out-thinking" the other player, because thats just what humans do.

Two More Numbers

Alright, now that the two numbers puzzle is out of the way, time for the follow-up. I first learned this puzzle in a paper called "Games People Don't Play" which I found on the comments at the xkcd blag:

Two numbers are selected uniformly at random from the interval (0,1) and shown to Alice. Alice must select one of these two numbers and show it to Bob. Bob must then guess if Alice has shown him the larger of the two or the smaller of the two. What is the optimal (equilibrium) strategy for the players?

This time Alice does not get control of the two numbers, and Bob is aware of the distribution, but Alice gets to choose what number Bob sees, so who gains the advantage from those changes?

Only A Little

Time for the solution to the Two Numbers problem. I suppose I could just state the solution right away, but I like to do something of a derivation first.

First of all, consider the results of the following strategy for Bob:

If the number you see is greater than zero, guess it is larger, if the number is less than zero, guess it is smaller

Easy enough to implement, if both numbers that Alice wrote down are positive, then you are still 50/50. If they are both negative then you are again 50/50, but if one number was positive and one was negative, then you are guaranteed to win.

Alright, thats all well and good, naturally if Alice knows you are doing this, then she won't ever write down a positive and negative number together of course, so this is not actually guaranteed to give you a better than 50% chance of winning the game. Now, instead of greater than/less than zero, why not use a random number K. Perform the following strategy:

Select a nonzero probability distribution over the reals f(z). After Alice writes down the numbers, select a number K using f(z). If the number you see is greater than K guess it is the larger one, if the number you see is smaller than K then guess it is the smaller one.

By nonzero probability distribution I mean that f(z)>0 always and ∫f(z)dz = 1 when integrated over all the reals. Basically, the strategy is to assume that the unseen number is near K.

Suppose Alice writes down x and y with y>x, then if x>K or K>y you are simply 50/50, but if y>K>x you win the game 100%. The chance of you winning is therefore

∫f(z)dz+(1-∫f(z)dz)1/2
=1/2+1/2∫f(z)dz

Where the integral is between x and y (giving the chance K lands between x and y). Since f(z)>0 always, this is greater than 1/2 in all cases and is a valid solution. Naturally, if Alice knows f(z), she can make that integral as small as she likes, but she cannot make it non positive.

One can make a slightly more general (but not actually any better) solution as well. Consider that Bob looks at the number before choosing K. Then the chance that K will be less than x (and thus guess x is larger) is ∫f(z)dz integrated from -∞ to x. Let p(x) be that number (the probability that we say x is larger). Clearly we have p(x) positive, increasing, and 0 at -∞ and 1 at +∞.

Let Alice choose number x and y with y>x. Now the chance Bob wins given some function p(x) is 1/2 (the chance he is given y) times p(y) (the chance he says y is larger) plus 1/2 (the chance he is given x) times 1-p(x) (the chance he says x is smaller). thus giving

1/2 p(y)+1/2(1-p(x))
=1/2+1/2(p(y)-p(x))

Not surprising given that p is the integral of f from before.

Anyway, the only thing that we need to demand of p(x) is that is be strictly increasing and bounded between 0 and 1. It does not matter that it goes to 0 at -∞ or 1 at +∞ (though, I guess it might as well). So the strategy of saying the number you see, x, is greater with probability p(x) is more general than the strategy of picking K from f(x) (though not any better, even if it is more general). Again, given p(x) Alice has the power to make p(y)-p(x) as small as she wants, but she can never stop it from being positive.