Frisbee Catching

You'd think that with a puzzle as simple as that one I would have posted an answer sooner, but what can you do? Anyway, in answer to the frisbee flipping problem, first I'll give a wrong answer that they actually use when people play ultimate.

Flip twice, calling it heads if they are the same and tails if they are different.

Its not hard to see that this won't work. if the probability a coin comes up heads is P(H)=k and tails is P(T)=1-k, then the probability of "same" or "different" are given as:

P(S)=P(H)²+P(T)²
P(S)=1-2k+2k²
P(D)=P(H)P(T)+P(T)P(H)
P(D)=2k-2k²

and so the amount more common "same" is over "different" is

P(S)-P(D)=1-4k+4k²
=(1-2k)²

always positive. Thus, if you are ever presented with this situation, call "same".

As a side note, since P(T)-P(H)=1-2k is less than 1, using "same" and "different" has a smaller gap between the good strategy and the bad strategy (squaring a positive number less than one pushes it closer to zero). So it is possible to "converge" to a fair coin by using nested versions of the "same" and "different" strategy. Specifically, you could get within any epsilon of a fair coin if you were given the value of k.

Alright, for the actual answer to the problem (at least the only answer I know of):

Flip the coin twice, discard the result of both sides come out the same, use the second result if they come out different

Since the probability they come out different is 2k(1-k), it will on average take 1/(2k(1-k)) tries to get a result using this method. I suppose a better method might take less flips, if anybody has one feel free to post it in the comments.

Frisbee Flipping

So, a question that I found on the intertubes some time ago was re-inspired by talking with Andres. In a game of ultimate frisbee, the teams must flip a coin to decide who goes first, however, a fair coin is not usually available. What is available are frisbees, so they try to use them as coins. Its not hard to guess that a frisbee does not make a great coin, as it is biased to land on one side over another. This gives us the problem to solve:

You are given a biased coin that lands on heads with probability k and tails with probability 1-k (k ∈ (0,1)). Without knowing the value of k, how can you use this coin to simulate a fair coin?

I'll post the solution next time.

Ray's Random Walk

So, I was thinking about just how good Sam and Ray can do by simply taking the random strategy. Sam always guesses the right answer and Ray simply guesses randomly. Its easy to see that this strategy has at least 50% chance to work, since you might just get the first one right and quit (of course the argument about just repeating the strategy n times to make $n fails, but whatever). So I started to wonder, the probability of at some point getting to $1 within the first k steps is lower than 1 and can not decrease as k goes upward. Thus in the limit as k goes to infinity it must converge to some real number, what real number does it converge to?

I suppose I could post it as a logic problem, but I'd rather just work out the solution right now, as its actually sort of tricky. Also I'm not 100% about my proof anyway, so maybe somebody can point out to me a flaw or something.

First, lets reformulate the problem:

Consider a random walk on the integers, starting at 0. At each step, we have a 1/2 chance to move up one step from n to n+1 and a 1/2 chance to move down 2 steps from n to n-2. What is the probability that we ever reach 1?

If you are concerned about the ambiguity of the term "ever reach", then define f(k) to be the probability of reaching 1 within the first k steps (well defined, nondecreasing, and bounded above by 1). Now ask what is the limit of f(k) as k tends to infinity.

Suppose we let P(n) represent the probability of ever reaching point n, we are interested in P(1) given that P(0)=1. Notice that P(n) will obey the relation:

P(n)=1/2P(n-1)+1/2P(n+2)

Its not so easy to prove that statement rigorously (I'm not even confident I know how to), but it is intuitive to say that to be at n, you came in from n-1 or n+2.

Next we must define the 'derivative' function:

d(n)=P(n+1)-P(n)

Then, we can rearrange our earlier equation to

P(n)-P(n-1)=P(n+2)-P(n)
d(n-1)=d(n)+d(n+1)

d(n) seems to obey some sort of "reverse Fibonacci" relationship, d(n) is determined as the sum of d(n+1) and d(n+2). Equivalently, and in a way that makes more sense:

d(n+1)=d(n-1)-d(n)

So, it is clear d(n) would be uniquely determined by any initial two values. There is a clean relationship you can use to find d(n) given d(0) and d(1) (similar to the one for the Fibonacci Squence in terms of the golden ratio), I will give an outline of the derivation.

Define a vector D(n) by [d(n+1),d(n)]. Then D(n+1)=A D(n), where A is the matrix [[-1,1],[1,0]]. You can diagonalize A into UTU^-1, so that D(n)=AⁿD(0)=UTⁿU^-1D(0). Tⁿ is easy to calculate, as T is diagonal.

This will give you a relationship of d(n) in terms of d(1) and d(0). The golden ratio φ will show up everywhere (φ=(sqrt(5)+1)/2 and obeys φ=1+1/φ).

We can lock down d(0) and d(1) by using the boundary conditions. It is clear that P(n) must be a non-increasing function for n>0, because in order to reach 5, you must pass through 4 first, so P(5) cannot be greater than P(4). This means that P(n) must converge to some number as n tends to infinity. This guarantees that d(n), as the difference of successive P(n) terms, must converge to zero.

If one has been following along with the math and actually found the exact expression for d(n) (its not very pretty, so I didn't want to illustrate it), you find that it has terms of φⁿ and φ^-n. The condition d(n) converges to zero as n tends to infinity guarantees that the coefficient of φⁿ must vanish, giving us d(1)=d(0)/φ, and cleans up the relationship to

d(n)=d(0)/φⁿ

Now we must only lock down d(0). We know that P(n) is the sum of the first n d(i) values plus P(0) (which is 1). But this sum is an easy geometric sum:

P(n)=1+d(0)(1-φ^-n)/(φ -1)
=1+d(0)φ(1-φ^-n)

So, as n tends to infinity, P(n) tends to 1+d(0)φ. It seemed pretty self-evident to me that P(n) either tends to zero or one, but I have found a pretty convincing argument for zero.

After the first N steps, you will have moved right a spaces and left 2*(N-a) spaces (a is a number between 0 and N). You have ended on space 3a-2N, and this is clearly positive if a>2N/3. The probability of any particular value of a is (N choose a)/2^N. The probability of ending to the right of zero is the sum of that as a goes from 2N/3 to N. This is the sum of the right third of the Nth row of Pascals triangle, divided be the sum of the whole Nth row. This will tend to zero as N tends to infinity (as the right third and the left third are equal in size, but the middle third is always bigger, eventually much bigger).

From this, I would conclude that P(n) tends to zero as n tends to infinity (not rigorous mind you, but I'm convinced). This guarantees that d(0) is -φ^-1 and so:

P(n)=φ^-n for n>0

Note that we needed the argument that P(n) is nondecreasing as we go to infinity, which fails for n<0, so I don't know what the behavior is there. In conclusion, if you use the random strategy in the Sam and Ray problem to try to get $n, it will work with probability φ^-n.

Salmon Ray

Alright, time for further musings on the Sam and Ray problem. Actually there are two separate realizations here, but both of them seem to go nowhere, and I will post them anyway because this blog is to allow me to get this stuff out of my brain so I can one day actually finish my thesis.

So, the first thing was that I thought about the possibility of constructing the set S referred to in the Sam and Ray solution, but this time using a Hamming distance of two instead of one. Due to the fact that the best set was constructed out of efficiency in the initial solution, lets try that again.

We wish to construct a set S of binary strings of length N. S must have the feature that every possible binary string of length N is within Hamming distance 2 of exactly one element of S. The demand of exactly one element is an efficiency demand, if there were two elements, then we have "wasted elements" in some sense. Also making that demand will at least make this problem tractable.

What do we know about S? There are 2^N possible binary strings that must be covered by S, so how many strings are covered by a single element of S? Each element covers itself (1) plus neighbors that are one bitflip away (N) plus neighbors that are two biflips away (N(N-1)/2), thus N²/2+N/2+1. So the number of elements that S has is at least 2^N/(N²/2+N/2+1), which may or may not be an integer. However, if that number is not an integer, we will not meet our efficiency demand, so we will insist that 2^N/(N²/2+N/2+1) is an integer. 2^N/k will only be an integer if k is also a power of two, so we know that there exists an M such that:

N²+N+2=2^M+1

then |S|=2^N-M. Also, keep in mind, I have not proved that this S actually exists when N satisfies the above, but I have proven it cannot exist (with the efficiency demand) if N does not. Of course, ignoring the efficiency demand S always exists, but its probably ugly.

Solving our polynomial for N, we get

N=1/2(√2^M+3-7-1)

or, in a format which is less visually offensive and more illustrative:

N=1/2(J-1)
J²=2^M+3-7

Since N is an integer, J will have to be an odd integer, further in order for M to exist as we wanted, J²+7 will have to be a power of two (which also demands J be an odd integer, good).

Alright, lets try out some numbers to find candidates for J.

J=1 ⇒ J²+7=8, good. Then M=0 and N=0. Well, OK, this seems to be the trivial solution.

J=3 ⇒ J²+7=16, good. Then M=1 and N=1. Another trivial solution.

J=5 ⇒ J²+7=32, wow, this works great. Now M=2 and N=2. Still a trivial solution, as S={00} is good enough in the N=2 case.

J=7 ⇒ J²+7=56, finally not a power of two, I was worried.

J=9 ⇒ J²+7=89, again nothing.

J=11 ⇒ J²+7=128, cool. So M=4 and N=5. S must have cardinality 2^N-M=2 and the set is simply S={00000,11111}.

This is good, we already knew about the cases N=0,1,2, and 5. In fact the N=5 case is what our information sending strategy is based on. So the next one will give us what we really want. You can try the next few values of J yourself, but they won't give you any powers of two for some time, instead I resorted to Maple. Actually, it is more practical to ask Maple for numbers such that 2^N-7 is a perfect square rather than J²+7 being a power of two, because then you go through the numbers exponentially rather than quadratically. You will find that J=181 is the next solution.

J=181 ⇒ J²+7=32768=2¹⁵, so M=12 and N=90. S must have cardinality 2^N-M, so |S|=2⁷⁸.

OK, now I'm interested. We have a sequence of numbers that has N going 0,1,2,5,90, M goes 0,1,2,4,12, J goes 1,3,5,11,181, and |S| goes 1,1,1,2,2⁷⁸, anybody else out there see the pattern?

I'm mostly interested in the next J value, and Maple was able to tell me there aren't any before 2²⁰⁰⁰⁰. This was a bit worrisome, as the numbers 1,3,5,11,181 sort of make me think of things like the busy beaver function or the Ackermann function, so I expect the next number to be Graham's number or something silly (probably not that big, but you get the idea). Anyway, I decided to take a stroll over to the On-Line Encyclopedia of Integer Sequences and type in 1,3,5,11,181. Turns out its in there as A038198, and that there is no next number in the sequence, its well known as the solutions to Ramanujan's Square Equation.

OK, so my guess that the next number would be huge wasn't far off, at least I was correct in guessing that Maple would never find it for me. Anyway, this means that there is no more than one set S satisfying our efficiency demand that we don't know about already (for example {00000,11111}) (there might not even be any of course, I still haven't proven existence). I guess this means that there won't be worries about the general construction like there was in the Hamming distance one case, one just needs to explicitly construct the set in the case N=90 and you have done all the possible ones. Now, I have no idea how to construct the set, if anybody out there knows I would love to hear it, until then I'll give it a shot in my spare time and if I get anywhere I'll post it.

So, let us assume we actually had this set S, we can now give it to Sam and Ray. Sam now has the ability to specify any 90 digit string two within two digits by only using 78 bits of data. 78 bits of data costs $79, and getting 90 bits with only two wrong earns $88-$4=$84. So they earn $5, and have two wrong to send out new bits. Assuming they just convert those bits directly into cash, they earn $7 (they can do better than just convert to cash, but who's counting anyway). How long does it take this strategy to earn said $7? This algorithm takes 77x5 steps to send out the data and then a string of 90, finally the first bit and the last two bits gives us 478, and average of 68 steps/$, compared to my earlier strategies of 46 steps/$ and 72 steps/$. Though I will concede that I am being a bit wasteful about my endpoints, so my analysis isn't great. Anyway, I will conclude that using a Hamming distance of 2 does not improve your efficiency by much, and in fact costs you quite a bit if you only intend to earn $1 before quitting.

I still have more musings on this problem, but this post seems long enough for now.

Last thing to say before I close this one up mostly a reminder to myself that I would still like to construct S with N=90. It seems very interesting that there would be exactly one such set, it probably has neat properties. Or does not exist, which is also a neat property.

Sending And Receiving

Alright, time for the solution to the Sam And Ray problem. First I'll do my usual thing of going through the thought process before getting to the solution, because I like hearing myself talk (or type, I suppose). (Edit after finishing this post: its crazy long and shows just how much I like hearing myself type)

Its pretty easy to see that right out you are down $2, and get to send a bit of information (I mean a technical "bit", not a small amount or something vague), and the real question is what do we do with this bit. We won't get very far trying to tell Ray what all the answers are ("We" is Sam, of course), because every bit costs us $2 and only makes $1. However, we can do something sort of neat, we can tell Ray what the most common one of the next three is. In that case we guarantee that Ray will get two of the three correct, and on the wrong one we can send out another bit. In the chance that there is no wrong one, we get three correct for only 1 bit of information. If we get two right and one wrong, we lose no money, and if we get 3 right at the cost of one bit, we gain $1. This gives us our starting strategy:

Sam tells Ray what the most common one of the next three will be, Ray guesses that for the next three and Sam guesses that when it will be correct. On the one that they get wrong Sam tells Ray what the most common one in the following block of three will be, and if there isn't one they get wrong, then they end off $1 ahead and quit.

Thats great if the numbers are assigned randomly, since a given block of three will all be the same with 1/4 probability, this will work within the first N blocks of three with probability 1-(3/4)^N (proof left to the reader). So eventually, with probability 1, they will succeed if the list of numbers is infinitely long.

Of course, we might want a solution that is guaranteed to work in some finite amount of time, perhaps our players must specify beforehand how long they are going to play for. Or perhaps the numbers are being set by an all-knowing adversary, and we want a solution that works for all possible binary lists.

Alright, lets expand our solution. Rather than sending information about the most common one in the next three, lets do the next five. We will get 3 right and 2 wrong, costing $1 and our bit that we have sent, and we get to send 2 new bits. Of course, if we happen to get 4 right we gain $2 and still get to send a bit, and if we get 5 right we gain $4 at the cost of our bit, either of these situations is a gain.

So, using this, we can spend $1 and a bit to send 2 bits. This is much better than spending $2 to send a bit. Can we get any better with seven?

Sending information about seven bits, we get 4 right and 3 wrong, costing $2 and sending 3 bits at the cost of 1 bit. This is not any better than the five case, not really any worse overall, but perhaps we don't want to buy in bulk (actually, it comes out probabilistically better I think, since you are more likely to get 5 right and 2 wrong than 4 right and 1 wrong, but we already have a probabilistic solution anyway).

So, we have our information sending strategy:

Sam tells Ray the most common one in the next block of 5, Ray is to guess that for the entire block. On the ones they get two wrong, Sam will send out 1 bit of "useful information" and 1 bit telling the most common one in the next block of five. On the ones they get one wrong, Sam will send out a bit saying the most common one in the next block of five. On the ones they get all five right, Sam will just send additional data about the next block of five immediately after.

After Ray has reached the pre-agreed amount of data, the last bit Sam sends out does not say the next block of five, but is in fact the final bit of "useful information"

I realize that it is possible to handle the "get all five right" cases more elegantly, but those ones are just gravy anyway, and do not actually affect the solution.

This strategy gives Sam the ability to send Ray K bits of information at a cost of no more than $(K+1). Now what can we do with this information?

Clearly it is a bad idea to simply try to get a bunch right, as there is no way we can get K+1 answers correct with only sending K bits of information, but perhaps its is acceptable to get a few wrong in there, that might just give us enough wiggle room.

How about we try to get only one wrong in a list of N bits. Clearly, if getting one wrong is acceptable, then we can specify 3 bits using just 1 bit, as every three bit binary string is only one away from 000 and 111. This is a concept called Hamming distance, the number of bitflips needed to get from one binary string to another.

We seek to find a set S of binary strings of length N such that all binary strings of length N are within 1 Hamming distance from at least one member of S. (People familiar with Hamming codes can probably already see the solution now.) So, how do we do this? We want to be as efficient as possible, so we do not want to waste any elements of the set. If there were any binary string that was within distance 1 of two different members of S, we have wasted overlap.

An element of our set will cover N+1 elements (itself, and each of N individual bitflips), and we have 2^N elements to cover. If we want exact coverage to be possible, we will have to demand that 2^N/(N+1) be an integer, specifically there must exist an integer M such that N+1=2^M. We see that S will then have 2^N/(N+1) elements, so in terms of M the cardinality of S is |S|=2^(2M-1-M) (if it exists, I haven't actually proven that yet). Lets look at a few simple cases first, cause thats how I roll.

For M=1, we have N=1 and |S|=1. Clearly all binary strings of length 1 are within distance 1 of either the string "0" or the string "1", so S does indeed exist here.

For M=2, we have N=3 and |S|=2. All binary strings of length 3 are within distance 1 of either 000 or 111, so using S={000, 111} gives our set.

For M=3, we have N=7 and |S|=16. Ok, S has gotten big pretty fast, before trying to find it, lets go back to Sam and Ray and make sure this will actually give us something.

If we have the set S for N=7, we could specify an element of it with 4 bits, costing us $5. This would allow us to specify a 7 bit string to within 1 bitflip. We would get 6 right and 1 wrong, making $4, thus we have lost $1. However, there is a ray of hope, we did get one of those wrong, so signal is still open. That signal could be used to specify the next list of 5 (as per our information sending strategy) and thus we can now successfully send out K bits of information at the cost of $K. Using our set S for N=7 again, we can specify an element of it using 4 bits costing us $4. We now get 6 right and 1 wrong again, losing us $4, so we have broken even. But once again, we still have signal, we can send a bit on the wrong one. Thus we finally get one right and win the game.

Not that it matters, but how many bits did it take to win? This took us 3 sets of 5 to specify 4 bits, then a set of 7 to use our set S, then another 3 sets of 5 to send out more information and then another set of 7. Also there is the first bit we send out, and the last one we get right, for 3x5+7+3x5+7+1+1=46 bits of information total. Actually a clever adversary might have us get some blocks of five totally correct to mess us up, but that just means we don't have to play for as long, so I think that doesn't make this any worse.

Anyway, before we move on to proving that S actually exists, lets try to see if larger sets can get us any further. Considering the case M=4, we have N=15 and |S|=2¹¹. Alright, I certainly hope we can find a general solution for how to find S now, because I am not in the mood to list out all of those.

We can specify an element of this S using 11 bits, costing $12 and we get 14 right and 1 wrong in a string of 15, making $12. Thus we break even and can send out signal on the wrong one, winning the game. The length of this strategy is 11x5+15+1+1=72. Oddly enough, the more convoluted strategy is shorter.

Alright, now to prove S exists, I will give the general method, and show with an example in the case N=7. N will be 2^M-1, so each bit can be identified with a binary string of length M excluding the zero string. Note this can get a little confusing, so I will restate some of our notation here. We are attempting to construct S which contains binary strings of length N, while the n-th bit in a given string (n runs from 1 to N) is identified with a binary number that is, at most, M digits long.

We will call any bit that happens to have an n value that is a power of two (that is, its binary representation has exactly one 1) a "parity bit". Any bit with n value that is not exactly a power of two (and has more than one 1 in its binary representation) will be called a "data bit". Note that there are M parity bits and N-M data bits, and we know |S|=2^(N-M).

Let the data bits run over all possible combinations, and let the parity bits be specified from the data bits as follows:

The parity bit corresponding to 2^L will be given the value of the parity of all the bits whose n value contains a 1 in their 2^L place.

Just to be specific, I should say that the parity of a list of bits is the value of XORing them together.

So, the first bit (with n=1=2⁰) is a parity bit, it checks the parity of any data bit that has odd n value (the numbers with a 1 in the 2⁰ place in their binary expansion).

The second bit (with n=2=2¹) is also a parity bit, it checks the parity of any data bit that have values such as 3,6,7,10,11,14,15...(the numbers with a 1 in the 2¹ place in their binary expansion).

The third bit is a data bit, its value runs over all possible values, as data bits do.

So, for the case N=7, the set S looks like

0000000
1101001
0101010
1000011
1001100
0100101
1100110
0001111
1110000
0011001
1011010
0110011
0111100
1010101
0010110
1111111

Note that bits 3,5,6,7 run over all possible values. Bit 1 checks the parity of bits 3,5,7. Bit 2 checks the parity of bits 3,6,7. Bit 4 checks the parity of bits 5,6,7.

Further note that every bit is being checked by a unique combination of at least two parity bits. Bit 5 is being checked by 4 and 1 (because 5 in binary is represented as 4+1) and only bit 5 is being checked by bits 4 and 1 alone. This idea will hold in general.

Now, we can specify an element of S uniquely just by giving its data bits (there are N-M data bits) and if we are given a binary string of length N, we can find an element of S that is different in no more than 1 spot through the following method: Find the element of S with the same data bits, it will differ in one or more parity bits. If it differs in one parity bit, we are done. If it differs in more than one parity bit, add of the n values of those parity bits to find a value j. You will find that if you flip data bit j, all of the parity bits will now be correct and you will have exactly an element of S. Thus you either differ in only one parity bit, or the incorrect parity bits specify what data bit is off from an element of S.

This gives us the general construction of the set S and completes the solution.

I am not sure if this is the most efficient solution, it might be possible to get a better solution using a Hamming distance of 2 for S rather than just 1. I suppose it is an interesting problem to try to construct those sets.

By the way, the elements of S are known as Hamming codes, and are very useful in coding theory.

Fun stuff

Sam And Ray

This last weekend, I was finally able to solve a logic problem that I learned some time ago over at the xkcd forums. Frequently when I tell people this problem, I manage to slur the words "Sam And Ray" into something sounding like "salmon ray" causing much confusion and hilarity for all.

Alright, the problem is:

Two players, Sam and Ray, will play a cooperative game. There is a list of zeros and ones, and Sam and Ray must simultaneously guess the next number in the list starting from the first one, they must guess either 0 or 1. They can see what the other one guessed, and what the correct answer was. If they are both correct, they win $1, if either or both of them are wrong, they lose $2. They may play as long as they like, the list of numbers is arbitrarily long.

Before the game, Sam will be given access to the complete list of numbers, he knows every correct answer. Before Sam is given the list, the two of them may meet up to strategize. Come up with a strategy that guarantees that they can win a positive amount of money before quitting.

Of course, one could ask you to make a strategy that wins, say, $100, but once you have a strategy that is guaranteed to get $1, you can just repeat it as many times as needed.

I'll post the solution later.

Kittens For All

OK, time to solve the hat problem from last time. So, first it is easiest to solve the two person, two hat colours case. When we have two people with only black or white hats, the solution is as follows:

Person 1: guess the hat colour you can see on person 2

Person 2: guess the hat colour opposite to the one you can see on person 1

More simply, person 1 assumes both hat colours are the same, person 2 assumes they are different, one of them will be correct.

Its also interesting to note that either individual has a 50% chance to be right (this is trivial since hat colours are independent), but there is no way both will be right. Thus, let event A be "person 1 is right", event B be "person 2 is right", so P(A)=1/2=P(B), and the probability that at least one of them is right is given by

P(A or B) = P(A) + P(B) - P(A and B) = 1 - P(A and B)

So we see that by minimizing P(A and B) to zero, we guarantee that one of them will be right.

This idea generalizes, in the seven person case, it is sufficient and necessary to find a solution that no two people can ever be correct at the same time, and you guarantee that one of them will be correct.

I will show the full solution using modular arithmetic. All math in the following solution will be done mod 7:

Number the hat colours 0 through 6, and number the people 0 through 6. There exists a number S which is the sum of everybodys hat colour (but none of the players have enough information to fully calculate S). Person n is to assume that the value of S is n, this gives them only one choice of hat colour to guess.

Each person assumes that the sum of the hats is a different number mod 7, and one of them will be right, also never will two of them be right.

This idea of making sure that no two people are right at the same time, so that you don't waste any extra "rightness" has uses in other logic problems, I'll probably point it out when it comes up or something.