2 - Background

Summary

In Hungarian Problem Book III, we covered a large number of theorems in basic mathematics. Not much else is needed to tackle the problems in the current volume. We list them again without further discussion, and add two sections on theorems not covered in the earlier volume.

Theorems in Combinatorics

Principle of Mathematical InductionIf S is a set of positive integers such that 1 ∈ S, and n + 1 ∈ S whenever n ∈ S, then S is the set of all positive integers.

Well Ordering PrincipleAny non-empty set of positive integers has a minimum.

Extremal Value PrincipleEvery non-empty finite set of real numbers has a maximum and a minimum.

Mean Value PrincipleIn every non-empty finite set of real numbers, there is at least one which is not less than the arithmetic mean of the set, and at least one not greater.

Pigeonhole PrincipleSeveral pigeons are stuffed into several holes. If there are more pigeons than holes, then at least one hole contains at least two pigeons. If there are more holes than pigeons, then there is at least one empty hole.

Finite Union PrincipleThe union of finitely many finite sets is also finite.

Parity PrincipleThe sum of two even integers is even, the sum of two odd integers is also even, while the sum of an odd and an even integer is odd. Moreover, an odd integer can never be equal to an even integer.

Multiplication Principle |A × B| = |A| · |B|.