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.

## 2 comments:

I figured this one out pretty much from the get-go, at least after having been swindled by the wording. Keep coming up with these great problems, dear!

how much more time before the next one ???

Post a Comment