Problem:
Determine whether it is possible to write the numbers on the edges of the grid of squares shown, one number to each edge, such that the sum of the six numbers on every path of minimal length from the upper left corner to the lower right corner is the same.
Solution:
It is possible, and two especially simple solutions are shown. To check that they work without going through every path, one can use the following strategy: First notice that in each of the nine unit squares, the sum of the left and bottom edges equals the sum of the top and right edges. Now, given any path that includes a rightward move (R) followed by a downward move (D), we can replace RD by DR without changing the sum of the edges. Now a minimal path consists of three R's and three D's, and each can move past each at most once; so after at most nine steps the path will be converted to DDDRRR. This proves that all paths have the same sum.
