In Stitches

After doing the back-stitching on a few of the letters in this counted cross stitch pattern, I wondered if there would always be an even amount of stitches in the outline of a block shape.

Problem:

Define a "block shape" as any shape that can be created by coloring in squares on graph paper. Each square in a multi-square block shape must share at least one side with another square in that shape. Call the length of a square on the graph paper one unit. Prove or disprove: the perimeter of a block shape will always be an even number of units.


Solution:

I will prove that the perimeter is always an even number of units using the Principle of Mathematical Induction.

• Base case: consider a one-square block shape. Its perimeter is 4 units - one for each side. Since 4 is even, the proposition holds for the base case.


• Inductive hypothesis: assume that a block shape consisting of n squares has an even perimeter.


• Deductive step: What happens when I add a square to the n-block shape?
  
  
  
  • If the new square is touching exactly one other square, then I am taking away 1 unit from the perimeter and adding 3 units. That's a net gain of 2 units, so the perimeter remains even.
  
  
  • If the new square is touching exactly two other squares, I am taking away 2 units and adding 2 units to the perimeter. The net change is 0, so the perimeter remains even.
  
  
  • If the new square is touching exactly three other squares, I am reducing the perimeter by 3 units and adding 1. The net loss is 2 units, so the perimeter remains even.
  
  
  • If the new square is touching exactly four other squares, I am taking away 4 units from the perimeter and adding none. The perimeter remains even.
  
  In each possible case, the perimeter of the (n+1)-block shape remains even.

Therefore, by the Principle of Mathematical Induction, the perimeter of a block shape will always be even.