All books

Professional

Apps About Coach Log in Start reading

Quantitative Finance · Glossary

What is Invariant method?

Definition 12.1 The Interview Book · Chapter 12 — Brainteasers and Logic

The invariant method solves a puzzle about a process by finding a quantity that no allowed move changes (a parity, a sum modulo mm, a product, a colouring count); every reachable state shares the starting value, so a state with another value is unreachable, and the final state is determined.

Examples

Example 12.3 (The hat line)

With kk colours numbered 0,…,k−10, \dots, k-1, the last person in the line (who sees everyone else) announces the sum of the colours in front modulo kk. Each following person knows that sum, hears every answer given after the first, sees everyone in front, and so can subtract to find their own colour. All but the first are right, whatever kk: the invariant is the announced sum.

Read in context →