Problem of the Week 942

Can Bob Determine Alice's Numbers?

Alice chooses 101 distinct real numbers, places them in order so that a1 < a2 < ...< a101, and tells Bob their sum, the sum of their squares, and all the 99 differences a3-a1, a4-a2, ...,a101-a99. Can Bob always determine the numbers?

Source: Dirk Laurie, South Africa
BONUS PROBLEM

Here is a bonus problem. It is a bit too hard for a PoW, but working out a solution gave me much pleasure over the summer, so here's your chance to enjoy it too. It is from an Iranian contest and appeared in Crux Mathematicorum.

True or False: Every solvable maze is solvable using left and right turns only.

Notes and Clarifications:

A "maze" is a collection of rooms in the plane, with the rooms connected by doors. One room is marked "S" for start, another is marked "F" for finish.

The maze is "solvable" if there is a path from S to F.

Taking a "left turn" means: "upon entering the room, follow the wall on your left and exit by the first door you come to". "Right turn" is defined similarly.

COMPLICATION: One has to be careful defining the maze. We want to be able to think of the maze as being simply a planar graph. One vertex is marked S, one is marked F. A left turn means coming into a vertex along an edge and taking the first edge one comes to on the left. Similarly for right. I think if we say that our maze consists of rectangular rooms with doors into other rooms, and with the property that each rectangle has nothing in its interior (no "rooms within rooms"), then I am in the situation I want.

Moreover, at the start one is in the "room" corresponding to vertex S with one's back against a wall of the room. This is so that L and R are well-defined at the very start.

© Copyright 2001 Stan Wagon. Reproduced with permission.


9 October 2001