Gladiator Battle

Been some time since I had a new puzzle, and there are still two left in the paper "Games People Don't Play", though they are basically the same with a slight variation. Here is the first one:

Alice and Bob are competing team managers in a gladiator competition. Alice's gladiators have strength a₁, a₂, a₃...a_n and Bob's have strength b₁, b₂, b₃...b_m. Each round, Alice will select a gladiator from her team and then Bob will select one from his team and the chosen gladiators will fight.

If a gladiator of strength x fights a gladiator of strength y, the chance the one with strength x wins is given by x/(x+y). The losing gladiator is eliminated and the winning gladiator gains confidence from the fight, increasing the winning gladiator's total strength to x+y. Then a new round begins with Alice and Bob selecting gladiators to fight. The competition ends when one of the teams has run out of gladiators.

What is the optimal play? In particular, suppose Alice always chooses to send in her strongest gladiator, how should Bob respond?

It seems needlessly elaborate, especially given that in theory you have to solve for all possible values of a₁ through a_n and b₁ through b_m. It actually has a fairly elegant solution, but requires something of a mathematical transformation of the puzzle to reduce it to an easier setup.

XOR Solution

OK, anybody who cares has certainly solved the number puzzle from last time. Lets work through the solution now.

For convenience, I'll state the five facts here

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

Notationally, I'm going to use each statement with a letter 'a' or 'b' to refer to the first part or the second part of the statement. Specifically, when I say "statement 4a" I mean "N is divisible by 11", and "statement 2b" means "N is prime" and so on.
Alright, most people latch right onto 1 and 5 right away, to figure out how many digits the number has, and that is a sensible thing to do. Also note that 5a and 3b are exclusive, since a number cannot be a perfect square and one more than a perfect square (except for 1, I suppose, but it is easy to verify that 1 is not a solution to the puzzle). Looking at 3a, being the product of two consecutive integers means N=m(m+2) for m odd. That is N=m²+2m=(m+1)²-1 for m odd. So 3a says that N is exactly one less than a perfect even square. Thus, by 3, N is next to a perfect square, and so 5a is false.

This gives us that 5b is true and so 1a is false and 1b is true. But since N is even, and 3a says it is odd, 3b must be true. So we have N is even, has 3 digits, and is one more than a perfect square. Letting K=N-1, K=m² for m odd. Consider 4b now, if that is true then K is a perfect cube and so being a perfect cube and a perfect square means it is a perfect sixth power. We know 2⁶=64, 3⁶=729, and 4⁶=4096, so the only consistent thing would be if K=729. This would be N=730, which satisfies 2a and not 2b, while satisfying 4b and not 4a. This is the answer.

I recall some more elegant method of eliminating the false statements in 2 and 4, but I cannot remember it now. As usual, feel free to comment with any alternate methods you have.

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.