Flipping Vases

Alright, back to blogging before I stop blogging for another month or something. Time for the solution to the vases in a line puzzle from last time.

First of all, suppose we have a solution for N vases, then by removing vases M+1 through N, we will have a solution for M vases for any M less than N. Thus, we only need to find solutions in a few particular cases of N, as long as those cases get arbitrarily large it will be good enough (for example, we are going to wind up having a solution that works for N being a power of 2, since any number can be expressed a less than some power of two, you can simply grab that larger solution and remove the extra vases).

For future considerations, it will be slightly easier to subtract 1 from the heights of all the vases, so they are numbered 0 through N-1, rather than 1 through N.

We must arrange things so that no number is between two numbers it is the average of, so x cannot appear between x+a and x-a for any a. Note that the average of two even numbers is even and the average of two odd numbers is odd, and the average of an even number and an odd number is not an integer. This suggests that we place all the even numbers on one side, and all the odd numbers on the other. That way there is no concern of the "left side" and the "right side" having anything dangerous in between them, we can simply treat them independently.

Within the even ones, we can simply half them and solve the N/2 case. With the odd ones, we can subtract 1 from them and then half them and use the N/2 solution. Thus we can see that if we can solve N/2, we can solve N. This is why we will get solutions for powers of two, we simply must start by solving the case N=2 (this is trivial, the solution is (0 1)).

So, if we wanted to solve N=4, we have 0 1 2 3 to place in order, begin with the evens on the left and odds on the right and we get (0 2 1 3) as our solution. For N=8 we being by sorting them to (0 2 4 6 1 3 5 7) next treat 0 2 4 6 as 0 1 2 3 to get (0 4 2 6) and treat 1 3 5 7 as 0 1 2 3 to get (1 5 3 7), so the solution is (0 4 2 6 1 5 3 7).

There is another way to generate this solution, begin by writing out the numbers 0 through N-1 in binary

000
001
010
011
100
101
110
111

Next, reverse the digits

000
100
010
110
001
101
011
111

Next, read them off as they are to get (0 4 2 6 1 5 3 7), which is the same solution.

That first algorithm to get the solution is clean enough, and I was pretty happy to consider it the solution, but the second solution involving binary numbers in reverse is really cool (and I did not come up with it, I saw it on xkcd). Its a bit harder to prove that it always works though, but its not so counterintuitive that its impossible to believe. Naturally, if you want the solution for N that is not a power of two, just solve a larger N that is a power of two and ignore the extra numbers, so for N=5 we have (0 4 2 1 3), which after adding 1 becomes (1 5 3 2 4) which works as a solution.

Vases In A Line

Blogging is for chumps, I'm on extended vacation (also known as semi-unemployed). Anyway, time for a puzzle that I found on the forums at xkcd:

There is a museum with N vases they wish to arrange on a display. The vases are such that the first one has a height of 1cm, the second one has height of 2cm, and so on such that the N^th one has a height of N centimeters. The people at the museum wish to arrange the vases in a linear display in a special way, such that if we have three vases with heights a,b,c, with b being the average of a and c, b does not appear between a and c.

The puzzle is to come up with an algorithm that will generate an arrangement of numbers 1 through N such that no number appears between two numbers it is the average of.

So, for example if N=5, we could not have 3 appear anywhere between 2 and 4, or anywhere between 1 and 5, 2 could not appear between 1 and 3, and 4 could not appear between 3 and 5. An acceptable answer there would be (1 5 3 2 4).

Arrangements and Derangements

So, it seems that finishing my thesis has slowed down my blogging. Blogging was done as a way to slack from work, and now I don't really do much work anymore, leaving me with nothing to slack from. Basically, I need to start looking for a job so I can slack off with maximum efficiency.

Alright, time to look at the solution to the sorting puzzle from last time. I guess the solution was given in the comments, which means that I actually have something of a readership I guess (which is a good thing?), anyway, I have no problems with people posting solutions in the comments, but I'm going to do my own solution as usual.

First, lets try to solve it in some simple cases. We already know that the sequence (2 1) takes two moves, how about the sequence (3 1 2). There seems to be no reason to hold any of them in place, and a randomization has an equal chance of going to any of (1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1). The number of steps those are away from the sorted form is 0, 2, 2, k, k, 2, respectively, (knowing that, say, (1 3 2) is two steps away on average) where k is the number of steps (3 1 2) is away. This allows us to say that

k=1/6(0+1)+3/6(2+1)+2/6(k+1)

which can be solved to get k=3. So this solves the N=3 case completely.

For N=4 we have a bit more of a complicated situation, it is clear that anything such as (_ _ _ 4) reduces to the N=3 case, but we have two separate things to solve, one is things of the form (2 3 4 1) where we have everything out of place, and the other is of the form (2 1 4 3) where we have two separate groups. We already know that it is possible to solve (2 1 4 3) in two steps by doing the first two separate from the second two, but it might be better somehow to just ignore that they are two separate cycles and randomize the whole thing. If it is better, then (2 3 4 1) will be less than 4 steps away on average. If it is more than 4 on average, then we should treat cycles separately, and if it is exactly 4 then it does not matter if we isolate cycles.

First, we will treat cycles separately, and let g(n) be the number of moves it takes on average to sort an n-cycle with each element out of place to the right by one (or left if you like). We have seen g(2)=2, g(3)=3 and trivially g(0)=0, g(1) isn't really a thing since you can't have a cycle of 1 with each one being out of place. Anyway, from a 4-cycle we have 24 places we can go, 1 of them is (1 2 3 4), the solution, ₄C₂ of them are 2-cycles (like (2 1 3 4)), ₄C₂/2 of then are two 2-cycles (like (2 1 4 3)), 8 of them are 3-cycles (you can see this by locking one of them down and there are two ways the remaining three are out of place), and the remaining 6 of them are 4-cycles. We can then see that

g(4)=1/24(0+1)+6/24(g(2)+1)+3/24(g(2)+g(2)+1)+8/24(g(3)+1)+6/24(g(4)+1)

which we can solve to get g(4)=4. If we chose the other strategy of just treating two 2-cycles as a 4-cycle, we would replace the term g(2)+g(2) with g(4) instead, and still get the solution g(4)=4, showing that the strategies are the same.

Given that, we might as well only lock down ones that are in the correct place, and not worry about the smaller cycles. Let f(n) be the number of steps it takes to get from a completely unsorted list of n elements to a sorted one ("completely unsorted" means none are in the correct place). Mathematicans have a name for a completely unsorted list, they call it a derangement, and the standard notation for the number of derangements of n elements is !n. A few early ones are !0=1, !1=0, !2=1, !3=2, !4=9. Our earlier strategy for finding f(4) can be expressed as

f(4)=!0/4!(f(0)+1)+!1/4!(f(1)+1)+!2/4!(f(2)+1)+!3/4!(f(3)+1)+!4/4!(f(4)+1)

that is, f(4) is the chance you get k elements in the wrong place, times f(k)+1, summed over k. The chance that exactly k elements are in the wrong place is !k/4!. f(1) isn't really defined, but !1 is zero anyway, I just included that term for completeness.

From this we can deduce the general form

f(N)=Σ !k/N!(f(k)+1)

summed k from 0 to N. If we hypothesize that f(k)=k for all k less than N, we can then proceed to prove f(N)=N, though it is rather tedious to do it this way.

The more intuitive way to get f(N)=N was given in the comments, throwing N elements into the air, each one has a 1/N chance of landing in the right spot, and you threw N of them, so on average one of them will land in the right spot. Thus it takes N steps.

Sorting Numbers

Alright, new puzzle time, Bart showed me this one from the Code Jam this year:

You have a list of the integers 1 through N in some random order, and you are going to attempt to sort them. The only operation you have is to randomize any subset of these integers. Specifically, you may select any subset of the integers and lock them in place, and then the other ones get rearranged randomly. You may perform this operation as many times as you like, but want to do it as few times as possible.

Given the initial list of integers, what is the optimal average number of steps it will take to get the list in order?

The original puzzle had a bit more coding bubble-wrap around it, but not too much. It also had a nicer explanation of why the algorithm is so weird, but whatever.

As a few specific examples, if the initial list is (2 1 3), you can hold the 3 in place and randomize the other two until they fall in place, this will take on average 2 steps. If the initial list is (2 1 4 3) you can hold the first two in place until the second two land in order and then hold the second two in place until the first two land in order. This will take 4 steps on average. Given the initial list, is there an easy way to determine how many steps it will take on average? (Hint: there is, or I wouldn't consider this puzzle interesting).

Cards and Coins

Alright, time for the solution to the score cards puzzle I put up last time. The comments contained the essentials of the solution, but I still want to type anyway.

First, suppose we had a target number N and a solution to use bases a,b,c,d... That is to say, the product abcd... is at least N with the sum a+b+c+d+... minimized. Suppose the proper solution had a 7 as one of the bases, it is just as good to replace the 7 with a 5 and 2, it makes the sum no larger and in fact makes the product bigger, we can similarly replace 6 with 4 and 2 and even 4 with 2 and 2. In all cases where a is larger than 4 it is better to replace a with a-2 and 2 (this is sort of obvious, but if you wanted to prove it note that 2(a-2) > a can be rearranged into a > 4). Anyway, so a proper solution has no need to contain numbers greater than 3, it should only have 2's and 3's.

Next, note that if a proper solution ever had three 2's, we might as well replace them with two 3's, since the product is larger and the sum the same. So any proper solution need not contain more than two 2's. Thus, we find the algorithm to find the optimal base for a target N. Select k such that 3^k is at least as large as N and 3^k-1 is smaller than N. Compare 3^k-12 and 3^k-22² to N. Whichever of those things is smallest while being larger than N is the expression of the solution.

It is somewhat surprising that base 3 is the optimal solution, most people (myself included) would intuitively think that base 2 is better, but that is just not the case. In some cases base 2 does work fine, our solution does give an optimal solution, but it is not the only one, for example if the target number is 60 then this solution gives us to use 3⁴, however using 2⁶ works just as well. As the numbers get sufficiently large however, base 3 will always win out.

One can "generalize" this problem somewhat by assuming the numbers do not have to be integers. So, we have to select numbers a,b,c,... to minimize their sum and have their product be N. There is nothing to be gained by overshooting N if we are using reals rather than integers, so we might as well hit it exact. Whats more, if two numbers a and b appear in the solution we would do just as well to replace them with a/x and bx with a smaller sum. How do we minimize the sum of a and b while keeping the product equal? This is just minimizing the perimeter of a rectangle, make it a square, set a=b. So we actually should only use a single number a. That is, we want p copies of a such that the sum a+a+a+... is minimized while the product equals N. That is, minimize pa with N=a^p. Minimizing a(Ln(N)/Ln(a)) over a gives us a=e. Giving us that the optimal base is base e. This is sort of why 3 was best, it is the closest integer to e, with 2 also sort of being part of it (I'm not sure how to interpret that, but it feels right).

This also can be taken as a commentary on currency, the optimal base for a currency is base 3 (base e would be better, but then your coins are really weird and making change is hard). Base 3 currency is optimal in the sense of needing the fewest total number of coins to represent a variety of different values. Of course, I doubt we will see a switch to base 3 coinage anytime soon, a single coin of value 3 could probably happen (and probably has, but I know of no real world examples), but coins of value 27 and 81 would be pretty hard to get used to for people who are used to thinking in base 10.

Score Cards

Alright, time for a new puzzle. Though I meant to post last time that that lemma I used didn't actually need the numbers a_i to be positive reals, it is sufficient to be real. The proof is the exact same even, the only thing that needed to be positive in the proof were the z_i, and positivity is guaranteed by L being the minimum L_i. Anyway, whatever. New puzzle, I first learned from Bart:

There is a school that is using flip cards to keep track of scores in their sporting events. They use a series of cards to represent the ones place of the score, and another series for the tens place and so on for as many places as they feel they need. They want to minimize the number of cards used however, and (being a very mathematically inclined school) they are willing to change from base 10 to another base to accomplish this. For example, if you wanted to represent scores 0-99 in base 10 you would need 20 cards (10 for the ones place and 10 for the hundreds place) however you could do even better by using base 5 and having 3 sets of 5 cards (15 cards total) and be able to represent all the way from 0-124, naturally having the ability to represent extra numbers is not harmful at all, if it uses fewer cards it is better.

Actually, this school is even more mathematically inclined than that, they are even willing to use different bases for each place, for example the first digit could be base 5, the second digit base 5 and the third digit base 4, this uses only 14 cards and can represent 100 different possible numbers.

The puzzle is this: given a target number N, find the minimum number of cards it would take to represent at least the numbers 0 through N-1 on this style of scoreboard.

The solution to this puzzle is somewhat surprising, if you do think you have found a solution, make sure you have checked it out in some medium-sized cases (like numbers 10 through 25) to make sure it works, or better yet have a full proof done that it is actually optimal.

Nonlinear Prisoners

OK, I just finished my PhD departmental defense, so now its time to look over the solution to the prisoners and light switches puzzle. I wanted to have a post calculating out how long the actual strategy would take for the prisoners to complete, so here we go.

First, we need to figure out how long each procedure will take to perform, starting with the upper bound procedure. The upper bound procedure has k nights of activating people, followed by k nights of deactivating people. If the number of prisoners is N, they will have to run k from 1 to N before the warden is forced to reveal there is an upper bound, this will take N(N+1) nights, and they will have an upper bound B=2^N. The cannot say the upper bound is lower than that, as they do not know what the warden chose to do.

A ping procedure takes B nights to perform, obviously, and the bing procedure takes 1 night. The upper bound procedure is the awful one, for it takes 2^z nights if it is called for on night z.

When the how many times can the warden make them call the upper bound procedure? Well, that depends on how big he can group them up. If he groups the prisoners into very large groups and then splits them off one at a time until they are all in their own groups of size one, the warden will maximize the number of times they perform the group division procedure.

Suppose we have N prisoners. As they run the upper bound procedure, the warden cannot do better than to split them into lg(N) groups. Actually, odds are that if he does this maximally, they will probably find their value of B faster and it will be smaller, but I don't want to do a more complicated calculation than this. So, they have taken on the order of N² nights to find B, the group division procedure than takes like 2^N2 nights. Next they do lg(N) pings, costing B lg(N) nights, but that is nothing compared to 2^N2. The adversary makes one more group, so they call the group division procedure again and it takes 2^(2^(N²)) more nights.

We can see where this is going, the warden can make them call the group division procedure N-lg(N) times, resulting in the prisoners needing x^N2 nights, where x is 2^2^2^2^..., N-lg(N) times, also known as 2 tetrad (N-lg(N)). I tried calculating out that number for something like N=20, but it was huge beyond my comprehension. So then I tried N=5, and again, it was huge beyond my comprehension. Basically, this strategy is stupid.