Problems

Questions with room for experiments, examples and more than one useful route.

Try the problems before opening an interactive or writing a program. Small cases, diagrams and deliberately chosen failures are all legitimate beginnings.

01

Counting boundary bits

The sixteen four-bit tiles contain thirty-two (1)s in total. If all boundary bits of a (4) arrangement are (0), what does this force about the number of active shared edges inside the board? What necessary conditions can you extract before attempting a construction?

02

Local rules, multiple loops

Construct an arrangement in which the boundary closes and every adjacent pair matches, but the drawing has more than one connected component. What is the smallest board on which this can happen if repeated tiles are allowed?

03

Sliding between valid boards

Start and finish with valid connected configurations, but allow arbitrary intermediate configurations. Which features of the labelled 15-puzzle are unchanged by every legal slide? How would you compute the invariant without first finding a path?