Marlin’s Gottahack – 1998 Sep 21 – HOME NEXT



The Concept



I believe you all know one another, if not you'all can introduce yourselves. As most of you know, I started up Sunhawk with the idea that I would make a lot of money selling sheet music and be able to use our tremendous profits to get together a group of hackers/musicians and do some interesting research on music composition and ways to do that from the computer.


Well, profits come way slower than anticipated and the writing is on the wall, if I wait till Sunhawk is stable to get started on the research, it will never happen.


I decided that the best way for me to get going is to start doing something regularly and this is that something. I have been spending far too long worrying about what language I should be writing in, VB, FORTH, ASM, or (gag me) learn C++. As a result I have been writing nothing. Then it occurs to me that the choice of language is obvious. It should be English most of the time and any or all of the above when appropriate. English is the most robust and flexible choice and it don't even gotta parse good!


So with this email, I am going to try to start my research group. You all are free to contribute if you wish, remain silent if you wish, or throw these mailings out unread if you wish. I am going to try to produce something weekly. I figure that if I set myself a regular correspondence date (every Monday night) I ought to be able to hack out something.


I certainly do not expect on any given week to produce anything particulaly mind boggling but I can certainly set aside the time to write and in the absence of inspiration I can always write up some totally random thing. I will be happy to act as a consolidator i.e. you all can send me comments, material, whatever and I will fold it all into one weekly document. This does not of course prevent or even discourage you all from emailing one another, it merely attempts to consolidate the threads in one place. For all I know, email is not the best way to do this, there may be discussion groupware that does it better. I am open to suggestion.


The Rules



OK. Now that that is settled we should talk about the rules. "What? Rules in a knife fight??" - (from Butch Cassidy and the Sundance Kid) They ain't NO rules! gottahack is for those of us that gotta hack. (have you got a hack to share?) It does not have to be computer algorithms and music composition ideas. Poetry and novels are ok. Pictures of the dog are ok. Random math puzzles are ok. Half baked ideas are espically ok. So launching right into some random stuff I typed up earlier this week.


Math Puzzle #1


4 singers enter a contest to pick the best singer. It is decided that the 4 singers themselves are the best qualified to judge the contest. It is also decided that no man should vote for himself since that would be unfair so every singer gets to cast votes for the others using a point system. Each singer awards 3 points to the best man (excluding himself of course), 2 to the second best and 1 to the worst (and 0 to himself).

The scores are tallied up and the results are a perfect 4 way tie, every man getting exactly 6 points. Then one of the singers confesses that he cheated. Instead of giving the best man 3 and the worst 1, he reversed them. He figured that if he gave the best guy only 1 point and the worst one 3, it might help the best man to lose and thus better his own chances. Well, the real surprise is that as soon as he confessed to this cheating, 2 of the other singers admited to doing exactly the same thing. In short, there was only one honest singer in the crowd.

Naturally once the cheating was brought to light, the votes were retallied correctly.


Once the votes are recounted, what is the standing of the one honest singer. Did he come in first, second, third, or fourth?


Answer next week.


The Twelve Days of Christmas



You all know the song:


On the first day of Christmas my true love gave to me a Partridge and a pear tree (one object)

On the second day... 2 turtle doves and a partridge in a pair tree (2 + 1 objects = 3 objects)

On the third day ... 3 + 2 + 1 objects = 6


Clearly on day N my true love give to me T(n) objects, where T(n) is the triangular number for n.


As we all recall from our early math education


T(n) = n*(n+1)/2


You have probably heard the story about how Gauss wowed his elementary school teacher by whipping out this formula to sum up the numbers from 1 to 100 before the teacher had time to sit down after telling the kids to spend the afternoon summing up those numbers.


Probably at some point or another you were forced to prove it using mathematical induction. Most likely this formula for the triangular numbers was used to introduce you to the concept of a proof by mathematical induction.

Now upon contemplating the days of Christmas the question may arise: "How much stuff total have I accumulated over the twelve days of Christmas?"


Clearly it is the sum of the first 12 Triangular numbers. But what is the formula for that? (No pulling out the CRC and looking it up!)


In all my years of math education, I was given many opportunities to "Prove that this formula is correct by induction" but was rarely given any reason to derive such a formula. One occasion out of the school framework when I had to derive some such formula it occurred to me that you could use exactly the same method that you use in executing an induction proof of a formula to derive the formula. I thought I would pass on that method if you have not already seen this trick.


What I am looking for is a formula for the sum of the first N triangular numbers, S(n).


I make the random assumption that since summing up the first n numbers gave a quadratic formula then probably summing up the first n quadratic triangular numbers will be something like a cubic or possibly higher power. I.e.


S(n) = An^3 + Bn^2 + Cn + D


I don’t know what the constants A,B,C, and D are but I believe that the final formula for the Sum of the first n triangular numbers has that form.


Now since I have the formula for S, I "prove" that it is correct by induction. First we "prove" it for 1


S(1) = T(1) = 1 = A + B + C + D


This gives me one equation in A,B,C, and D.


Then we "prove" it for (n+1) assuming it is true for (n)


S(n+1) = A(n+1)^3 + B(n+1)^2 + C(n+1) + D = S(n) + T(n+1) = An^3 + Bn^2 + Cn + D + (n+1)(n+2)/2


If you expand and collect all the terms in the polynomial you get


An^3 + (3A + B)n^2 + (3A + 2B + C)n + (A+B+C+D) = An^3 + (B+1/2)n^2 + (C+3/2)n + (D+1)


Now if the proof is to work for all n, the corresponding coefficients of this polynomial in n must be equal so we get a system of equations


A = A

3A + B = B + 1/2

3A + 2B + C = C + 3/2

A + B + C + D = D + 1


The first of which looks pretty useless but then we remember the equation that we got from "proving" the 1 case, namely:


A + B + C + D = 1


Four equations with 4 unknowns and since the sucker is already practically in triangular form we quickly solve for A,B,C, and D


A = 1/6

B = 1/2

C = 1/3

D = 0


So the formula for how much stuff you have after N days of Christmas (assuming you have a true love) is:


S(n) = (n^3 + 3n^2 + 2n)/6


You can check the first few numbers to see that


S(1) = 1

S(2) = 1 + 3

S(3) = 1 + 3 + 6

S(4) = 1 + 3 + 6 + 10


But of course there is no need to check. We know that the formula is correct because we already proved it by induction.


Pretty cute, nee?


If you're curious where this came from, it was the first week of school for the kids. Amanda's teacher started on day one singing, "On the first day of school my teacher gave to me, a pencil with an eraser." and gave them each a pencil. On the next day she gave them 2 pechee yellow folders and one pencil with an eraser. WOW! Amanda could hardly wait to see what she was going to get three of on the next day. I get to thinking, "if she keeps this up all week, how many of each supply does she need to get? humm, 5 pencils, 8 yellow pechee folders, 9 of some other thing... what does it all add up to?" Then I remembered this way that I had discovered some 20 years ago and figured I should write it up.


Comming up


Some new ink compression algorithms, thoughts on 2D parsing, whineings about the inadaquacy of ascii text in Eudora email for writing equations and maybe some news about the kids.


Let me know what you think.