Seminar

Please join MSRIs Directorate for a fun talk led by Dr. Elwyn Berlekamp: 

One version of the classic traveling salesman problem seeks to determine whether or not, in any given graph, there exists a "Hamiltonian path" which traverses every node exactly once.   In the general case, this problem is well-known to be NP Hard.   In one interesting subclass of this problem, the nodes are taken to be the first N integers, {1,2,3,...,N}, where there is a branch between J and K iff J+K is in a specified set S = {S[1], S[2], S[3],...,S[M]}.   Or, given S, for what values of N does a Hamiltonian path exist?  How fast can the elements of S grow such that there exist solutions for infinitely many N?

The answer to the second question turns out to be a close relative of the Fibonacci numbers, for which we construct solutions by observing the path of a billiard ball which travels at 45 degree angles to the sides of its table.  Using the same billiard ball methodology, we also find some particular solutions when S is the set of squares or the set of cubes.