Domino Marriage

About time to post the solution for the covering problem from last time. I though I had come up with a good way to post pictures in blogger, but I apparently forgot what it was, so I don't think I'll bother, the solution is easy enough to describe anyway.

Picture a horizontal line of four squares, numbered 1,2,3,4. Add a square we will call 5 above square 2, and a square we will call 6 below square 3.

It is clear this cannot be tiled, as both 1 and 5 only touch 2 (as well as 4 and 6 only touching 3), but if we add a 2x1 block below 1 and 2, this gives a new option for 1 and 6 to connect, and the tiling works.

Easy enough solution, and it got me thinking, is there an easy way we can check when a tiling is possible or impossible? The general problem is that we have two equally sized groups of things (in this case white and black squares) and you want to have a 1-1 matching between group 1 and group 2, but there are restrictions on what may match with what. In my solution example, we have squares 1,3,5 in group 1 and 2,4,6 in group 2. 1 and 5 may match to 2, and 3 may match to any of 2,4,6. Clearly in this case a matching is impossible, since we will not be able to match different things to 1 and 5, also on the other side we won't be able to match 4 and 6.

We can see a necessary condition here:

For each subset S of group 1, the set of things that subset can match with needs to have at least as many elements as S.

So in our example, the set S can be {1,5} and the set of things they match to is {2} and so it violates this condition. Of course, I could have put group 2 instead of group 1, but as it turns out I don't need to, as we will see.

I spent some time wondering if it was possible to satisfy this condition and still not have a possible matching, but I wasn't able to find anything, I started to suspect that this condition was not just necessary, but also sufficient. Then somebody pointed me to the Hall marriage theorem which proves that this statement is in fact sufficient, and also having this statement proves the equivalent statement on group 2.

Anyway, neat stuff, and a new theorem I didn't know. Thats all for now.

Covering Solution

Alright, I'm pretty sure I still have this blog, and now I have something of a backlog of puzzles to post. Something of an embarrassment of riches that I don't bother to post as often as I learn new puzzles, but thats life I guess. Anyway, time for the solution to the domino problem from last time.

The solution is very simple: Consider naming the squares on the chessboard black and white, with no two of the same colour adjacent (the way chessboards are actually coloured). A given domino must cover exactly 1 white and 1 black square. The standard chessboard has 32 squares of each colour, but opposite corners are always the same colour so removing two of opposite corners will leave us with 32 squares of one colour and 30 of the other. It will not be possible to cover this with 31 dominoes.

Thats it really, I'll follow this with a post about the follow up problem.

Josephus Solution

Time for the solution to the Josephus problem from last time. As is common for problems that are basically induction puzzles, its easiest to see what is going on by looking at a few cases.

First of all, you can just work through who wins in the cases N=1,2,3,4,5,6,7,8 and so on, you will see that the winners are 1,1,3,1,3,5,7,1. A bit of an interesting note is that all the winners are odd numbers, of course this note is instantly less interesting when you realize that all the even numbered individuals are killed on the first pass. Actually, if N is even, that brings up a good point, specifically that for N=2K you immediately reduce to the problem with K people, with #1 going first and a bit of a renumbering that person 2m-1 is now person m. But if this new K also happens to be even, then you can half it again. From here you can see that if the initial N is some power of 2, then person #1 will be the last one standing.

At this point, we can realize that whoevers turn it is when the total number of people is a power of two is the person who is going to win. Naturally, if the total is an even number, then that is person #1, but if N is equal to 2^k+M, for some M less than 2^k (or we would just use k+1 in the power instead), then once M people die, the next person on turn will live. Clearly since M is less than half of N, those first M people will die on the first pass around the table, so when M people have died it is the turn of person #2M+1.

This gives us the general solution for an arbitrary N. Let 2^k be the largest power of 2 less than or equal to N, and let M=N-2^k. The final person standing will be person #2M+1.

Then a year passed

Alright, that was a good year of not blogging, but I'm back, for today, who knows for how long. Anyway, time to post the solution to the funny Knights and Knaves puzzle from last time.

First, I will refer to each person at the party by naming them with the number of truth tellers they claim to have shaken hands with. Now, you can determine right away that person 99 must be a liar, as if he did shake hands with 99 truth tellers then everybody would be a truth teller, including the individual who claims to have shaken hands with nobody. This is a contradiction, so person 99 is a liar. One can continue this down by looking at person 98 next. Since 99 is a liar, in order for 98 to be telling they truth, everybody else must be a truth teller, but this agian would make person 0 a liar, since 98 shook hands with everybody (except possibly 99) in this assumption. So 98 is also a liar.

This logic continues down, making all individuals who claim to have shaken hands with a positive number of truth tellers liars. This leaves only person 0 as a possible truth teller. As there were no other truth tellers at the party, it is certian that person 0 shook hands with no truth tellers, thus person 0 is in fact a truth teller. This gives the answer to the puzzle as 1, there is only 1 truth teller at the party.

Somebody had pointed out to me that there is a silly solution that works out, since the answer is independent of the knowledge of who shook hands with who, it is possible there were no handshakes. In that case person 0 is telling the truth, and everybody else is a liar. This has no contradictions and must be a possible solution, so if there is actually a solution to the puzzle, then the solution must be 1. I'm always reluctant to actually use this sort of solution, as it feels like something of a hack to assume a solution exists and then go from there, but it does often work to use this trick.

Pascals Cube

Well, summer has now mostly gone by with no posts from me on that puzzle about the cube of resistors, so I guess I'll solve it now.

The thing to do for the initial puzzle in three dimensions is conisder the eight vertices of the cube and apply a potential difference of V between one vertex and the opposite corner. We could then find the current and the ratio would give us the resistance. The trick is then to notice that the three vertices that are one edge away from the starting vertex are an equpotential, so they can be fused into a single vertex. Then notice that the three vertices that are adjacent to the final vertex are also an equipotential. We then have only 4 vertices, the first is connected to the second by 3 resistors, the second connected to the third by 6 resistors (takes a bit of work to confirm that 6) and the third is connected to the fourth by 3 resistors. Since M 1-Ohm resistors in parallel have an effective resistance of 1/M, the equivalent resistance of this is 1/3+1/6+1/3=5/6

OK, thats fun, and should generalize pretty fast, but we need to see exactly how. In N dimensions, each vertex can be represented as a series of N zeros and ones, and this is a complete list of the 2^N vertices, each vertex is connected to the N vertices next to it, so any vertex has N edges on it. So N edges lead out from the initial vertex to the first equipotential. Next, the N vertices have 1 edge leading backward, and N-1 leading forward, so there are a total of N*(N-1) edges leading to the next equipotential (This is N*_N-1C₁). The next _NC₂ vertices each have N*(N-1)/_NC₂ (which is 2) edges from beind them, so there are N-2 going forward. This means there are a total of N(N-1)/2*(N-2) vertices going forward (this is N*_N-1C₂. As you can guess, the number of vertices going forward is always N*_N-1C_k, with k going from 0 to N-1.

So, in order to find the total resistance, we simply need to add up 1/N*_N-1C_k, which is 1/N times the sum of the recriprocials of the N^th row of Pascal's triangle. This doesn't really have much of a closed form, but its enough to let you figure out the specific number for any particular value of N. There is a bit of a question left of the infinite limit, and fortunately Ben found a paper called "Sum of the reciprocals of the binomial coefficients", which should be easy enough to find if you are interested, the main point here though is that the limit of the sum at large N is 2, therefore the effective resistance is 2/N. Not much of an answer I guess, but I'm always happy when Pascal's triangle shows up.

Partitioning

So, I have a few new puzzles in the bank now, so I need to get to blogging again to spend them. I guess I need to start with my solution to the number puzzle from last time.

So, we have a list of numbers L, with n elements, whose sum is S, and the sum is known to both people. Further, they have a product P and if you knew P, n, and S, the list is not uniquely specified. We want to find the list that has these properties with the smallest S possible. We are looking for two lists I will call L₁ and L₂.

Its easy to see that L must have more than 2 numbers, since if you adjust two numbers and keep their sum the same, the product must get larger for the list that has the numbers closer together (you maximize the area of a rectangle by making it more square). So the list will need at least 3 numbers. Further, if L₁ and L₂ have any numbers in common, we may as well delete the common numbers from both lists, as they will still have equal total sums and products after common numbers are deleted.

At the point it is basically a matter of playing around, the first solution I found was {2,2,10} and {1,5,8}, which was just playing around with the possible prime factorizations of numbers that seems like good canditates. I was quite certian this was the smallest solution, I am quite sure (but less than 100% sure) that there are no solutions with n=3 that have a smaller S, and I had assumed there wouldn't be a smaller S that used larger n, but then Ben told me he had a solution with S=12, so I had to go looking. Eventually I found it as {2,2,2,6} and {1,3,4,4}. Ben says he has proved with a computer that there are no smaller S solutions, but I am interested if there are any solutions out there with a smaller P, however I doubt it.

Anyway, thats all I got here.

Order or Not

Solution time?? Solution time. Puzzle last time was the one about magical balloons. The solution is far from unique, but here is the one I found:

Step 1: Name the balloons 1,2,3,4, measure 1 and 2 in the machine. If the machine tells you that either zero or two of them are magical, you can just test the other two balloons one at a time using your remaining two measurements. So proceed assuming we got a result of one.

Step 2: Test 2 and 3 in the machine. If the result is zero, you know 1 is magical and you can test 4 alone. If the result is two, you know 1 isn't magical and agian you can test 4 alone. If the result is one, then either 1 and 3 are both magical and 2 is not, or 2 is and 1 and 3 are not.

Step 3: Test 1, 3, 4 together in the machine. The result being odd will point at 4 being magical, while being even will indicate 4 is not magical. The result being two or three will mean 1 and 3 are magical and 2 is not, while the result being zero or one will mean 1 and 3 are not magical and 2 is.

One flaw that I didn't like about this strategy is that it isn't memoryless, the tests I intend to do each step depends on the results of previous steps, and you can come up with memoryless strategies. However, if you look at the last path of my strategy: Test 1&2, then 2&3, then 1&3&4, that will work to be a memoryless strategy, you just have to analyise your results when you are done. I do not know of any strategy that is totally memoryless, that is, one that there is no path through it that you couldn't have just used from the start as a memoryless strategy.

Other things I don't know about this puzzle: how the heck to generalize it to N balloons and K measurements, so thats a thing to work on.

Box Box Box Box

I wonder if I will ever get back to something like weekly blogging instead of monthly. Anyway, time to do the solution to the box puzzle from last time.

First, we might as well use numbers instead of colours, because thats the sort of people we are. Let the colours be called 0, 1, and 2. In this case, "all three the same" and "all three different" is the same as "the three add to 0 mod 3".

This means the top box is negative the sum of the two boxes in the second row. The second row left box is negative the sum of the two left boxes in the third row, and the second row right box is negative the sum of the two right boxes in the third row, meaning that the top box is made up from the third row by adding the first box + 2*the second box + the third box. We can see quickly that Pascals triangle and the occasional minus sign is all we need.

The 9th row of Pascals triangle (calling the top row zero, which I do) is 1,9,36,84,126,126,84,36,9,1, so add the boxes on the bottom row with these coefficents mod 3 to get the box on the top. As it turns out, 9, 36, 84, and 126 are all multiples of 3, so they don't even matter, only the two end boxes contribute at all. Finally, there is a minus sign, as every other row gets one.

Thus the solution is, if the bottom two end boxes are the same colour, then the box on top will be that colour, if they are different colours, the box on top will be the third colour.

Most of The Time

Time to solve out the hat problem from last time. There are probably a reasonable number of forms of the solution, but I suspect that they are all equivalent to the one I am about to give.

First of all, consider one of the three people (I will name this person Bob), he must have some strategy on when to guess and when to pass. Guessing all the time or passing all the time must each be non-optimal, since any guess has only a 1/3 chance of being right, you want to ensure that your guesses line up with your partners guesses in such a way that you are all wrong together, but you are right alone. Clearly the only trigger on when to guess must be the other players hat colours, so let us assume that Bob will guess when we see that the other two hat colours are the same, and he might as well guess that his hat is of the same colour (this is possibly not the most general solution, but I think most other forms of guessing for the first person can be mapped onto this isomorphically).

Bob will assume that the three hat colours are the same, and if that is not possible, he will pass.

Next, consider Alice, she will look at the hats that Bob and Eve are wearing (I'll just name people on the fly now). Bob will guess if Alice and Eve share a hat colour and in that case he will be guessing right or wrong and Alice can do nothing about it. So Alice may as well assume her hat colour is different from that of Eve, since if it is the same Bob is going to be guessing anyway. A reasonable guess for Alice is to guess her hat colour is the same as Bobs, unless Bob and Eve have the same hat colour in which case she should pass. In this way, she will sometime guess correctly, but will never guess correctly at the same time that Bob does it (and we know from similar problems that we want people to guess wrong together but correct alone).

If Alice sees that Bob and Eve have the same hat colour she will pass, otherwise she will guess the same as Bobs hat colour.

Eve might as well obey the same strategy as Alice, just to cover the case where Eve and Bob actually do share a hat colour and Alice does not.

If Eve sees that Bob and Alice have the same hat colour she will pass, otherwise she will guess the same as Bobs hat colour.

Looking over this, we can see that the players will win if somebody shares a hat colour with Bob, and will lose if nobody does. One can see that the probability of winning is then 5/9, or 15 of the 27 cases.

For a theoretical upper bound, imagine the possible space of hat distributions as some continuous region (I chose to imagine a disc). In that region, each person can choose a part of it for where their strategy will call for them to guess, and in that part they will guess correctly 1/3 of the time and incorrectly 2/3 of the time. So, take some region and colour it 1/3 green and 2/3 red.

Now take another region, which may have some overlap with the first region, you must also colour this one 1/3 green and 2/3 red, but if some part is coloured both green and red, it stays red (a right guess and a wrong guess is a loss). Clearly if we want more green and less red, it is best to have exactly the red parts overlap and the green parts be distinct. Finally we take a third region and colour it 1/3 green and 2/3 red. Any regions left uncoloured at this point are red (since if nobody guesses we lose).

If we have done this optimally we have 3/5 green and 2/5 red, since each person had one part green to two parts red, but they can all use the same red, there are three green parts at most. So theoretically the players can win at most 3/5 of the time, this comes out to 16.2 of the 27 cases, so 16 at best. We can see that our solution is slightly short of this theoretical optimal.

Ben has given me an argument for why 16 is not actually attinable, basically by just breaking down possible strategies, but its not particularily interesting to give here, so I won't bother with it, unless somebody really wants me to.

All Lined Up

A month between posts, thats about right. I guess I should post more frequently for the next little while, as I have learned a few new puzzles from Ben as of late, but we will see if that actually gets me to post more.

Anyway, time for the solution to the lineup puzzle that I posted last time.

So, its not hard to work out what the solution is for a few simple N, but it might be a bit tricky to see what the pattern is if you don't recognise it. For some small N values, the solution F(N) is given by:

F(1)=1
F(2)=3/2
F(3)=11/6
F(4)=25/12
F(5)=137/60

Gets sort of ugly, but if you take the differences:

F(2)-F(1)=1/2
F(3)-F(2)=1/3
F(4)-F(3)=1/4
F(5)-F(4)=1/5

The solution being the sum of 1/k from 1 to N seems like the obvious solution. You can go ahead and prove it by induction if you like, but there is a much cleaner solution.

Consider the people enter the lineup into random positions, starting with the tallest person. You can see the tallest person with probability 1, and shorter people added to the lineup cannot change that. You can see the second tallest person with probability 1/2, and shorter people added to the line cannot change that, you can see the k^th tallest person with proably 1/k, and shorter people added to the lineup cannot change that. This gives the solution of the sum of 1/k (also known as the harmonic numbers).

Spinning Robots

Ok, that was quite the break from blogging. Time to solve out the robot chasing puzzle I put up last time.

First of all, it is easiest to work in polar coordinates, r and θ, the robot starts at r=0 and moves along θ=θ₀ and you start at r=r₀ and θ=0 The robots path given

r(t) = v_rt
θ(t) = θ₀

We get to pick our r(t) and θ(t) and choose a path such that we will meet up with the robot path for any arbitrary value of θ₀.

First of all, we might as well move straight to the robot, assuming that θ₀ is 0. We move toward r=0 and would meet the robot at r=r₀*(v_r/(v_p+v_r)) This value, which I will call R, will be our effective starting point.

Next, we must move outward in a spiral, such that our r(t) continues to match the robot r(t), but our value of θ takes on all values between 0 and 2π. This is simple enough, find r(t) and θ(t) such that:

r'(t) = v_r
(r(t)θ'(t))²+r'(t)² = v_p²

Solving it out, you get

r(t) = v_rt+R
θ(t) = √(v_p²/v_r²-1)ln((v_rt+R)/R)

Note the problem we would have if the robot were faster than the player. Anyway, since the logarithm is unbounded from above, you know that this θ will eventually reach 2π, solving the problem. This also finds the smallest disc you can solve the problem on, since you just find that t where θ is 2π and put it back into r.

Not too tricky of a problem once you hit on the solution really, but at first it did look somewhat impossible.

Narrowing It Down

Well, that was quite a while without blogging, huh...Anyway, summer is here agian along with free time, so its time for the solution to the number guessing problem from last time.

When I was solving this on my own, I made a mistake and thought I figured out the solution when I actually hadn't, so then I looked at the real solution and was disappointed to see that I spoiled it for myself. Anyway, what I had figured out was an important piece of the solution, so I will post it anyway.

Essentially, you represent your numbers in binary, and then ask Alice "Is the ones digit of your number a 0?", "Is the twos digit of your number a 0?", "Is the fours digit of your number a 0?", and so on. So, if the first question is answered "no", the second question "yes", the third question "yes", then you know that 3 times Alice has told you the number is not something ending in 110. Extening this to all 10 digits, there will exist some number that Alice has said 10 times that that is not her number, thus you can eliminate it for your list of candidates.

To eliminate the next number, you could just renumber the remaining candidates, but a better way is just to use a series of sets. Assume the set S₀ is your list of possible candidates. Divide S₀ into two equally sized sets and ask if her number is in the first set, you then have S₁, the set of candidates that Alice just said her number is not in. Divide S₁ into two sets also, and take S₂ to be the set that she denies her number being in. Eventually you reach S₁₀ a set of numbers that she has just told you 10 consecutive times that her number is not in. As long as S₁₀ isn't empty, we have made progress. This requires that S₉ have at least 2 memebers, so S₈ has at least 4, moving up to S₁ needing 512 members so S₀ would need at least 1024. We can see this method will eliminate at least one candidate as long as we started with at least 1024. (When I solved this myself, I tried to go through that logic in my head, and miscounted to 512, so I thought I had a solution).

To proceed any further, we essentually do the strategy twice, but using the tail end of the last set of questions in the new questions, since any 10 consecutive questions must have at least 1 truthful answer. The method (as given by the xkcd forums) is:

If there are more than 512 candidates, act as follows: (This procedure will eliminate at least one additional number)
1a) Let C₀ be the set of all candidates. (C_n will be the set of numbers such that, if it is in C_n, she has told n straight lies.)
1b) Divide C₀ in half into A₀ and B₀. (|A₀| >= 256 and |B₀| >= 256.)
1c) Ask whether the number is in A₀.
1d) If she says yes, define C₁ to be B₀; if she says no, define C₁ to be A₀. (|C₁| >= 256)
2) Construct A₁, B₁, and C₂ in the same way. (|C₂| >= 128)
3) Keep going (|C₃| >= 64... |C₉| >= 1.
4) If |C₉| > 1, construct C₁₀ and eliminate all numbers in C₁₀. STOP.
5) Ask again "Is your number in C₉?".
6a) If she says no, you can eliminate all numbers in C₉. STOP.
6b) If she says yes, define D₁ as being C₀ - C₉. |D₁| >= 512. (A number will be in D_n iff it requires her to make at least n lies starting from the question in 5.)
7) Construct D₂, ... similarly. |D₂| >= 256, ... |D₁₀| >= 1.
8) Eliminate D₁₀. STOP.

The first 4 steps are the same as mine, but then switches in the case that the set C₉ has only 1 element (which could happen if C₀ had between 512 and 1023).

Anyway, thats it for that. You can solve the harder problem of trying to restate the initial problem replacing 2000 (the size of Alices initial set) with N, 1000 (the size of Bobs target set) with M and 9 (the maximum number of consecutive lies) with K, but I would suggest you take a look at the thread on the xkcd forums for that stuff, it goes pretty far down the rabbit-hole.

Xor Not

Hmm....funny how time goes by. Also, I had wrote down my solution to the boolean problem from last time, but then I lost it, and I kept on putting off working it out agian.

Anyway, lets work it out here. First, let us assume that we have managed to construct a series of boolean objects T₀, T₁, T₀₁, T₂₃, and so on, where T₀ is true if exactly 0 of (A,B,C) are true, and T₁₂ is true if exactly 1 or 2 of (A,B,C) are true and so on for the other T's. So there are in principle 16 such objects, we won't be needing them all, but I just wanted to define the general notation.

If we had these objects then we could easily express NOT A as follows:

NOT A = T₀ OR (T₁ AND (B OR C)) OR (T₂ AND B AND C)

We can see this because exactly 1 of T₀, T₁, T₂, T₃ will be true. If T₀ is true, NOT A must be true. If T₁ is true, NOT A will be true if B or C is true, and false otherwise. If T₂ is true, NOT A will only be true if both B and C are true. Finally if T₃ is true, then NOT A is just false. Note also that we can make similar expressions for NOT B and NOT C just by permutation.

Alright, how do we go about constructing as many of these T's as possible without using more than 2 NOT gates? Well, we have some of them for free, namely:

T₃ = A AND B AND C
T₂₃ = (A AND B) OR (A AND C) OR (B AND C)
T₁₂₃ = A OR B OR C

Next, we can make T₀₁, costing us 1 NOT gate:

T₀₁ = NOT T₂₃

T₁ and T₀₁₃ are now available:

T₁ = T₁₂₃ AND T₀₁
T₀₁₃ = T₀₁ OR T₃

and T₁₃

T₁₃ = T₀₁₃ AND T₁₂₃

Finally we can bring out our other NOT gate

T₀₂ = NOT T₁₃

At last we construct T₀ and T₂:

T₀ = T₀₂ AND T₀₁₃
T₂ = T₀₂ AND T₂₃

This completes the construction of T₀, T₁, and T₂, finishing the problem.

One At A Time

Alright, time for the solution to the blind maze puzzle from last time.

The solution is pretty simple, the main point to notice is that, for a particular N, there are only finitely many mazes that can exist, so you essentially solve them one at a time. Specifically, you number the mazes 1 through M, then begin by writing instructions for the solution for maze 1, which is easy to find explicitly. Next, assume you are in maze number 2, and see where you would be given the instructions you have written so far, and then continue with the instructions to solve maze 2. Step by step, solve all the mazes that you could possibly be in. This will only create a finite list of instructions.

As for the more difficult problem of finding a solution that guarantees ending the program on the final square, imagine running all of those M mazes in parallel, each using the same set of instructions. The goal is to make sure that we are on the final square of every maze simultaneously, then we stop the program.

To prove that there exists a program to do this, let us consider a randomly generated program that is S steps long. The randomly generated program will move north with probability e, south with probability 1/2-e, west with probabilty e and east with probability 1/2-e. I claim that for a sufficiently small e, and sufficiently large S, the robot following this program will be on the final square of every maze simultaneously at some point. In a sense, even if the claim is true, it does little to help us find a program for our solution, since we don't know how long we should run our randomly generated program for. This objection doesn't really matter though, we are only trying to prove existence of a program, we don't need to actually find it. If our program has any non-zero chance of getting to all the endings at the same time, then there exists a program that terminates on the ending of any maze we could be in.

Next, for a particular maze m, the robot is wandering around the maze at random, with probabilities as above. By the Perron-Frobenius theorem, there is a unique steady state distribution of probabilites p(i,j) for the robot to be at location (i,j), and after a large enough number of steps any starting distribution will converge to this one. The main idea will be to show that when e is sufficiently small, p(N,N) becomes close to 1 (in other words, over a very large timescale the wandering robot will spend almost all of its time at the exit).

The main point of the proof is that p(i,j) is proportional to ((1/2-e)/e)^(i+j) for any reachable (i,j) in the maze M (this is the point that I am not sure how to prove, I'm sure its something simple using random walk theory, but my education is deficient there). Since p(N,N) < 1, we must have p(i,j) < e/(1/2-e) ≤ 4e for (i,j) not equal to (N,N) (this happens because if we choose e < 1/4). Thus p(N,N) is at least 1-((N^2-1)*4e). It will take some number of steps to do this for each separate maze, but you can just take the maximum over all the mazes.

Now, note that if we have two events A and B, with probabilities 1-x and 1-y of happening, then the probability of A and B happening is at least 1-x-y (you can prove this from P(A and B) = P(A) + P(B) - P(A or B) and P(A and B) is at most 1). In our case, we have M events (getting to the end of the maze in each maze) and the chance of each happening is at least 1-M*((N^2-1)*4e). So, with a suitable choice of e, such as 1/(2((N^2-1)*4), the probability of all of the events happening is at least 1/2.

So there is some nonzero chance of getting to the end of every maze at once, and so there must exist some set of instructions that will end at the end of the maze. This proof gets us no closer to finding it, I suppose, but who cares about that.

One At A Time

Alright, time to finish off the solution to the balls in jars problem from before.

The essential proof is that it is possible to find an algorithm that will move from a position (a,b,c), with a>b>c, to a position (x,y,z) such that z is less than c. Thus by repeating this algorithm no more than c times, you must reach zero (given that we can only have integer values).

OK, suppose we start in some position. Call the bucket with the most marbles A, the one with the fewest marbles C, and the other one B. The names of those jars will not change throughout the algorithm, specifically even though C has the fewest at the start it might not at some later point. Let a, b, and c be the number of marbles in jars A, B, and C respectively. Note that even though A, B, and C will not change throughout the algorithm, the values of a, b, and c will.

The algorithm is: Check the value of floor(b/c). If it is even, move marbles from A to C. If it is odd, move marbles from B to C. If C has more marbles than B then stop, otherwise go back to the start.

Simple enough, now, to prove it works. We must prove that at the end B will have fewer marbles in it than C started with.

At the start, we know that b is greater than c, let us write b=qc+t with t less than c, so q being the floor of b/c. For this proof, we will not change the values of a, b, and c, I will assume those values are locked at the start.

Let us suppose b is not at least twice as big as c, so then q=1 and when we move marbles from B to C (as per the algorithm), B will have t marbles in it, and t is less than c.

Now, if q is bigger than 1, I will show that the algorithm will reduce the number of marbles in jar B without changing the value of t, so eventually q will be 1.

So, if we suppose q is even, so we move marbles from A to C. Now C contains 2c, and B contains b. Since b=qc+t=(q/2)(2c)+t, so b mod c and b mod 2c both give t (note that q being even was needed).

If q is odd, we will move marbles from B to C. Now C contains 2c and B contains b-c. Since b=qc+t we can also then show b-c=((q-1)/2)(2c)+t, so b mod c and b-c mod 2c both give t (in this case q being odd is needed).

Each time, B contains fewer marbles, so eventually q will be 1 and then next move B will have t marbles, which was less than the starting value of C. So, this finishes the proof. One simply needs to repeat the algorithm many times (renaming the jars A, B, and C after each iteration) to win the game.

Two In One

Alright, time for the partial solution to the balls in jars problem from last time.

I guess since the two-jar problem is a decent amount easier, I'll solve that out first.

First of all, it is absolutley trivial to see that if the total number of balls in the jars is not an even number, there will be no way to win, since to win you must first arrive at a position of the form (p,p). Next, it is easy to see that any common divisor has no effect on the ability to win from a position, that is to say: the position (p,q) is winnable iff the position (np,nq) is winnable.

At this point, we might be inclined to work out a few winning positions. OK, so what are the winning positions of the form (1,q)? Well, clearly (1,1) is a winning position, and (1,q) can only be a winning position if q is odd. From the position (1,q) we move to the position (2,q-1), but since q is odd for any position of interest this is the same as (1,[q-1]/2) so if we suppose this is another position, say (1,k), we see that q=2k+1 so if (1,k) is a winning position then so is (1,2k+1). From here we can list off the positions as (1,3), (1,7), (1,15)... clearly (1,q) seems to be a winning position if q is 1 less than a power of two. You can prove that by induction if you like, and with a bit more work we can also be sure that there aren't other winning positions of the form (1,q), but I won't bother with that yet.

Next, what about positions of the form (3,q)? Well, first of all q=1 would be a winning position. Next, from (3,q) we can move to (6,q-3) (this assumes that q>3, but other positions are finite enough anyway). Now since we might as well assume q is odd, we can half this position to (3,[q-3]/2) so calling this (3,k) again, we see that if (3,k) is a winning position then so is (3,2k+3). Listing off positions we can see that the winning positions seem to be (3,1), (3,5), (3,11), (3,29)... again summing to a power of two. This makes it seem that a position (p,q) is a winning position iff the sum p+q is a power of two. Well, thats easy enough to disprove, (3,9) is a winning position, but it is merely a multiple of 3 away from (1,3).

The main thing that will finish this off is the realiziation that once you have divided off any multiples in your problem, no new ones will show up, besides 2, and that one will show up every move. Lets prove that. Suppose we are in some position (p,q) with p and q both odd (so that their sum is even, but we do not need to divide off an overall 2), and we assume that p and q are not both multiples of some prime number n (n>2). Now we move to (p-q, 2q) (setting p as the larger one), I claim that p-q and 2q are also not both multiples of n. If they were then q would be a multiple of n (since 2q is) and then p would be (since p-q is and q is). Naturally this argument won't work for n=2, an overall multiple of 2 shows up every single move.

Now I will prove the main result: from position (p,q) with p and q having no common factors, we are in a winning position iff p+q is a power of 2.

You can prove one direction by induction. Prove it for p+q=2^n. It is trivial for n=1, then if it is true for n=k and you are in position (p,q) with p+q=2^(k+1) you can make one move and then half p and q so that p+q will now equal 2^k.

For the other direction we must show that if p+q is a multiple of a prime other than 2 and p and q have no common factors, then it is a losing position. Suppose p+q is z*k where z is a prime other than 2. k must be even, for if p+q is odd then we are trivially in a losing position. In order to win, we must first reach (z*k/2, z*k/2) but we have already proven that once you have divided off multiples, no new ones can show up. A new multiple of z (for z>2) cannot happen, so the position (z*k/2, z*k/2) cannot be reached, so the game cannot be won.

This finishes the proof. While working on the problem I also noticed that the legal move from (p,q) is to (2p,2q) mod p+q, which I thought was sort of cool. Perhaps people who are better at number theory than I can make use of that. Anyway, feel free to try to use this to solve the three jar problem, I was never able to.

Just One

OK, time for the solution to the coins puzzle from last time.

Not much derivation to do, so I'll just sort of post my solution:

Ask if he knows if one of Porthos or Aramis got at least two gold coins. If Athos got two of the three gold coins, he knows the answer is no. If Athos got no gold coins, then given that all three were given out he knows that the answer is yes. If Athos got one gold coin then he will not be sure.

Of course, you can switch "gold" for "silver" in that solution if you like. Anyway, simple, like I said, but I sort of thought it was neat. I would love to hear any alternate solutions, I haven't thought of any but they probably exist.

One Way Or The Other

Solution time! Puzzle last time was that game about breaking chocolate.

I know of two ways to come about the solution, the one is easy and elegant (and was how I solved it initially), while the other is a bit more roundabout and uses a bunch of game theory that I think is sort of cool. Anyway, I'm going to do the long game theory version first, if you want to just read the elegant quick solution, skip to the second last paragraph.

First of all, I'm going to set up a bit about game theory of impartial games, games where both players always have the same options available to them (other games are called partizan, chess and go are partizan games with one player playing black and the other white, I cannot move your pawn). I will also be focused exclusively on the type of game where the players alternate turns in the usual way. It is clear that for any impartial game, in any position either the active player has a winning strategy or the inactive player does. As is standard, we will call the former kind of position an "N-position" (for next player wins) and the latter a "P-position" (for previous player wins). It is clear that from any position you always want to move to P-positions, when possible.

At this point will be looking just at games that use the "normal play" rule that is, if you have no moves available on your turn you lose the game (as opposed to the "misère play" rule where having no legal moves is a win). So the game state with no legal moves is a P-position. Generally speaking, if from a game state you can move to a P-position, then that game state must be an N-position (since P-position moves are winning moves, having a P move available means that the active player has a winning strategy). On the other hand, if all the legal moves from a game state are N-positions (including the specific case of no legal moves), then that game state must be a P-position. So if a player has used this to completely map out the game space (first by labeling the end state P then moving outward labeling things P or N) that player will always try to move to a P-position, the opponent will have to choice to move to an N-positon, from which a new move to a P-position is available, and eventually the game must end with the winning player being the one who can move the game into P-positions (the end state also being a P-position).

Next we must figure out how game types combine when you add them together as we do in the breaking chocolate game. Suppose we start the breaking chocolate gmae from a 5x6 position and we move to the 5x2 + 5x4 position, what does that "+" mean? It means that we can make a move in either game. So, if G and H are both games, then G+H is the game where you can legally move in either G or in H, you must move in one of them, but not in both. Convince yourself that this addition is associative, that is (G+H)+J is the same as G+(H+J), it is also commutative but that is trivial.

Now we can prove something, I claim that if G is a P-position and if H is a P-position, then G+H is also a P-position (yay, a theorem), the proof is to simply show the strategy. If G is a P-position, then the inactive player has a response to any move the active player can make, and the inactive player can guarantee that it is the active player will run out of moves first (note how much more difficult it is if we used misère play instead, the fact is normal play is much easier to analyise in most cases). All this is true about H as well, so by simply always responding to the opponents moves in G with moves in G and respond to moves in H with moves in H you can always get to another position of the form P+P. So, we see that:

P+P=P

Good good.

Next, I claim that if G is an N-position and H is a P-position then G+H is an N-position. To prove this I simply need to show that there is a legal move in G+H to a state that is a P-position. We know that there is a legal move in G to a game state K with K being a P-position, but then K+H is a P-position by the previous theorem. So we see that there is a legal move in G+H to a P-position, specifically the move from G to K. So, we have:

N+P=N

Actually, we can quite generally show that if H is a P-position, then for any game G, G+H=G because you can just use your strategy in G and always respond to opponent moves in H with moves in H.

Alright, it is natural to wonder about N+N next, unfortunately you can come up with situations in actual games where N+N can be P and other games where N+N can be N. You can show that any game plus itself is a P-position, because in G+G you can always answer your opponents move in one with the same move in ther other, so they will run out of moves first, so G+G is a P-position, but if G and H are both N-positions, but not the same N-position, you can't prove much.

Alright, now for the chocolate game, I will prove the following statement for some arbitrary AxB position (I would have used NxM, but N is being used for something else here, and that notation is more standard):

AxB is a P-position if both A and B are odd and is an N-position if either A or B is even

The proof will be by induction, we can see this are true if AxB is 1x1, now to prove it by indution suppose we have want to prove this statement for a particular AxB and we are going to assume it is true for all ixB (with i less than A) and all Axj (with j less than B).

Now, I must show that AxB can reach a P-position if either A or B are even, this is easy, just move to (A/2)xB+(A/2)xB or Ax(B/2)+Ax(B/2), whichever exists. Then you mirror the opponent from there and cannot run out of moves first, so AxB can reach a P-position, it must be an N-position. Now if A and B are both odd, a generic legal move is to RxB+SxB with R even and S odd. But then RxB is an N-position and SxB is a P-position by the induction assumption and we know that N+P=N, so any legal move leads to an N-position meaning AxB must have been a P-position.

This completes the proof of the theorem, so we know from any start position if it is a P-position or an N-position so we can clearly say who wins and how (and the typical winning move is to break even sides directly in half), now I will show that that is totally unneeded and if you are in a winning position you can just make random moves and you won't ruin it.

Consider, at the start of the game we have a single block of chocolate on the table (of size NxM), each move causes one break in an existing piece of chocolate, increasing the number of blocks of chocolate on the table by exactly 1. The game ends when there are NxM blocks of chocolate on the table, so exactly NxM-1 moves have gone by, no matter what people chose as their moves there were exactly NxM-1 moves in all cases. The first player wins if NxM is even as there will be an odd number of moves, and the second player wins if NxM is odd as there will be an even number of moves.

Anyway, game theory is cool, but this game is really trivial. The P and N-position things come up alot in other games though, for example the game where you are removing sticks from a pile of N sticks but you cannot remove more than 4 (or K) at a time. You can also be a bit more general and use the Sprague–Grundy theorem to make any impartial game under the normal play condition into nim, but that takes more work (though not much more).

Trinary Answer

Two posts in one month? Unheard of. Anyway, I found a new puzzle recently, so now I have two puzzles I haven't posted and I want to waste them as soon as possible (also, post them before I forget what they are).

Alright, solution to last times light bulb puzzle:

You turn on one switch and leave it on for a reasonable amount of time, then turn it off and turn on a different switch. Go to the other building and check to see if the light bulb is on, warm, or cold, each of these results points to a different switch.

Not much to it, there are proably other answers, but its hard to come up with one as reasonable as this one. If you have any, I would love to hear them.

Off The Edge

I still blog, I swear. Anyway, I suppose I should put up the solution for the plane puzzle from last time.

There is a standard puzzle of this form where you have camels going into a desert and you have to feed them, bananas or something, but each camel can only carry a finite amount of food. Suppose a camel can carry enough food to go 90 meters (I choose 90 so I can take fractions of it easily), then with two camels you head out 45 meters, transfer all the food from camel 2 to camel 1 and can then go another 90 meters with camel 1 making a total of 135 meters. With 3 camels we can go 30 meters out, move all the food from camel 3 to 2 and 1 and then make it another 135 on top of the 30 for a total of 165. In general if one camel can carry the food for distance x, then the n^th camel adds an extra x/n to your total distance.

Anyway, then with our planes we can use this sort of strategy to go 1+1/2+1/3 times the distance half-way around the world, but that is only 11/6, so we are short. The solution to this is to make use of the fact that the puzzle is happening on the world, so we can go around the other way. Use two planes to go 3/2 the distance of one plane (that is 3/4 of the way around the world) and have the other plane meet you by going the last bit in the other direction.

Its not much of a puzzle, but its sort of cute and I thought it was a neat variation on a standard puzzle.