Here is one of Michael Boshernitzan’s favorite math problems, which came up again recently. I’d like to find an optimality proof for it, let me know if you have come across one:
General Karmov orders a 100-man company to line up for inspection. He is in a foul mood, and unfortunately the commanding officer doesn’t know his quirks. So when Karmov demands they form a single orderly line, the CO forgets to order them by height. “How sloppy! Must I do everything myself?” Karmov asks noone in particular, stepping back to consider the whole line. “No, don’t move.” He pulls out his pistol and walks down the line, shooting soldiers as he goes, until what remains is ordered by height. He stops from time to time to reload. Being a mathematician, he shoots no more soldiers than necessary to order the line…. What is the minimum number of soldiers remaining when he is done?