Marlin’s Gottahack
– 1998 Sep 21 – HOME NEXT
Hi,
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.