On Reading Peter

I love math/algorithmic puzzles, and when I was in high school, worked on olympiad problems for fun (I did write a "book" on solving these problems and sold them locally thereby funding a year of my social life in college, but no more on that story here). Yesterday, on my way to my vacation in Croatia, I decided to read Peter Winkler's book (Mathematical Puzzles: A connoisseur's collection). Peter is a connoisseur, and my favorite; I started reading this book to atone for missing his talk at ICALP, as a treat for me, and finally as a rehab since I felt a little disconnected with actually solving problems the past few weeks.

This is a long post in which I will capture as much as possible, my raw thoughts as I encountered one problem after another in Pages 1 -- 14. It is one thing to read the solution to a puzzle, but maybe the act of how one confronts a puzzle is interesting to some.

• The Bixby Boys puzzle. This sounds familiar. Typically think of father/son combo, in this case, since it is same birthdays, one quickly guesses: triplets.
• Attic Lamp Switch: Known.
• Gasoline Crisis. Given n points on a circle C with fuel x_i on the ith, if \sum x_i suffices to exactly go around C once, is there an i such that one can do this starting at i with an empty tank? Say I start at some point and move clockwise, collecting fuel as I go. The first time I run out of fuel before hitting the next point, I thought there would be some local exchange argument that will tell me I should have started elsewhere. I could not see any such local argument, indeed, the problem seemed to involve non-local segments. After some thought, I decided to go on with negative fuel and drew the picture of the fuel in the tank over the whole course. The fuel level goes up and down, in both positive and negative territory. Soon I realized the key was the bottom-most point in this trajectory. If you start from there, everything will work out. I wondered briefly: say x_i \geq k. Is there a solution with tank O(k) in size? Not true.
  
• Fuses. Known puzzle. I can even do any arbitrary fraction p/q with two fuses (you need infinite matches).
• Integers and Rectangles. Known puzzle. Vaguely remember a solution using Green's Theorem.
• Tipping the scale. Watches on the table. Path on a chessboard. Could not get into the spirit of these problems. Realized scale tipping is trivial if each weight had exactly one pupil's name. In general, some set averaging I am sure.
  
• Exponent on exponent. Seen before. e^{1/e}.
• Soldiers in the field. An odd number of soldiers are stationed in a field, all pairwise distances are distinct, each soldier watches the nearest other solider. Prove that at least one soldier is unwatched. Start making a graph, nodes are soldiers, make an edge from i to j if i watches j. With n=2 soldiers, they watch each other. With n=3, it is clear, the third watches one of the other two who are watching each other, and one can not create a triangle (if you label the edges a,b,c, two edges will give a total order on the distances which will contradict the third edge). So, in general, I wanted to prove that with odd n, you can't have a full circle and any circle will be partial. You can create a path with n-1 nodes and when I tried to put the nth node to complete the circle properly, I realized that the edge from the nth to one of the other nodes will break the path at the other node. So, forget about the circles etc, just take two nodes at a time that have the shortest distance between them, and we can repeatedly remove them to give the argument (if they are connected to the rest of the nodes, trivially one can conclude someone is not being watched). Cool. Wondered for sometime with the variation: Say node i points to node j if i is the nearest neighbor of j, does this property hold? I went thru n=3 case but then realized that now the graph may not even have n edges. So, not clear this is a well formed problem. Abandon.
• Intervals and distances: skipped. This looked like I actually have to do some calculation, something like the number of triangles * smthg \geq 1. Summing to 15. Known. I use this puzzle as an example of something where I can convince the audience of the answer without mathematically proving it to them. Locker doors. Page 13. Known. Zeros, Ones and Twos: I was asked (a) part of this problem and remember the pigeonholing answer many of us came up with.
• Sums and Differences. Given 25 different positive numbers, prove that you can choose two of them such that none of the other numbers equals either their sum or their difference. Say the numbers are x_1 ... x_25. It is easy to pick two numbers so their sum is not in the collection (x_1, x_25), the trick is with the difference. So, you can not pick x_1 and x_25 if x_24 is their difference, and so on. So, I considered what I would do with numbers x, 2x, 3x, ... ,25x. Seemed like difference of any two of them is in the set, and after a while realized the trick is to make sure the difference IS one of the numbers chosen, so something like 12x and 24x will do. Now, this logic can be generalized to arbitrary numbers (not just multiples of x). Choose x_12 and x_24. Nothing special about 25. That is misleading.
  

STOP. I am going to vacation now. If I get back to Page 14 and continue, will let you all know.