Invariant
Intermediate

Lecture Notes

An **invariant **is a quantity or property that remains constant throughout a series of transformations. This concept is widely utilized and studied across various disciplines, including discrete mathematics, which is a compulsory course for computer science majors.

A brain teaser related to invariants might not seem academic at first glance. Instead, it assesses the candidate's ability to first recognize that the problem can be solved by applying the concept of an invariant and then to identify this invariant.

The example below is a classic one. Such problems often present an infinite number of possible transformations. Many candidates might manage an educated guess to assert that the goal is unachievable, but they fail to provide clear and convincing reasoning.

Examples

(4645) $\textbf{Coin Flipping}$ There are $9$ coins on the table, all heads up. In each operation, you can flip any two of them. Is it possible to make all of them heads down after a series of operations? If yes, please list a series of such operations. If no, please explain. |