These are two puzzles I arrived at while working on my PhD thesis. I know the answers but not because I derived them. I think both puzzles are quite hard. Have fun!
Typesetting. As you know from a previous post, ViM doesn’t handle paragraph reformatting very well in LATEX, so I wrote a small tool. Given word lengths l1, l2, …, ln we want to insert line breaks such that (1) no line is longer than l and (2) the shortest line is as long as possible. Here’s the challenge: do it in O(n) time.
Inequality. Show that the following inequality has no solution in non-negative reals (or integers if you prefer).