17 March 2010

Typesetting Inequalities

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 l1l2, …, 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).

PS: I know the answers because of 11011110 and, respectively, geomblog.

3 comments:

rgrig said...

Just to make it explicit: The statement of problem Inequality is obfuscated to make it harder. I'll `deobfuscate' it when I post the answer. (The question is the same as something I asked on Mathoverflow, so you can view the answer there if you are impatient.)

Reith said...

Hi,
I'm writing (mostly written) a project for automatic programming exercise grading! (reith.bshellz.net/projects/tsi/) where i find your project on Ohloh, surprised! but can't find your E-mail address. maybe can we have share or experiences.
Sorry for irrelevant comment

rgrig said...

The inequality should say `greater or equal': Equality is obtained, for example, for b=f=1, and all others set to zero.

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.