Three Princesses

New puzzle time, I found this one some time ago on the forums at xkcd, but I wasn't sure if it was the style of puzzle I like to have here. Upon further consideration, and a lack of new puzzles to put up, I have decided that this is a good puzzle after all.

You are the most eligible bachelor in the kingdom, and as such the King has invited you to his castle so that you may choose one of his three daughters to marry. The eldest princess is honest and always tells the truth. The youngest princess is dishonest and always lies. The middle princess is mischievous and answers questions with either yes or no, however she pleases, ignoring the question asked.

As you will be forever married to one of the princesses, you want to marry the eldest (truth-teller) or the youngest (liar) because at least you know where you stand with them.

The problem is that you cannot tell which sister is which just by their appearance, and the King will only grant you a single yes or no question which you may only address to one of the sisters. After your question, you must select a princess to marry. What yes or no question can you ask which will ensure you do not marry the middle sister?

Its mostly a standard "knights and knaves" scenario, and I typically dislike these sorts of puzzles because the answer is invariably some bizzare meta-question (that is, a question of the form "If I were to ask that person '(insert question here)', what would their answer be?"). However, the 'intended solution' to this problem has no meta-questions involved, actually it is quite elegant. Given the nature of the question, it probably has a bunch of other solutions too, so it could also be interesting to see if anybody posts an answer I haven't seen.

They'll Get There Eventually

Alright, the Sending Scouts Into The Desert problem has been up there with no solution for far too long, I suppose its time to post the solution. I'm going to proceed assuming that you have not already read the solution over at cut the knot and basically steal their derivation.

We will do the solution case by case first. For N=1, it clearly takes two pieces, one on the first line and one on the second line. For N=2 it takes 4 pieces, 3 on the first line and 1 on the second line. N=3 is a bit less trivial, but it won't take long to find that you need 8 pieces. So, so far the pattern goes 2,4,8, so it looks like N=4 should take 16. This is actually not the case, if you try it you won't be able to get to N=4 with less than 21 pieces (cut the knot says you only need 20, but I am reasonably certain that they have made some error, I cannot find anything better than 5 on the first line + 5 on the second line + 5 on the third line + 5 on the fourth line + 1 on the fifth line).

For N=5 the situation is even more interesting though, you cannot get to the fifth line with any finite number of pieces. To see this, let us consider a function that maps board configurations onto integers. We will later arrange the function so that legal moves do not increase the value of the function, so you cannot reach a higher-valued configuration from a lower-valued one, and use this to prove that we cannot reach the fifth line.

Let us assign a number to each square of the checkerboard, and the function will simply add up the numbers at the locations where we have pieces. We will arrange the numbers so that legal moves never increase the value of the function. Let us assume that somebody claims to have reached a particular square on the N=5 line of the board. We will assign that square a value 1. The four squares that neighbor it will be assigned a value x (we will fix x later). The next 8 neighboring squares will be assigned value x². The next 12 neighboring squares will have value x³ and so on out to infinity. More concisely put, we have the "master square" of value 1 and a square that is K spaces away (taxicab metric) from the master square has value x^K.

Let us consider a generic legal move, where piece A jumps piece B. There are three types of things that could have happened from this. First, A could have landed closer to the master square than it was before. In this case, A started on x^m, while B started on x^m-1, then A ended on x^m-2. To ensure that the function is nonincreasing, we need

x^m-2 ≤ x^m-1+x^m

The second type of move has piece A moving further away from the master square. In this case, A started on x^m and B on x^m+1, with A ending on x^m+2. For a nonincreasing function, we need to have

x^m+2 ≤ x^m+1+x^m

The third type of move has piece A staying the same distance from the master square. In this case, A started on x^m and B started on x^m-1, with A ending on x^m. So we need to satisfy

x^m ≤ x^m-1+x^m

This condition is satisfied easily if x is a nonnegative number.

Let us assume that the first condition is an equality (this means that moves toward the master square will conserve the value of the function, rather than decrease it). Dividing out x^m-2, this equation solves to 1-x-x²=0, meaning that

x=(√5 - 1)/2

There is another root, but it was discarded because x must not be negative. This x is actually the inverse of the golden mean. The last equation remaining is also satisfied by this choice of x, as you can confirm easily.

Now, supposing as before that the master square is on the fifth line, it is the place on the fifth line that somebody claims that they can reach using some path of legal moves. This configuration has value 1 (or more, if they had extra pieces lying around), so their initial configuration must also have value 1 or more. What is the maximum value you can get with a configuration of pieces in your base to start? You have at most 1 piece on x⁵, at most 3 pieces on x⁶, at most 5 pieces on x⁷, at most 7 pieces on x⁸, and at most 2n+1 pieces on xⁿ⁺⁵. Thus, the most value of pieces you can have is

Σ (2n+1) xⁿ⁺⁵

the sum running from 0 to infinity (actually this isn't really the most you can have, its actually more than you can have with any finite number of pieces, but its how much you could have with an infinite number of pieces).

We can simplify the sum to

2x⁶Σ nx^n-1 + x⁵Σ xⁿ
= 2x⁶ d/dx Σ xⁿ+x⁵Σ xⁿ

Of course, the sum &Sigma xⁿ is 1/(1-x) (since x is between -1 and 1) so we have

2x⁶/(1-x)²+x⁵/(1-x)

Now we use 1-x=x² (the quadratic that x solved) to simplify this to

2x²+x³
=x²(2+x)
=(1-x)(2+x)
=2-x-x²
=1

Therefore, no finite number of pieces can have total value 1, so no finite number of pieces can make a series of legal moves that ends with a piece five lines deep.

I suppose one can still imagine an infinite number of pieces doing it, but it will also take them an infinite number of moves, so its not clear that it really makes any sense to talk about such a thing.

Sending Scouts Into The Desert

The problem I have this time is a bit of a weird one, I mostly only show it because it has an amazing solution and proof. I first found this puzzle at Cut The Knot, which is something of a math puzzle page.

Consider an infinite 2-dimensional checkerboard. The upper half of the board is called the "desert" and the lower half of the board is called the "base", and there is a line across the middle that divides the two (just to be clear, there are no squares between the desert and the base, every square is either in the desert or the base).

You will be playing a one player game on this board. First you set up as many checkers anywhere you want in the base (each square may only be occupied by one checker). Then you begin making your moves. A move consists of a checker jumping another single checker that is orthogonally adjacent to it and landing on the space on the other side (which was unoccupied before). The checker that is jumped over gets removed.

The goal is to get one of your pieces as far into the desert as possible. Find how many pieces it takes to get N spaces into the desert.

That may have been a bit awkward to read, however there is a nice applet at Cut The Knot that will allow you to play this game. That page also has the solution to this problem, so don't scroll too far down unless you are ready to see the solution. The solution that is there is quite well written though, and when I post the solution to this next time I'm basically just going to be following his derivation.