Full binary chocolate trees

Something weird happened on the way out of lecture.

I had presented two problems in complete induction, a proof technique. The first was about full binary trees --- trees in the graph-theory sense with nodes that have either 0 or two children. The second was about how to break up chocolate bars.

 I should have suspected there would be a connection when I remarked, a couple of times, that "non-empty full binary trees" was quite a mouthful: the result to be proved did not apply to a full binary tree with zero nodes (an empty full binary tree, so to speak). Except for the zero case, full binary trees have an odd number of nodes, and we prove it using the fact that subtrees are also full binary trees.

 The chocolate result is that you can break up a rectangular array of n chocolate squares into individual squares with n-1 "breaks." Breaks have to cleave right across, either lengthwise or widthwise, and although the result applies to a somewhat wider class than rectangular arrays, you can find counterexamples if you allow weird cases of three chocolate bars pasted together precariously on their edges.

 I'm working my way through a line of students after class who have questions or comments. One is staring into space, so I ask what's up. "I'm thinking about graph theory." The student draws a tree with the original chocolate bar labeling the root and as you break it into two, you label the two children with the resulting bars. And so on, until you have individual squares.

 The resulting tree is a full binary tree. A non-empty one, since who would go about breaking up zero chocolate squares? Applying the chocolate result to trees we see immediately that a non-empty full binary trees have one more leaf than internal node.

 The most wonderful part of the encounter was that my student assumed that I was leading the class toward this connection when I presented the two topics together. I hadn't, but I was flattered by the assumption.