Assignment #4
Theme: Backtracking and Gray codes
Assigned:October 27, 2015.
Due:November 6, 2015.
Reminder: homework should be handed in at the beginning of class
and should be in latex (or tex).

From the backtracking handout: Problem 4.

From the backtracking handout: Problem 10.
Turn in a program listing and the output of your program.

How many moves are required to solve the Chinese Rings Puzzle if there are $n$ rings?
I.e., what is the rank of $11 \cdots 1$ in the BRGC?
Express your answer as simply as possible (no summations).

What is the first number in the 10 billion odd number dictionary with Winkler's rules
(spaces don't count; i.e., are compressed)? What is the last number with my rules?

Prove the existence of a Gray path for the set of all binary strings of length $n$ with no $00$ substring.
How many such strings are there?
Why didn't I ask for a Gray cycle? Are there any values of $n$ for which Gray cycles exist?
HINT: The nonexistence of Gray cycles often boils down to a parity problem in the underlying
bipartite graph.