Induction (under construction)
induction by the method of undetermined coefficients
Name and conquer
completing the square – see e.g. the quadratic formula
If you have a transformation, look for an invariant!
Solution. With n people, label them according to how many they know. This will range from 0 to n-1. But If someone knows no-one (label 0), no-one knows n-1. By the pigeonhole principle, there are n people with n-1 labels, and at least 2 must know the same number of people.
Extremal principle: Pick an object which maximizes/minimizes some function.
Solution: Consider all partitions of the Parliament into two houses and, for each partition, count the total number E of enemies each member has in his house. The partition with minimal E has the required property. If some member had two or more enemies in his house, then he would have one enemy at most in the other house. By placing him in the other house, we could decrease the minimal E, which is a contradiction.
(for odd .
Sophie Germain’s identity:
Substituting in , , and :
Search for a pattern.
Draw a figure.
Formulate an equivalent problem.
Modify the problem.
Choose effective notation.
Divide into cases.
Argue by contradiction.
A. None. With this chess-board colouring, the 2nd, 4th and every even-numbered room visited is white. But there are an even number of rooms, and the last room on such a path would be even and black.
Loren C Larson – Problem-solving through problems (1983)
Arthur Engel – Problem-solving Strategies (2008)