multiple proofs

[gusl]

This note by John McCarthy from 1964 is about a sort of obfuscated-proof-contest.

This Stanford AI Memo of 1964 illustrated the fact that a theorem may not be easy to prove if the proof involves an idea not expressible in the language in which the theorem is stated.

Here's an exercise for the readers of this blog:

Prove that all Manhattan polygons (i.e. all lines are either horizontal or vertical) have an even number of corners. (credits to someone I'll leave anonymous just in case)

How many distinct proofs can you come up with? (What counts as distinct proofs is an interesting question to formalize (proof identity))

Comments

[marknau.livejournal.com]

Thumbnailing the first few that lept to mind:
1) Start at and edge and track compass heading. All corners change facing by 90 degrees. Therefore even number of corners to come back to same facing.
2) Transform concave corners into convex corners, converting 3 corners into 1, which maintains the mod2 number of conrners. Show it eventually transforms into a rectangle with 0mod2 corners.
3) Show that each H piece and the 2 corners formed by its neighboring V pieces fill up the set of all corners.
4) Chop rectangles off the shape, each time converting 3 corners to 1. End with a rectangle. Similar to #2.
5) Pair each corner with its opposite-corner directly "across" the shape. Show each corner has a unique anti-corner, and that it is its anti-corner's anti-corner. Not immediately clear to me how to pair them up, though.