Friday, 4 May 2001

A problem solved

Listening to:

Schubert, Adagio in E flat, D. 897 «Notturno». I bought some headphones yesterday, so that I could listen to music at work and get better sound. Until yesterday, I'd been using some very cheap in-ear pieces. The difference is definitely significant.

A proof that there is always a solution to Wednesday's problem:

If trying to find a string of length 2n, for n > 0, draw a graph with nodes consisting of all the bit strings of length n-1 (there will be 2n-1 of these). Then draw arcs between these nodes such that there is an arc between s and t labelled with s<x> if the last n - 1 bits of s<x> are equal to t. (<x> is a single bit, either a one or zero.) There will be 2n arcs. Each node will have two incoming and two outgoing arcs. By Euler's theorem, there is a path through the graph that goes over each arc once. That will easily give the bitstring required.

Proof due to clever friends, or possibly clever friends of friends.

An interesting piece by Eric Raymond about Microsoft and Open Source.

Comments