Probably Counterfeit Masses

So, time for the final counterfeit masses problem. Usually I say where I first heard my puzzles from but I actually made this one up myself, with Matts help:

You have a balance scale and 41 coins. Most of the coins are identical but there might be a counterfeit among them. The only difference with a counterfeit coin is that it has a slightly different weight than other coins. One of the 41 coins is set aside, that coin is promised not to be counterfeit. You may use the balance scale to make 4 measurements, find an algorithm that is guaranteed to identify which coin (if any) is the counterfeit coin and if it is heavy or light.

So, its essentially the same as the more counterfeit masses problem in that you don't know if the counterfeit is heavy or light, but now you don't even know if it exists. To make up for it, you are given a single coin reserve. Apparently that is enough to cancel out not knowing if the coin exists.

Probably Too Hard

Alright, well the solution to the second counterfeit coin puzzle actually isn't too hard, I've just run out of clever titles.

Anyway, its a pretty neat solution:

1. Weigh 13 coins against 13 coins.

If they come out equal, then you have 3 weightings left, 14 unknown coins and a reserve of 26 coins you know are not counterfeit. That will be easy to solve:

2a. Weigh 9 unknown coins against 9 in the reserve.

If the 9 come out heavy (light), then you have two measuerments left and you know the coin is in those 9 and heavy (light), so we have already solved this problem. If the 9 come out even then we have a reserve of 35 coins and 5 unknown with 2 measurements left.

3a. Weigh 3 unknown against 3 from the reserve.

Again, if the 3 are heavy (light), then you have one measuerment left and you know the coin is in those 3 and heavy (light), again we have already solved this problem. Finally if they are equal then we have 1 measurement left and a reserve of 38 coins with 2 unknown coins. At this point the solution is trivial.

From the solution we have so far, it is easy to see the power of a large reserve of coins that are promised not to be counterfeit. Given an infinite reserve and N measurements, it is easy to construct a solution that works for (3^N+1)/2 unknown coins (the sum of the first N-1 powers of 3, plus 1). By contrast, when you are told that the coin is heavy, you get 3^N, so not knowing the relative weight of the coin approximately doubles how many coins you can solve for. This kind of makes sense, as you sort of eliminate half the hypothetical possibilites for the counterfeit coin.

Anyway, back to step one, suppose one side came out heavier, now you have a reserve of 14 coins and 13 "possibly heavy" coins and 13 "possibly light" coins:

2b. Weigh 9 of the possibly light coins with 4 of the possibly heavy coins against 4 of the possibly light coins with 9 of the reserve coins.

You have left behind 9 of the possibly heavy coins and have 2 measurements left. If measurement 2b comes out equal, then you know it is in those 9 and heavy, easy to solve. If the side with the 9 light coins comes out light, then only those 9 can be to blame (there were no possibly heavy coins on the other side) and so you know it is in those 9 and light.

In the last case to solve the side with the 9 light coins came out heavy, in that case it could have either been due to the 4 possibly heavy coins of the 4 possibly light coins. We have 2 measurements left and a reserve of 32 coins. Now our reserve is large enough that we can do a more brute force soltuion:

3b. Weigh 3 of the possibly heavy coins with 3 of the possibly light coins against 6 reserve coins.

If the coins come out heavy, we know it is in the 3 and heavy. If they come out light, we know it is in the 3 and light. We have one measurement left, so both these cases are easy. Finally if they come out even we only have 2 unknown coins left and a large reserve. We don't even need to make use of the fact that we know the coin is "either heavy and this one or light and that one".

Technically, this completes the solution. However, out of a matter of elegance it is worth pointing out that you do not need to make use of the "large reserve" when you do step 3b. You could also put 3 light with 1 heavy agaianst 1 light and 3 reserve and treat it like measurement 2b. This construction works in general, to weigh 3^N light and (3^N-1)/2 heavy against (3^N-1)/2 light and 3^N reserve. This happens because the sum of the first N-1 powers of 3 is (3^N-1)/2.

In general, this solution will solve (3^N-1)/2 unknown coins with N measurements. That is only 1 worse than the solution when you have an infinite reserve, so apparently a reserve isn't as powerful as I had stated earlier. Really having a reserve just makes the solution easier to access.

Alright, next time I will post the hardest version of this puzzle that I know (though truthfully it won't be that hard, now that you have seen this solution).

More Counterfeit Masses

Alright, as promised, I should post the harder version of the counterfeit masses problem now. I first learned this problem from Jen:

You have a balance scale and 40 coins. 39 of the coins are identical while the other one is a counterfeit. The only difference with a counterfeit coin is that it has a slightly different weight than other coins. You may only use the balance scale to make 4 measurements, find an algorithm that is guaranteed to identify the counterfeit coin.

The main difference here is that you do not know if the counterfeit coin is heavier or lighter, so when you make a measurement you only learn that the counterfeit coin is either "on the left and heavier" or "on the right and lighter", or things like that.

Of course, the rules for the balance scale are the same as for the original problem.

Probably Too Easy

Alright, I was going to post this earlier because the solution to the counterfeit masses problem is really easy, but then my weekend got really occupied.

So, the solution is as follows:

Split the 27 coins into 3 piles of 9. Weigh two of the piles against eachother, whichever is heavier has the counterfeit coin and if neither is heavier the coin is in the third pile. Next, split the 9 into 3 groups of 3, and weigh two of those against eachother to find which pile of 3 has the counterfeit coin. Finally weigh two of the coins in the final pile of 3 against eachother to find the coin.

Its really a simple trinary search, this problem will only trip people up if they try to do a binary search not realizing that you always gain information about the coins you don't weigh.

Its also easy to see (and prove by induction) that with N measurements you can solve the problem with 3^N coins. Also this solution is optimal, you cannot do more than 3^N coins with only N measurements (also provable by induction).

I'll post the more difficult problem later today.

Counterfeit Masses

So, a recent discussion with Simon caused me to remember an old puzzle I've been meaning to post for some time. There are multiple versions of this puzzle though, so I'm going to start off with the easiest one and move up. I don't know where I first learned this puzzle, I've known it since childhood:

You have a balance scale and 27 coins. 26 of the coins are identical while the other one is a counterfeit. The only difference with a counterfeit coin is that it is slightly heavier than other coins. You may only use the balance scale to make 3 measurements, find an algorithm that is guaranteed to identify the counterfeit coin.

Of course, the amount by which the counterfeit coin is heavier is imperceptible to a human, only a balance scale can tell. Using the balance scale to make a measurement can be visualized as follows: The scale has two places to put coins, you put as many coins as you like in each of those two places, then you push a button and the scale tells you which of the two places has more mass on it. The button will work 3 times and then the scale will break.

Improbable Masses

Alright, seems like its time to post the solution to the Impossible Masses problem.

First, there are two key realizations you need before you can solve the problem:

1. You may multiply the weights of all the masses by any constant and not have any effect on the puzzle
2. You may add any constant to the masses and not have any effect on the puzzle

The proofs of these are pretty simple, so I won't bother to do it.

So, first thing is that you use your power of a multiplicative constant to give all the masses integer mass (keep multiplying by denominators until you are there, basically). Next, you can use the additive constant to make one of the masses zero. Finally, you can halve all the masses as many times as it takes for there to be at least one weight with an odd mass (this step fails iff all the weights have the same mass). So, you have 11 integer masses and at least one of them is zero and at least one of them is odd.

Now, remove the zero mass, the remaining ten can be divided into two groups with the same (integer) mass. Thus, the total mass remaining must be an even number. Thus the total mass even with the zero mass included must be an even number.

Now, remove the odd mass, the remaining ten can be divided into two groups with the same (integer) mass. But, the total mass of the weights left behind must be an odd number. This is a contradiction, proving the masses must all be the same.

In the case where the masses can be real, I believe the proof goes along the same lines, but I do not actually know it myself.

Impossible Masses

Man, two weeks without posting, who's driving this thing? Anyway, time for a new puzzle. I first learned this one from the math room on KGS:

Consider you have a collection of 11 weights, each with a rational mass. This collection has the property that if you remove any one weight the remaining 10 can be sorted into two piles of 5 weights each, and each with the same total mass. Prove that this is impossible unless every one of the weights has the same mass.

By "a rational mass" I really mean that the ratio of any two of their masses is rational. It feels a bit weird to ask for a proof in a logic puzzle, but the proof is really quite elegant, and understandable without complicated math.

It can also be proven when the masses are real instead of rational, but it is much more abstract to do that.

Notation, Notation, Notation

So Matt always says that the key to all mathematics is good notation, with the solution to the improved blind man puzzle that is certainly the case. I began my solution to this problem by first trying to show that it can't be done, because lets face it, its clearly impossible. In trying to make my proof that its impossible correct I managed to improve my notation to the point where the solution was easy to find. Truthfully, the notation I use in this puzzle is not all that amazing, but it does help to clear out the needless junk that this puzzle carries with it.

So, first thing we need notation for the legal moves that the player can make. There are really only three possible moves. One is to choose two coins that are diagonally opposite and flip them both, we will call this move D (for "diagonal"). The next move is to take two coins that are adjacent to eachother and flip them both, I called this move H (for "horizontal"). The last move is to just flip a single coin, which coin is always irrelevant, because the spinning of the board will always result in you not having any control whatsoever on which coin gets flipped, this move is called S (for "single").

Alright, next we need to consider the possible board positions. I will name a board position with a number that corresponds to the maximum number of coins that have a common side up. So a position with three coins white side up and one coin black side up with be called position 3. A position with two coins on white and two on black will be called position 2. Position 4 is of course the goal. All positions of the name 3 are identical to the player, as white cannot be told from black in any way, and the exact location of the odd coin out can never be determined. The 2 positions do break into two distinct categories though, 2H will denote the position with two white coins that are adjacent to eachother and two black coins also adjacent to eachother. 2D will denote the position with two white coins diagonally opposite and the two black coins diagonally opposite.

Now, consider the effect that the 3 moves {D,H,S} have on the 3 non-winning positions {3,2H,2D}. D and H can only take position 3 to position 3, as D and H flip two coins each and so cannot change if there are an odd number of coins with black (or white) side up. So we will begin only using moves D and H to make sure we are not in any of positions {2D, 2H} and then we will solve the position 3 case after.

Move 1: D

This will have no effect on the board from position 2H (the only thing D can do to 2H is make it another 2H), and if the position was 2D, we now win. Of course, position 3 would be unchanged.

Move 2: H

This still does not change position 3, and it will turn position 2H into either position 4 or position 2D.

Move 3: D

If the board was in position 2D, we have now won. We have now totally ruled out any position 2D or 2H. If we have not won yet we must be in position 3.

Move 4: S

On position 3, S will make it either position 4 or one of positions 2D or 2H (which one is unknown). But now we know for a fact the board is not in position 3.

Moves 5-7: D,H,D

By the same logic as before, this will rule out position 2D, then change 2H into 2D, then lead to position 4.

This completes the solution. As before, I'm pretty convinced this solution is optimal, but I don't see a real proof of it.

Blind And Numb

Alright, so I have recently found a more difficult extension to the blind man puzzle:

There are four coins, each with a black side and a white side. The coins are arranged in a 2x2 pattern on a board. A blind man is going to play a game with these coins, he wins the game if at the end of one of his turns every coin has the same side up.

A turn consists of the man selecting any two coins, and he may then flip either or both of them. Coins may not be moved. After his turn he will be told if he has won. If he has not won yet, the board will be randomly rotated before his next turn.

Find a strategy that guarantees he can win within N turns, for some number N.

Its the exact same puzzle, except that you do not get to learn the status of the two holes that you choose. Of course it requires a few more moves, but its really interesting that you can still solve it.

Blind Man Winning

Time for the solution to the Blind man puzzle. The solution is actually fairly simple to explain, I don't even need pictures or anything. I'll explain it over a few steps.

First move: select two adjacent holes, fill them with pegs.
Second move: select two diagonally opposite holes, fill them with pegs.

Now there are at least 3 holes with pegs in them, as you could not have selected the same two holes twice there. At this point you have either won or the final hole is empty. If you have not won yet,

Third move: select two diagonally opposite holes, if one is empty, fill it and you win. If both are pegged, empty one of them.

Now you know that the board has two pegged holes adjacent to eachother, and two empty holes adjacent to eachother.

Fourth move: select two adjacent holes, if both are filled, empty them. If both are empty, fill them. If one is empty and one is full, switch them

Now you have either won by filling the empty holes or emptying the filled ones, or the board is in a configuration with two pegged holes that are diagonally opposite, and two empty holes that are diagonally opposite. Now you are set to win.

Fifth move: select two diagonally opposite holes, if they are empty fill them, if they are pegged empty them.

Now you win.

This strategy will solve the puzzle for N=5. I would be greatly surprised if there are solutions with less moves, but it is not clear at all the me how to prove it. If anybody out there has a better solution or a proof that there isn't one, feel free to post it in the comments.

Blind Man Walking

Time for a new puzzle I suppose. Though most people who read this blog have already heard this puzzle anyway, so whatever. Anyway, I first learned this puzzle somewhere randomly on the internets:

Consider a square wooden board with four holes drilled in it, arranged in a 2x2 square, with pegs available to fill the holes. A blind man is going to play a game on this board, he wins the game if at the end of one of his turns either every hole has a peg in it or no hole has a peg in it.

A turn consists of the man selecting any two holes, finding out their current status, and he may then change their status to anything he likes. His turn is then over. If he has won, he is now told so, if he has not won, the board will be randomly spun before his next turn.

Find a strategy that guarantees he can win within N turns, for some number N.

The bit about winning in N turns is just to rule out the random strategy, which would work eventually. You need a strategy that is guaranteed to work in a limited number of turns. Also by "randomly spun" I suppose it should be taken for given that the spins will be in multiples of 90 degrees.

Pascal's Modified Triangle

Well, time to post the solution to the coins in a bucket problem. First, just to get an idea of how I got to the solution, consider the answer in the case where the coins go into the bucket randomly, with 50/50 chance, rather than that weird weighted probability that was actually used in the problem. Let P(n,m) represent the probability that you arrive in the situation where there are n coins in the left bucket and m coins in the right bucket. P(1,1) is clearly 1. Next P(2,1) and P(1,2) are both easily found as 1/2. Then P(3,1) and P(1,3) are 1/4, since you must first get to (2,1) or (1,2) and then there is a 1/2 chance that the coin goes in the right place, while P(2,2) is 2/4, as the probabilities must sum to 1.

You basically wind up writing out Pascal's triangle, normalized so that the sum of the elements in any row comes out to 1. P(n,m) will be _n+m-2C_n-1/2^n+m-2. Each element of P(n,m) is the average of the two above it.

Now, in the case of the actual problem, we will still let P(n,m) denote the probability that you arrive in the situation where there are n coins in the left bucket and m coins in the right bucket. As before, P(n,m)=P(m,n), and the sum over all values of n and m such that n+m is held constant should be &Sigma P(n,m)=1.

So, as before P(1,1)=1 and P(2,1)=P(1,2)=1/2. Now, to get to (3,1) you must be at (2,1) and there is a 2/3 chance the coin goes in the right place. So P(3,1)=2/3*P(2,1)=1/3 also P(1,3)=1/3 by symmetry, and by normalization P(2,2)=1/3. Next, for (4,1), you must be first at (3,1) and then there is a 3/4 chance the coin falls into the right place, so P(4,1)=3/4*P(3,1)=1/4 and P(1,4)=1/4 so by normalization and symmetry we must also have P(3,2)=P(2,3)=1/4. So, our triangle has 1, then 1/2,1/2, then 1/3,1/3,1/3 and then 1/4,1/4,1/4,1/4.

Weird, it appears that P(n,m) depends only on n+m and not on the particular values. All distributions of n and m are equally likely across constant n+m. Let us try to prove the guess P(n,m)=1/(n+m-1). We know that this is true for n+m equal to any of {2,3,4}. P(n,m) must obey the relation:

P(n,m)=(n-1)/(n+m-1) P(n-1,m) + (m-1)/(n+m-1) P(n,m-1)

The first term is the chance you got to (n,m) by a coin falling into the left from (n-1,m) and the second is from a coin falling into the right from (n,m-1). Now we can prove our general formula for P(n,m) by induction on n+m. Assume it holds true for n+m=K, then for n+m=K+1

P(n,m)=(n-1)/(n+m-1)*1/(n+m-2) + (m-1)/(n+m-1)*1/(n+m-2)
P(n,m)=1/(m+n-1)

Alright, so for the 1000 coin case, the 999 differet cases (1,999), (2,998), (3,997),.....(998,2), (999,1) are all equally likely. So the bucket with less coins has any of {1,2,3,...499} coins with probability 2/999 and 500 coins with probability 1/999. The solution is then

2/999*&Sigma n +1/999*500
=(2/999)*(499*500/2)+500/999
=500^2/999
=250+250/999

Slightly more than 250. It would be 250.5 if not for the fact that 500 coins in the lesser bucket is slightly less likely.

Coins In A Bucket

Time for a random new puzzle. I managed to solve this one last week, its not very hard but has a really neat solution. I first learned this one from the forums on xkcd:

You have two buckets that you are throwing coins into. The probability that a coin goes into a particular bucket is proportional to the number of coins currently in that bucket. The buckets are initially seeded each with one coin. You have 1000 coins in total, and after you have thrown all of those coins into the buckets you look into the bucket which has fewer coins in it. On average, how many coins are in that bucket?

In particular, just so you understand the whole "probability that a coin goes into a particular bucket is proportional to the number of coins currently in that bucket" thing, if the two buckets have 5 and 2 coins in them currently, then the next coin will go into the bucket with 5 coins with probability 5/7 and the one with 2 coins with probability 2/7.

The solution itself isn't actually all that neat, but there is something about this situation that you find along the way that is really cool.

End Of The Line

So, its time for the solution to the Hats in a line problem. I've always like this problem, because when I first learned it I got lucky and managed to solve it in under an hour. Its not uncommon though to take a few days.

Anyway, the solution is easy enough:

Treat the hat colours as 0 or 1, the person at the back states the value you get by taking the XOR of the front 99 hats. The next person from the back can see the front 98 hats and knows the parity, so that is enough for them to be correct. The next person can see the front 97 hats and knows that the person second from the back was correct, and knows the parity of the first 99 hats, so that is enough information for them. It is easy to see that each person will be correct now except possibly the one at the back, who is 50/50 to survive.

Its not hard to see this is optimal, as the person at the back cannot possibly do better than 50/50 with zero information, and everybody else is 100%. Its also interesting to note that having on "idiot" in line will not kill everybody in front of them. They will be wrong, and they will screw up the person in front of them, but after that the two mistakes will cancel out. This is even true if the person at the back of the line is incorrect for some reason.

Hats In A Line

Alright, time for a new puzzle. I haven't put much thought into what puzzle I wanted to post next, so I guess I'll just go with one I have known for ages. Possible that most of my readership has already seen this also (all two of you), but I'm also just posting it for my own archiving purposes.

Anyway, I first learned this one from Bart:

There are 100 people in a line wearing hats. Each hat is either white or black, and each person can see all the hats in front of them, not their own hat or any hat behind them. Then, some disreputable men in black suits will come and ask each man a simple question: "What colour hat are you wearing?". They begin asking at the back and move forward in the line one person at a time. The people can only answer with "white" or "black". For each person, if that person is correct they are silently released, if that person is incorrect they are silently killed. Every person in front of them can hear their answer.

The people may get together and plan before the hats are assigned. What strategy guarantees the maximum number of people survive?

I would like to call the rule about seeing all the hats in front of you and none behind you "standard line hat rules", but theres only one other problem I know of that even uses that rule, and it involves the axiom of choice.

Duck In A Wolf

Seems like its time to solve the advanced Wolf and Duck problem now. First, we should set up some coordinates (because I don't want to go through the trouble of making pictures on blogger). We will set up polar coordinates in the pond, with R going from 0 to 1 (1 being the edge of the pond), and θ going from 0 to 2π. We know the duck can manage to get to a radius 1/v and be on the opposite side of the pond from the wolf (using previous strategies). Let us set up coordinates so the puzzle starts with the duck at θ=0, R=1/v and the wolf is at θ=π at R=1, of course.

Now, the duck will travel a small distance epsilon out to the edge of the pond, and the wolf must choose to go in the direction of increasing θ or decreasing θ. Let us assume the wolf goes in the direction of increasing θ. The duck will now head for the point of escape (assuming there is one) at R=1, θ=φ. There is little point in the wolf changing directions now, as the duck will have gained a small distance epsilon toward the edge again before the wolf just gets back to its original location. There is also little point in the duck taking any path more complicated than a straight line, as wherever the escape point is, the duck might as well go straight there.

The wolf must get to the position φ before the duck can. The wolf must travel a distance φ+π. The duck must travel the distance D, given by the cosine law as:

D² = 1+1/v²-2/v cos(φ)

Now, let f(φ) be the function representing the amount of time between when the duck gets to the escape point and the wolf gets to the escape point. Specifically, f(φ) = D-φ+π)/v. Maximizing f(φ) gives one:

sin(φ) = D

So this means that the duck will travel tangental to the circle of radius 1/v. When sin(φ)=D we know cos(φ)=1/v, if this isn't obvious, you should probably be drawing a picture to follow along, I certainly needed to.

The value of f(φ) when sin(φ)=D (and thus cos(φ)=1/v) can be given as sin(φ)-(φ+π)cos(φ). If we set that to zero (to find the situation when the duck no longer beats the wolf to the edge) we find that:

tan(φ)= φ+π

Which has a solution at φ≈1.35 . Thus, v=1/cos(φ)≈4.6 is when this strategy will fail for the duck.

As far as I can tell, when the wolf speed is greater than this value, the duck can do nothing to escape, but I have found no proof of this.

Wolf Near A Pond

Alright, the comments section seems to imply that at least one person has solved my Wolf and Duck problem, so I suppose I'll post the solution now:

The duck moves out to a circle 1/4 the radius of the full pond. At this radius, the duck has a faster angular velocity of the wolf, so the duck can go in a circle until the wolf is on the far side of the pond from the duck. At the point, the duck goes straight to the edge, as the duck can traverse the distance of 3/4 before the wolf can traverse the distance π .

Just a note because we don't all use the same browsers, π is supposed to render as pi. In Safari it looks really weird.

Alright, what is the maximum wolf speed for which this works? In general, if the wolf has speed v, the duck can go out the a distance 1/v and still have a greater angular velocity. The duck must then travel a distance 1-1/v before the wolf can travel a distance π . So, the duck requires that:

1-1/v < π/ v v < π+1

Thus, this strategy works until the wolf has speed π+1.

Next question:

Suppose we increase the speed of the wolf to 4.3 times the ducks speed, can the duck do any better? What is the maximum wolf speed for this new strategy?

I'll concede this isn't really a new question, but really it feels like one. The better strategy is alot harder to find and requires some more complicated math to prove it works and is optimal. However, I still promise that all shapes involved are simple geometrical shapes, lines and arcs of circles basically.

Duck In A Pond

Alright, been a full two weeks since I posted. I seem to be on the "new puzzle" part of my cycle, so I suppose I'll do one of those. This one looks a bit less mathy than my usual puzzles, but it really isn't. I first learned this one from Bart:

A duck is at the center of a circular pond with radius 1. A wolf is at the edge of the pond and is able to move around the circumference. The duck wins if it is able to get to the edge of the pond with no wolf there. Find a strategy that can guarantee the duck can escape to the circumference assuming that the wolf moves 3.5 times as fast as the duck.

For clarity, you can assume the duck is pointlike and the wolf has a small size epsilon (the wolfs size is needed to dodge weird solutions involving the duck touching an irrational point on the circumference and the wolf cannot access him). To qualify as a solution, it must work for some epsilon greater than zero. I will say that the proper solution involves no weird spirals or things, all shapes are simple geometrical objects that you can calculate lengths of easily.

There are a few follow-up questions to this one, I'll post one of them later, but for now:

What is the maximum speed of the wolf for which this strategy still works?

Hamming Hats

So, I hope everybody is ready for the solution to the hat problem from last time. Its a pretty good one, and combines a bunch of ideas I have set forward in previous puzzles.

First, one would like to solve a few cases with small N. The N=1 case is trivial, of course, you can't get better than 1/2 chance of success. Sadly, the two person case is similar, you cannot do anything better than 1/2 again. In the three person case however, we can do better with the following strategy:

For each person, guess black if both hats you see are white, guess white if both hats you see are black, and pass otherwise.

So, if the hats are white, white, black, then the black hat guy will guess correctly and the other two will pass. If the hats are white, white, white, then everybody will guess black and be wrong.

This is good, because we know that in a puzzle where one person being right is sufficient, then we don't want two people to be right at the same time. Also, in a puzzle where one person being wrong makes it all fail, we know that we should try to make it that everybody is wrong at the same time. Our solution will work unless everybody has the same hat colour, so the chance of success is 3/4.

So, in the case of general N now. We want that in any given situation, one person will guess correctly, or everybody will guess and be wrong. I honestly can't remember the logic I followed to get to the solution in the general case, but here is the solution in the N=7 case:

Treat a distribution of hats as a binary sequence of 7 digits, call it X. Each person knows all the bits except their own. Construct the Hamming set S of binary sequences of length 7. Each person is to look at the hats around, and if it is possible (based on the one missing bit) that X is an element of S, then make a guess assuming that X is not an element of S. If it is not possible X is an element of S, then pass.

If you have forgotten about Hamming codes, take a look at the sam and ray solution. So, since each string of length N is within one bitflip of an element of S, then unless X is an element of S, exactly one person will guess and they will be correct. If X is an element of S then everybody will guess and be wrong. The probability of failure is 2⁴/2⁷ which is 1/8.

If you have 10 people, say, then you just split 7 of them off and have them use that solution, have the other 3 always pass. In general with N people, split off M people so that they construct the largest Hamming set you can (it will be when M+1 is a power of 2) and have the remaining N-M people pass. The M people have a 1/(M+1) chance of failure, which will go to zero as M goes to infinity (and M goes to infinity as N goes to infinity, just taking a different path).

Hats, Hats, And Hats Some More

Time for a new problem I suppose. This one is going to be a bit weird, because as I understand it part of this is actually an open problem. The solution is only known in a few special cases, and so part of the problem will be to find how those cases fit in. Here we go:

There are N people in a room, each of them wearing hats. The hats can either be white or black, and standard hat rules will apply. At a specified time, each person simultaneously must either guess their own hat colour or pass. The players win the game if nobody guessed their hat colour incorrectly and somebody guessed correctly. They lose the game if either somebody was wrong, or everybody passed. The players are free to strategize before the hats are assigned. Find a strategy for the N player case such that in the limit as N goes to infinity, the probability of success goes to 1.

This problem as it is stated can be solved, its not an open problem really. Solving it in the N person case optimally is an open problem, so don't worry about that.

And We All Go Down Together

OK, I feel like distracting myself from work, so its time to post the full solution to the hats in a room puzzle. You must have already seen the hint I gave, so I will go from there.

The next case to solve is the four person case. The random strategy for that case gives a 1/16 chance of success, and the 'left-right' strategy gives 1/6. Doesn't seem like there is much room to improve, but lets try. First, let us name our people Adam, Betty, Candy, and Dale (I suppose I could give them numbers as names, but the hats will also need to be numbered, and it will make my explanation a bit less transparent). Suppose we plan to have Adam and Betty look under the two hats on the left, and Candy and Dale will look under the two hats to the right. Adam will look under hat 1 first, if he sees his own name, then all is well. If he sees Betty's name in that hat, then we are still OK. However, if he sees either Candy or Dale under that hat, then there is a problem.

If Adam knows that Candy's name is under hat 1, then he knows that the plan is going to fail unless he aborts. Whats more, he knows that the plan will fail anyway unless Candy also aborted. One way that Candy will abort is if she sees Adam's name under hat 3. If Candy sees Adam's name under hat 3, she will know that the default plan is doomed, and must abort. Thus, if Adam sees Candy's name under hat 1, he should look under hat 3 next. Out of some sort of symmetry, he might as well look under hat 4 if he sees Dale's name under hat 1.

At this point you can guess the strategy (actually, lots of people guess this strategy after the hint, but few are able to convince themselves it actually works). Adam will be assigned hat 1, Betty hat 2, Candy hat 3, and Dale hat 4. Look under your own hat, and whatever name you see, look under that persons hat next. What are the odds this works? Its is easy enough just to look at all 24 arrangements of the hats and see. I will denote an arrangement like Adam under hat 1, Dale under hat 2, Candy under hat 3, Betty under hat 4, with the letter sequence ADCB, and write S for success and F for fail.

ABCD - S
ABDC - S
ACBD - S
ACDB - F
ADBC - F
ADCB - S
BACD - S
BADC - S
BCAD - F
BCDA - F
BDAC - F
BDCA - F
CABD - F
CADB - F
CBAD - S
CBDA - F
CDAB - S
CDBA - F
DABC - F
DACB - F
DBAC - F
DBCA - S
DCAB - F
DCBA - S

So, 10 successes out of 24, thats better than the 'left-right' strategy of 6 successes out of 24 (actually, those successes are a subset of these ones). Okay, its not likely that we will do better than that, as its easy to show that no matter what the first person does, he cannot win with more than 1/2 chance, so at best we can approach 12 out of 24. Back to the 100 person case.

With 100 people the strategy generalizes simply, assign each of them a number and have each person look under the hat of their number. Then go to the hat corresponding to the name of the person you saw under that hat, repeat until you either see your own name or you have looked at 50 hats. There is no concern that you get sent back to your first hat, as only seeing your own name can do that.

Easy enough strategy, does it work? More simply, given the numbers 1 to 100 in a line (an element of the permutation group) what are the odds that there is no cycle of length 51 or more?

Alright, we know that in total there are 100! ways to arrange the numbers 1 to 100, how many of them contain a cycle of length 51 or more? Well, lets assume we wanted to construct a list with a cycle of length n (with n>50), then there are ₁₀₀C_n ways to choose those elements. Given those n elements to form a cycle, there are (n-1)! ways to arrange them into a cycle (because the first one can link to n-1 others, the second one to n-2 others and so on). Finally the remaining 100-n elements can be arranged (100-n)! ways (note there is no concern of the remaining elements forming a cycle of length n, as n>50).

We can see that the total number of ways to create a list of the numbers 1 to 100 that contains a cycle of length exactly n is:

T(n)=₁₀₀C_n*(n-1)!*(100-n)!
=100!*(n-1)!*(100-n)!/(n!(100-n)!)
=100!/n

Well, isn't that nice.

So the probability that there is a cycle of length n is

Σ T(n)/100!

Where the sum has n going from 51 to 100. The sum can easily be calculated on some math program, or you can approximate is as an integral if you believe that 100 is large enough (it is). Then it is the integral from y to 2y of 1/x dx, which is simply ln(2)≈ 0.69. That is the total probability of failure.

We can see that even in the case that the number of prisoners tends to infinity, the chance of success using this strategy will, at worst, be 1-ln(2)≈ 0.31. Thus they can expect to get out in just over 3 days.

As a side note, what are the odds that the first person expects to find his name when he first enters the room? He will not find his name if it is part of a cycle of length n with n>50. There are ₉₉C_n-1 ways to choose the other n-1 elements, and (n-1)! ways to arrange them into a cycle, and (100-n)! ways to arrange the remaining elements. Thus, we are interested in summing

₉₉C_n-1*(n-1)!*(100-n)!/100!

as n goes from 51 to 100. But that term is exactly 1/100, so after summing we will have 1/2.

As one would expect, the chance of the first person (or any individual, for that matter) finding their own name is 1/2. However, if that person is wrong, then there are at least 50 other people who are wrong with them. This is standard in problems where one person being wrong ruins everything. Make sure that nobody is ever wrong alone, they must take as many people with them as possible.

On the other hand, with problems where you only need one person to be right (such as with some of my earlier hat problems), you need to make sure they are always right alone, so you don't waste any extra "rightness".

Hints In A Room

So as a follow-up to my hats in a room puzzle, I'm going to be doing something unusual this time....I'm going to be giving a hint. This puzzle is particularly difficult, and even with this hint it still is quite a trick. Before giving the hint though, lets go through some of the logic that you have probably already gone through.

First of all, you need to see just how badly the random strategy fails. Each person has a 1/2 chance to select their correct hat if done randomly, so the chance that they all happen to be correct is 1/(2¹⁰⁰). Thats pretty bad. OK, next we try to solve the two person case and try to do better than 1/4 that the random strategy gives. Its clearly a waste of time for both people to look under the same hat, so we might as well agree that one person looks in the left one, and the other person in the right one. This gives a 1/2 chance of success, huzzah. Generalizing this back to the 100 person case, if 50 people look in the ones on the left and the other 50 look in the ones on the right, you have a 1/(₁₀₀C₅₀) chance of success. This is substantially better than 1/(2¹⁰⁰), but still nowhere close to being able to get out in a week. This is the best you can do without a key realization.

The realization that you need to come to is that you do not have to choose all of the hats you will look under right away, you can look under some of them and use that information to decide where to go next.

I'll finish the entire solution some time later this week.

Hats In A Room

So, I haven't been in town for a while, I've been away at the go congress. My performance there was average, but I'm happy with the games I played. Anyway, onto the new puzzle. I first learned this one from Bart:

There are 100 prisoners in a room (we shall call this room A) and the warden of these prisoners has decided to play a game with them. In another room (room B) there are 100 hats, and each one has the name of one of the prisoners underneath it (each prisoner has a unique name). A prisoner will be selected randomly and sent into room B. While in room B, the prisoner may look underneath 50 of the hats and then will be sent into another room (room C). Room B will then be restored to its initial state before a new prisoner is sent into it.

One by one, each prisoner will have a chance to look underneath 50 hats before being sent into room C. Once they are all in room C, they will all be released if each one of them has looked under the hat that contains their own name. If any of them has not looked under the hat that contains their own name, they will be sent to their cells for another night and the scenario will be run again tomorrow, with the names randomized underneath the hats each time.

The prisoners may plan while in room A. Come up with a strategy that, on average, will set them free in less than a week.

As I understand, Bart first learned this one at a talk entitled "Seven Problems You Swear You've Heard Incorrectly".

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.

More Hats

Alright, so for a blog entitled "Standard Hat Rules Apply", the standard hat rules sure haven't applied very much here, so it's time to remedy that. Here is a problem I first learned on the forums over at xkcd.

Consider a room of seven people around a table. They will each be assigned hats from seven different colours (ROYGBIV colours for definiteness, if you like). Hat colours may repeat, it is possible everybody will be given a blue hat or something. Standard hat rules will apply.

They must each simultaneously guess what their own hat colour is. If anybody is correct, everybody wins and are all given kittens. If everybody is incorrect they all lose and no kittens will be awarded, also the players will be killed. They may strategise before the hats are assigned. What is a strategy that guarantees victory (and thus kittens)?

Solution next time.

Ball Solutions

So, last time I introduced a ball problem, and I guess its time to show the solution. The solution is actually really simple, but I feel like doing a full-blown derivation.

First, let us define f(n,m) to be the solution to our problem, specifically it is how many black balls will be left if we started with n white and m black balls. We know f on the boundary cases:

1. f(0,m)=m
2. f(n,0)=0

To get the rest, consider that from a given position with n white balls and m black balls, we have a m/(n+m) chance to remove a black ball, and a n/(n+m) chance to remove a white ball. This means that:

f(n,m)=m/(n+m)*f(n,m-1)+n/(n+m)*f(n-1,m)

From here we can start to figure stuff out.

First, let us find f(1,m)

f(1,m)=m/(m+1)*f(1,m-1)+1/(m+1)*m
f(1,m)=m(m+1)*(f(1,m-1)+1)

From here, you can find f(1,1)=1/2, f(1,2)=1, f(1,3)=3/2 and guess f(1,m)=m/2. Alright, great, then a similar process on f(2,m) gives you that it is m/3, and this leads one to the general guess of f(n,m)=m/(n+1). Since it is already known to be true for the boundary cases, it suffices to show that when this formula holds for f(n-1,m) and f(n,m-1) it then holds for f(n,m). Something of a double induction:

f(n,m)=m/(n+m)*f(n,m-1)+n/(n+m)*f(n-1,m)
f(n,m)=m/(n+m)*(m-1)/(n+1)+n/(n+m)*m/n
f(n,m)=m/(n+m)*((m-1)/(n+1)+1)
f(n,m)=m/(n+m)*(m-1+n+1)/(n+1)=m/(n+1)

Yep, it works.

Actually, after the fact, you can intuit the answer in the limit of large m (does it still count as intuiting it after the fact?). If m is large, you can picture many black balls in a line, with a few white balls in the mix. If they are sorted randomly, and then taken from one end how many black balls will be after the last white ball? The white balls will evenly divide up the black balls into n+1 groups, and so at the end there will be m/(n+1) black balls.

Ball Problems

Man, I sure expected to post more often than once a week when I started this stupid thing. Eh, whatever, who reads this anyway? Anyway, time to introduce a new problem. I originally learned this problem somewhere randomly on the intertubes.

Consider you have a bag with n white balls and m black balls in it. You randomly pull balls out of the bag, one at a time, until you have drawn all the white balls. On average, how many black balls will be left when you stop?

Yeah, OK, thats all I got. Solution to follow later.

Some Days You Can't Lose

So, last week (man, I planned to write more often than this, but blogging is so hard) I wrote about the card flipping problem, and I guess its time to discuss the solution. First though, its probably best to discuss a common "solution" that does not work (well, actually it works, as we shall see, but its not the solution to the problem).

Attempted solution is as follows:

As soon as you have seen more black cards go by than red cards, say stop.

This looks like a good solution, as anytime you say stop you will have a greater than 1/2 chance to win. What exactly is the overall chance to win though? In the case of a 52 card deck, that is very hard to find, so lets try for a 4 card deck.

There are two separate cases where this strategy will say stop.

1. If the first card is black (1/2 chance), you say stop and win 2/3 of the time.

2. If the first card is red (1/2 chance), then you will only say stop if the next two cards are black (1/3 chance), but then you are guaranteed to win.

So far, you win (1/2*2/3+1/2*1/3)=1/2 of the times that you say stop.

OK, what about when you do not say stop? If you reach the end of the deck and have not seen more black cards than red, then you are in trouble, the last card of the deck is guaranteed to be black.

This summarizes the problem that you meet in the 52 card deck. Many games you will say stop at some point and you have a slightly better than 1/2 chance to win, but there will be the occasional game where you do not say stop and you are certain to lose. In the end you come out 50% no matter what.

OK, could you do better? No, as it turns out. The argument can be made with a few simple points:

1. When you say stop, it wouldn't matter if I were to shuffle the deck before that last flip.
2. When you say stop, if instead I just picked a face-down card in the deck from my choosing, it wouldn't change anything
3. When you say stop, I could just deal the next card from the bottom of the deck.

(This argument can be put more succinctly, but I find this method more convincing). So now we have a different game. I will deal cards off the deck until you tell me to stop. When you do so I will show the bottom card of the deck, if it is red you win, if it is black you lose. What is the optimal strategy for this game?

Its pretty easy to see this game is 50-50 no matter what you do. Even if you were trying to lose you couldn't do more than 1/2 the time (of course, in this game trying to win is equivalent to trying to lose the other way). Naturally, at any given moment when you tell me to stop, you might be better or worse than 1/2 (in particular, if you wait until the last card, then you are either 0 or 1), but for anything you try to do, you were 50-50 from the first card.

This realization that sometimes the order doesn't matter for random events can be very useful, and I will probably refer back to it from time to time (though, I can honestly only think of one major instance that I have used it in logic problems).

I have also used this idea in boardgames. In 1960: The Making of the President, there is a point in the game where you draw 3 cubes from a bag to determine the outcome of events. If at least 2 of the cubes come up your colour, then you win the event, but if at least 2 of them come up the opponents colour, then you lose it, either way, the cubes do not get returned to the bag. Not all the events are equal, and you can choose what order they happen in.

Some would argue something about wanting to do the less important event first, so if the opponents cubes come out, you have more of your cubes in the bag for the better event, and I'm sure one could also make some argument for doing the more important event first as well. However, its not hard to show that there is no optimal strategy here. Naturally, if you do the weaker event first and a bunch of your own cubes come out, you will be upset, but a priori all strategies had been the same.

Card Flipping

Alright, just to post because I haven't done so in a few days, I'll introduce a new problem. I first learned this problem (as with so many of my puzzles) from Bart:

I hold a deck of 52 cards, 26 of them are red, and the other 26 are black. I will flip cards face up off the deck one at a time until you tell me to stop. When you stop me, I will then flip one more card, if that card is black you lose the game, if it is red you win the game. You are required to stop me before I flip the last card of the deck. What is the optimal strategy to win this game?

As is my standard method, I'll post the solution next time.

Monty Hall Problem

I would imagine most people who would bother reading a blog like this are very familiar with the Monty Hall problem. Of course, in the interest of completeness, I'm going to state the problem here:

You are on a game show where you must choose between three doors. Behind one door is a prize, and the other two doors have nothing behind them. After you select a door the show host, Monty, will open one of the doors that has nothing behind it. Monty, of course, knows exactly where the prize is and is always able to select such a door. You are then given the option to select a new door. What is the optimal strategy to select the door with the prize?

Given a bit of analysis, its not too hard to determine the optimal solution, though some people have a hard time wrapping their minds around it. However, opponents of the standard solution often point out an unstated assumption, and that is that Monty will always offer you the choice to switch. If Monty gets paid based on contestants not finding the prize, then perhaps Monty would rather only offer the switch to contestants who correctly guessed the prize door. In this case, it is clear to see that you should never switch. Of course, perhaps Monty will occasionally offer the switch to a contestant who is wrong, just to mess things up a bit.

After thinking about this, I came up with a extension problem to work out:

Suppose Monty will offer the switch with probability x to a contestant who picked the right door, and will offer the switch with probability y to a contestant who picked the wrong door. Assuming the contestant watches the show frequently enough to determine the values of x and y, what is the optimal solution for the contestant? What are the optimal values of x and y for Monty?

If you feel like working this out yourself, I encourage it. Its not a particularly hard problem, and the answer is very intuitive.

Anyway, I'm going to post the answer here now.

Suppose the contestant decides he will accept the switch with probability c. c cannot depend on the contestant getting the right door, as the contestant doesn't know, however, c can depend on x and y.

The probability the contestant wins is given by the sum of two terms. First, the probability they got the wrong door (2/3), times the probability of being offered the switch (y), times the probability they accepted the switch (c). The second term is in two pieces, the probability they got the right door (1/3) times the probability they were not offered the switch (1-x), and the probability they got the right door (1/3), were offered the switch (x), and refused it (1-c).

Adding it up, the probability the contestant wins is given by:

P=1/3(2yc+(1-x)+x(1-c))

P=c/3(2y-x)+1/3

Since this is just a linear function of c, it will be maximized at the endpoints, either c=0 or c=1, depending on if 2y-x is positive. If Monty offers "good switches" (y) more than half as often as he offers "bad switches" (x), then you should switch, otherwise don't. If 2y-x=0, then either switch or do not, it doesn't matter.

The optimal solution for Monty is to make sure 2y-x is not positive, because he has no way to reduce P less than 1/3 (the contestant can always choose c=0), but if 2y-x is positive then P will be greater than 1/3 with c>0.

Finally, note that in the original case, if Monty always offers the switch then x=y=1, and the optimal solution is to switch. c=1 gives that P=2/3, whereas never switching gives P=1/3. So this method also solves the original Monty Hall problem.

Logical And Wrong

So, continuing my last post about monks with eyes, (though I should start calling them islanders now), if everybody assumes that their eye colour is one they have seen before, then they actually can figure out stuff fairly quickly. Its interesting to see what happens if that information is wrong though.

For example, assume there is 1 blue-eyed person and 3 brown-eyed people. The blue-eyed one will have to assume his eyes are brown and leave that night, and the brown eyed people will figure out it the next night and leave. Of course, the blue-eyed person will leave because he thought he figured out his eyes were brown and he is just wrong, but thats what happens when perfectly logical people are told the wrong information.

Continuing upward, if there is 3 blue and 2 brown, the 2 brown leave on the second night and the blue leave on the third night, its easy to see this because a brown eyed person will assume his eyes are either brown or blue.

Next, assuming there is 1 green, 2 blue, and 2 brown, the green-eyed person will assume his eyes are either blue or brown. If his eyes are blue, the brown eyed people will leave on the second night and vice-versa for brown. When the second night comes and nobody leaves, the green eyed person must realize a contradiction.

At this point, you can't really guess what happens next, when perfectly logical people see a contradiction they might come to second guess everything, so we really have no choice to declare there is a contradiction and end there. As a side note, the blue and brown eyed people all know that somebody has seen a contradiction, but they cannot figure out who knows it.

After seeing this, I came to a conjecture:

Either somebody will realize there is a contradiction and nobody leaves, or everybody will eventually leave the island.

Its not hard to justify this, as if anybody leaves, then everybody else gains a big piece of information, but if a contradiction is seen and somebody doesn't leave in time, then nobody can gain that information (unless, I suppose, if the person who found the contradiction is allowed to announce it).

Last neat thing I want to say about this puzzle is what happens if you give the assumption that no person has a unique eye colour. This is slightly different than the assumption that each person has an eye colour they have seen before (in spite of the fact that both are true under the same circumstances, which still sort of confuses me a tiny bit, to be honest).

In this case, with 2 brown and 2 green, they all leave on the first night, seeing that they all can see an eye colour that only one other person has. And with 1 blue, 3 brown, and 3 green, the brown and green will assume their eyes are blue the first night, and will all leave, and the blue guy will simply be left asking where everybody went. It appears my conjecture does not hold here anymore.

Alright, I'm done with that class of monk problems (for now). I'll start something new next time.

Monks With Eyes

So, given that nobody is actually reading this blog yet, its not 100% clear why I would wait for a day to post the solution to my monks with hats problem. Really, the reason is that I am worried that I only have a finite amount of blogging material, and I really don't want to waste it right away. As a general warning, there are spoilers ahead, so if you actually wanted to solve that problem yourself (and you know you want to), now would be the time to stop reading this.

Alright, to solution is simply that after 25 nights, the white hatted monks all kill themselves, and after 26 nights, the black hatted monks do. This can be most easily seen by considering a case where there is one monk of each hat colour, then moving up to two, and so on upwards until you are ready to prove by induction. Of course, no matter how much you think about it at first, pretty much anybody spends a long time being tripped up by this puzzle before they really come to accept it.

It is quite interesting to ponder what exactly it was that the rabbi told the monks that they did not already know, and if you can answer that, you will probably be more at peace with the answer (at least thats how I got to be).

An variation of this puzzle, which I first learned from xkcd, is that there is are a bunch of islanders who must leave the island at midnight if they learn their own eye colour. Suppose the island has 50 people with blue eyes, and 50 people with brown eyes. Then one day somebody comes along and points out that at least one of them has blue eyes.

Clearly this problem is the same as the monks with hats problem, so 50 nights later the blue-eyed islanders leave, followed the next night by all the brown eyed ones.

"But wait", the more pedantic of you will say, "there is no limitation on eye colour to be blue or brown, any of the brown eyed people can just assume they have green eyes and all is well." You would, of course, be quite right to say this, and so one can come up with a neat variation of the puzzle by adding one more assumption.

All of the islanders will assume that their eye colour is an eye colour that they have seen somebody else on the island have. Specifically, if you have only ever seen blue eyes or brown eyes, you will assume that you must have either blue eyes or brown eyes. Also, it is common knowledge that everybody will operate under this assumption.

As I was thinking about this one day though, I realized that something funny can now happen. If there is 50 blue-eyed people and only 2 brown-eyed people, then the brown-eyed people will say "If I have blue eyes, then that brown-eyed fellow will assume his eyes must be blue and leave tonight." Then of course when he stays, both brown eyed people will figure out their eye colour and leave that night. The next night the blue-eyed people will figure out that the only way the brown eyed pair figured it out would be if they had blue eyes, and so they all leave the third night.

Turns out nobody had to come along and give these islanders extra information, they will leave all by themselves. I suppose this problem is not quite as well posed at the other one, but there are some funny things that can happen with it. More about that next time.

Monks With Hats

Usually, after solving a logic problem, I like to take some sort of generalization of it just to complicate the issue. A typical example of that is to take a problem that only applies to natural numbers and solve it assuming its parameters can take on real values. This process isn't always very well defined, but I am usually pleased with the result anyway. Before I can start that though, I suppose I'll introduce the logic problem that triggered me to actually start this blog. I first learned this problem from Bart.

Consider a monastery with many hat-wearing monks in it. The hats can be either white or black, and the monks have taken vows not to look at their own hat or point out others hats or stuff like that (standard hat rules apply). Further, the monks have taken a vow that any monk who discovers their own hat colour is to kill themselves at midnight that night. When a monk dies this way, all the other monks are aware of it the next day. Finally, all the monks are perfectly logical and are all aware of all information in this paragraph.

Let us assume for definiteness that there are 50 monks, 25 with black hats and 25 with white hats. One day a rabbi, who does not particularly like these crazy hat-wearing monks, comes by to speak with the monks. He gathers all the monks together and announces to them, "I see that at least one of you is wearing a white hat today." The rabbi then leaves the monastery, what is the fate of the monks?

If you think the answer is "they happily live out many years of life", I should tell you the easier version of the problem where I end off the problem by saying this: Two months later the rabbi returns to the monastery, and all the monks are dead. On which day did the monks die (specifically, for each monk, on which day did that monk die)?

I won't state the solution in this post, just because some people might not want it spoiled for them, so I'll give it a day before making the next post.

Who Blogs These Days?

Apparently, these days anybody can be tricked into starting a blog, even me. One has to wonder what percentage of blogs actually get read by people outside of the bloggers circle of friends, but I suppose thats no reason to not blog. The main advantage of blogging is that you don't have to notice just how much people do not want to hear your random ramblings on things. If somebody doesn't care about what you write, they just stop reading, and you just keep writing anyway.

I suppose for my first real post though, I might as well explain what the title is about, just in the off chance that people outside of my circle of friends do actually read this thing. Simply put, I spend far too much of my time working on logic puzzles that begin with something like, "Seven people are in a room, and they are all wearing hats of various colours. Each person can see eachothers hats, but they cannot see their own through any means, nor can they communicate their hat colours to eachother in any way," but because so many problems involving hats have that last bit about not being able to see your own hat, but being able to see all the other hats, it helps to shorten that to just saying "Standard hat rules apply."

Yep, thats all I got.