Google Foobar: a Post Mortem
So, what was Google Foobar about? I still don't know. I will describe the problems I encountered, the techniques I used and what I learned. I will also discuss a few conjectures I have about it.
In a letter to the zoologist J.Z. Young, British mathematician Alan Turing announced that his theory of embriology could explain, among other things, the connection between leaf arrangements and Fibonacci numbers.
A sequence of integers \(d_1,\dots,d_n\) is called graphical if there exists a graph \(G\) with it as its degree sequence. A theorem by Erdős and Gallai characterizes which sequences are graphical, but gives no algorithm to explicitly construct such a graph. Can you construct it?
Who killed the Duke of Densmore?
One day Sherlock Holmes received the visit of his friend Watson, who was asked to investigate on a murder that had gone unsolved for more than ten years. At the time, the Duke of Densmore had been killed by a bomb powerful enough to destroy the castle where he had been living since retirement.
Four-coloring a Dodecahedron
By the Four color theorem, the faces of a dodecahedron are four-colorable; that is, one can pick a color among four for each face in such a way that no two adjacent faces share the same color. But can you find such a coloration?