Not Not

Blogging sure slows down when my life is consumed with marking.

Anyway, heres a new one that was told to me by some people in the math room on KGS:

You have 3 boolean inputs, A, B, and C. You are to set up a circut that has 3 outputs, D, E, and F. You may use as many AND and OR gates as you like, but only 2 NOT gates. Arrange it so that D has the value of NOT A, E has the value of NOT B, and F has the value of NOT C, for arbitrary inputs of A, B, and C.

To put that into a bit more "math" and less "circutry"...give me expressions for NOT A, NOT B, and NOT C, if you can only use NOT twice. You may store variables and use them freely, but you may only call the NOT operator a total of 2 times. For example, you could define P = NOT (A OR B) and then use P as much as you like and that would only count as 1 use of a NOT gate.

For a more general version of the problem, you have 2n+1 inputs to negate, and only n+1 uses of NOT. The general version is fairly tough though, and not very fun.

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.