Look for invariants!

Looking for invariants: a surprisingly versatile problem-solving trick.

A huge part of problem solving in math boils down to knowing a few tricks. The right trick can transform an impossible-sounding problem to a trivial one.

In this issue, I’ll explain one such trick. This trick is very versatile and it can be used in many different contexts.

This trick is simple: “look for invariants!”

What is an invariant? An invariant, as the name suggests, is a quantity in a problem which does not change. Let’s test it out on a problem.

Problem

At first, a room is empty. Each minute, either one person enters or two people leave. After exactly 3¹⁹⁹⁹ minutes, could the room contain 3¹⁰⁰⁰ + 2 people?

This is a hard problem and you might want to think about it for a few minutes before you continue.

If you’re still reading, I’m assuming that you’ve thought about the problem for a bit. You might try doing some sample calculations, but since 3¹⁹⁹⁹ is so big, this won’t get very far.

Enter our trick: looking for invariants

Let’s see how looking for invariants can solve our problem. Suppose there are n people in the room. The next minute, there will either be n-1 people or n+2 people in the room. What is the invariant here? The numbers n-1 and n+2 are congruent modulo 3. Therefore, at any fixed time, all the possible values for the population of the room differ from one another by multiples of 3.

After exactly 3¹⁹⁹⁹ minutes, one possible answer for the number of people in the room is 3¹⁹⁹⁹ (if one person enters the room each minute). This is a multiple of 3, so all the possible populations for the room have to also be multiples of 3. Therefore 3¹⁰⁰⁰ + 2 will not be a valid population. Done!

By looking for invariants, we solved the problem immediately. It was so easy it almost felt like cheating.

(This example is from Chapter 3 of Paul Zeitz’ book “The Art and Craft of Problem Solving”. This is a really amazing book and I’d highly recommend reading it.)

Problem of the week

Now it’s your turn to practice. Here is a challenge problem for this week. Try to solve it by looking for invariants.

Show that if every room in a house has an even number of doors, then the number of outside entrance doors must be even as well.

If you have a solution to this challenge problem, submit it here for a chance to be featured in the next issue of this newsletter.

Solution from last week

See here for the solution to last week’s problem. (Shoutout to Ankit Agarwal from the Bay Area whose solution is being featured this week!)

Thanks for reading and happy learning! Until next time,

Adithya