The following game was discussed in class:

       On the table there is a stack of n boxes. We want to 
       break it into n  stacks of 1 box each. The only type 
       of move we are allowed is to pick a stack and split 
       it into two smaller stacks. In every such move we earn
       a number of points, which is equal to the product of 
       the sizes of the two smaller stacks. What is the best 
       strategy to play this game?

In class we proved by induction the surprising fact that all 
strategies yield the same score: n(n-1)/2 points. Another way 
to prove this is the following:

       At any point during the game, consider the corresponding 
       "adjacency graph", that has  n  vertices (one for each 
       box) and an edge between two vertices iff the corresponding 
       boxes are in the same stack at that particular point.

Originally the adjacency graph is just the complete graph on  n
vertices. At the end of the game, it is the empty graph on  n
vertices. In general, at every point during the game the number of 
its connected components equals the number of stacks on the table. 
Moreover, every move decreases the number of edges in the graph by
exactly the number of points that we earn. It follows that our final
score will be equal to the total decrease of the number of edges, 
which is

  (edges in complete graph) - (edges in empty graph) = n(n-1)/2

no matter what our strategy has been.


--- One could build a problem on this setting, asking things about
the state machine that has all adjacency graphs as its states. We can
consider several functions of the number of edges, number of 
connected components, number of stacks, number of points and ask
whether they are increasing/decreasing/etc.