[vox] Re: [vox-tech] shell script challenge - Now MD5sum erratia

[Peter Jay Salzman <p@MAPSdirac.org>]

begin Micah Cowan <micah@cowan.name> 
> Samuel Merritt writes:
>  > 
>  > Micah Cowan writes: 
>  > > [snip]
>  > > But it's a heluva lot better than running diff from one file to every
>  > > other file - a factorial-time operation! :)
>  > 
>  > I think it's only quadratic-time. If you have N files, you need to diff
>  > every possible pair of files to make sure that all the files are unique.
>  > So,  you pick a file F, and compare it with all the other N-1 files. Since
>  > you have to do this for all N files, and diff(file1, file2) is the same as
>  > diff(file2, file1), that's only N(N-1)/2 diffs that have to be done. 
>  > 
>  > This is exactly like a question you see in math puzzle books sometimes: If
>  > there's a group of N people and each person shakes hands with every other
>  > person, how many handshakes are there? 
> 
> Sorry: I was thinking of sums and not multiplication (which is what
> factorial is). I meant: N + N-1 + N-2 + ... + N-(N-1), which is
> equivalent to N(N+1)/2.
 
(redirected to vox since i'm not adding anything to the conversation)

this is totally irrelvent to the discussion, but very cute.  the proof
of that is to do the sum twice:


  N  +  N-1  +   N-2   +   N-3  +  ...  +  3   +    2   +  1    <- sum1
  1  +   2   +    3    +    4   +  ...  + N-2  +   N-1  +  N    <- sum2
 ===========================================================
 N+1 +  N+1  +   N+1   +   N+1  +  ...  + N+1  +  N+1   +  N+1  <- 2*sum


so we have (N+1) taken N times.  therefore, both sums taken together is
N*(N+1).  since we did the sum twice, we need to divide by 2.
therefore:


1 + 2 + ... + N-1 + N  =  N(N+1)/2


this was attributed to the german mathematician gauss.  the story says
that when he was 8 years old, he mouthed off to a teacher.  as
punishment, the teacher said he had to add all the numbers from 1
through 100.   he developed this to get the job done quickly.

pete

-- 
GPG Fingerprint: B9F1 6CF3 47C4 7CD8 D33E  70A9 A3B9 1945 67EA 951D
_______________________________________________
vox mailing list
vox@lists.lugod.org
http://lists.lugod.org/mailman/listinfo/vox