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).

In The Line

Time for a new puzzle. I first found this one on the internets:

N people are standing in a lineup. There is a person at the front of the line (who is not one of the N) who can look down the line and see a given person if nobody taller than that person is in front of them. Each person in the line is of a unique height. What is the expected number of people that the person in front can see if each permutation of people is equally likely?

Just to make sure the wording is clear, with N=3, there are 6 cases (and assuming the line starts on the left and the person I name 1 is shortest and 3 is tallest):

123 -> three are visible
132 -> two are visible
213 -> two are visible
231 -> two are visible
312 -> one is visible
321 -> one is visible

So, on average, 11/6 people are visible in the N=3 case.

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.