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.

Robot Chasing

New puzzle time, because I actually have more than one in mind and I don't want to forget them.

I found this one somewhere random on the internets, I'll try to dig it up agian when I do the solution:

You are playing a game where you have to catch a robot. You and the robot are on an infinite 2-dimensional plane and you can see where the robot is. When the game starts the lights will be turned off and the robot will select a random direction and move in that direction at a constant speed. You may move around, and your top speed is some number which is greater than the robots constant speed (call them v_r and v_p for the robot speed and the player speed if you like). You naturally cannot see or hear the robot once the game begins. Find a strategy that guarantees you will find the robot.

So you must find a path (x(t), y(t)) which starts at a point (x₀, y₀) which never has a speed exceeding v_p and that path much intersect the robots path such that there is a t where they meet.

As a bonus problem, assume the game is played on a disc of radius R, with the robot starting in the center of the disc and the player on some point a distance P away from the robot. If the robot reaches the edge of the disc it escapes and the player loses. What is the smallest R for which your strategy works?

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.

Guessing numbers

Time for a new puzzle, I found this one recently on the forums over at xkcd:

Alice comes up to Bob one day and says "I have selected a random number between 1 and 2000, and I will let you hand me a list of 1000 numbers, if my chosen number appears on your list I will give you a prize."

Bob wants to win the prize, but would like a better than 50% chance at it, so he asks "Alright, but may I ask you some yes/no questions about your number?"

Alice doesn't want to make this easy for Bob, so she replies "Ask as many questions as you like, but I am allowed to lie in giving my answers."

Bob says "Well, that isnt very helpful." He then thinks about it and realizes "Actually, as long as you promise never to lie more than nine consecutive times, I think I can do this."

Alice doesn't believe this is possible, and is willing to hand over the prize if Bob can actually come up with such a strategy, so she agrees "Very well, ask your questions, I will not tell more than nine consecutive lies."

What is a possible strategy for Bob that will guarantee that he can narrow down Alices number to no more than 1000 candidates?

So you may ask as many yes/no questions as you want, and in any string of ten consecutive questions, at least one of them will get a true answer.

There is one common false solution I will refute right here, asking the same question 10 times in a row won't work, Alice will just alternate "yes" and "no", and will not have told ten consecutive lies.

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.

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.