The Math for Computer Science mascot, Theory Hippotamus, made a startling discov

Question

The Math for Computer Science mascot, Theory Hippotamus, made a startling discovery while playing with his prized collection of unit squares over the weekend. Here is what happened. First, Theory Hippotamus put his favorite unit square down on the floor as in Figure 5.9 (a). He noted that the length of the periphery of the resulting shape was 4, an even number. Next, he put a second unit square down next to the first so that the two squares shared an edge as in Figure 5.9 (b). He noticed that the length of the periphery of the resulting shape was now 6, which is also an even number. (The periphery of each shape in the figure is indicated by a thicker line.) Theory Hippotamus continued to place squares so that each new square shared an edge with at least one previously-placed square and no squares overlapped. Eventually, he arrived at the shape in Figure 5.9 (c). He realized that the length of the periphery of this shape was 36, which is again an even number. Our plucky porcine pal is perplexed by this peculiar pattern. Use induction on the number of squares to prove that the length of the periphery is always even, no matter how many squares Theory Hippotamus places or how he arranges them.

Explanation / Answer

Consider the fact that when placing a unit square, if an edge of the square placed touches an edge of the existing arrangement, two edges can not be part of the periphery. So start with a shape with an even number of edges. Place a unit square. Either 0,1, 2, 3, or 4 edges of the square placed must touch the existing shape. If 0 touch, you have 4 new edges on the periphery, makes an even number. If 1 touches, you have 3 new edges on the periphery from the square placed and 1 less edge from the existing shape, adding 2 to the number of edges, still an even number. If 2 touch, you have 2 new edges and 2 fewer existing edges, leaving the number of edges unchanged (still even). Similar argument for 3 touching or all 4 touching. Since this is true however many even edges you started with, this proves the argument by induction.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.