Lesson 1

How can we be certain that a solution is not just good, but the best possible? In this section, we develop techniques for proving optimality—showing that no alternative solution can outperform the one at hand.

A proof of optimality consists of two parts. To prove that the optimal value of some objective function is \(M\), one needs to:

1. prove that there exists an object for which the value of the objective function is \(M\);
2. prove that there does not exist an object for which the value of the objective function is better than \(M\) (or, in other words: prove that for any other object, the value of the objective function will not be better than \(M\)).

For example, we already know that the maximum number of knights on a chessboard that do not attack each other is 32: there exists an arrangement with exactly 32 knights (see the figure below), and there does not exist an arrangement with more than 32 knights (because all 64 cells of the board can be divided into 32 pairs, so that each pair can contain at most one knight).