Iterative Optimizers

Appendix

A.1. Pigeonhole principle and monotonicity

In its simple form, this can thus be stated as:

CLAIM A.1.– If n objects are placed in m boxes and n > m, then at least one box contains several objects.

Currently (June 2018), the oldest known application is in the book by Jean Leurechon in 1622 (Lereuchon 1692), regarding the fact that there necessarily exist two women who have the same number of hairs.

Here, if we define , then this principle provides a possible demonstration to the following small theorem:

THEOREM A.1.– There are only two strictly monotonic maps I_N in I_N: f₁ (x) = x and f₂ (x) = 1 − x.

It is obvious that these two maps are strictly monotonic. We assume that there exists another one g, increasing for example. We assume the strict inclusion g (I_N) ⊂ I_N. Let m = |g (I_N)|. This is the number of “boxes”. Since we have |I_N| = N > m, at least one box contains two elements of g (I_N). In other words, at least two or more elements x₁ and x₂ of I_N have the same value by g and monotonicity cannot be strict. One must therefore have g (I_N) = I_N and g can be seen as performing a permutation of the elements of I_N. However, the only permutation preserving the order of the elements is the identity, and therefore, g = f₁. A similar reasoning would show that if g is decreasing, then g = f₂.

REMARK A.1.– It can be specified that if there were pairs such as g (x₁) = g (x₂), then ...