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.