Invariant Method

1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8
9 10 11 12 9 10 11 12
13 14 15 13 15 14
 A Chessboard Problem

A Bishop can only move along a diagonal

Can a bishop move from its current position to the question mark?

?
 A Chessboard Problem

A bishop can only move along a diagonal

Can a bishop move from its current position to the question mark?

Impossible!
?

Why?
 A Chessboard Problem
Invariant!

1. The bishop is in a red position.

2. A red position can only move to

? a red position by diagonal
moves.

3. The question mark is in a white

position.

4. So it is impossible for the

bishop to go there.

This is a simple example of the invariant method.

 Domino Puzzle

An 8x8 chessboard, 32 pieces of dominos

Can we fill the chessboard?

 Domino Puzzle

An 8x8 chessboard, 32 pieces of dominos

Easy!
 Domino Puzzle

An 8x8 chessboard with two holes, 31 pieces of dominos

Can we fill the chessboard?

Easy!
 Domino Puzzle

An 8x8 chessboard with two holes, 31 pieces of dominos

Can we fill the chessboard?

Easy??
 Domino Puzzle

An 4x4 chessboard with two holes, 7 pieces of dominos

Can we fill the chessboard?

Impossible!
 Domino Puzzle

An 8x8 chessboard with two holes, 31 pieces of dominos

Can we fill the chessboard?

Then what??
 Domino Puzzle

An 8x8 chessboard with two holes, 31 pieces of dominos

Can we fill the chessboard?

 Domino Puzzle
Invariant!

1. Each domino will occupy one

white square and one red
square.

2. There are 32 blue squares but

only 30 white squares.

3. So it is impossible to fill the

chessboard using only 31
dominos.

This is another example of the invariant method.

 Invariant Method

1. Find properties (the invariants) that are satisfied

throughout the whole process.

2. Show that the target do not satisfy the properties.

3. Conclude that the target is not achievable.

In the rook example, the invariant is

the colour of the position of the rook.

In the domino example, the invariant is that

any placement of dominos will occupy the same
number of blue positions and white positions.
 The Possible

We just proved that if we take out two squares of

the same colour, then it is impossible to finish.

What if we take out two squares of different colours?

Would it be always possible to finish then?

Yes??
Prove the Possible

Yes??
Prove the Possible

The secret.
Prove the Possible

The secret.
 Fifteen Puzzle

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15

Move: can move a square adjacent to the empty square

to the empty square.
 Fifteen Puzzle

1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8
9 10 11 12 9 10 11 12
13 14 15 13 15 14
Initial configuration Target configuration

Is there a sequence of moves that allows you to start

from the initial configuration to the target
configuration?
 Invariant Method

1. Find properties (the invariants) that are satisfied

throughout the whole process.

2. Show that the target do not satisfy the properties.

3. Conclude that the target is not achievable.

What is an invariant in this game??

This is usually the hardest part of the proof.

 Hint

1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8
9 10 11 12 9 10 11 12
13 14 15 13 15 14
Initial configuration Target configuration

((1,2,3,…,14,15),(4,4)) ((1,2,3,…,15,14),(4,4))

Hint: the two states have different parity.

 Parity
Given a sequence, a pair is “out-of-order” if the first element is larger.

More formally, given a sequence (a1,a2,…,an),

a pair (i,j) is out-of-order if i<j but ai > aj.

For example, the sequence (1,2,4,5,3) has two out-of-order pairs, (4,3) and (5,3).

Given a state S = ((a1,a2,…,a15),(i,j))

Parity of S = (number of out-of-order pairs + row) mod 2

row number of the

empty square
 Hint

1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8
9 10 11 12 9 10 11 12
13 14 15 13 15 14
Initial configuration Target configuration

((1,2,3,…,14,15),(4,4)) ((1,2,3,…,15,14),(4,4))

Parity of S = (number of out-of-order pairs + row) mod 2

Clearly, the two states have different parity.

 Invariant Method
Parity is even

1. Find properties (the invariants) that are satisfied

throughout the whole process.

2. Show that the target do not satisfy the properties.

3. Conclude that the target is not achievable.

Parity is odd

Invariant = parity of state

Claim: Any move will preserve the parity of the state.

Proving the claim will finish the impossibility proof.

 Proving the Invariant

Parity of S = (number of out-of-order pairs + row) mod 2

Claim: Any move will preserve the parity of the state.

? ? ? ? ? ? ? ?
? a ? ? a ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?

Horizontal movement does not change anything…

 Proving the Invariant
Parity of S = (number of out-of-order pairs + row) mod 2

Claim: Any move will preserve the parity of the state.

? ? ? ? ? ? ? ?
? a b1 b2 ? b1 b2
b3 ? ? b3 a ? ?
? ? ? ? Row number has ? ? ? ?
changed by 1

To count the change on the number of out-of-order pairs, we can distinguish

4 cases, depending on the relative order of a among (a,b1,b2,b3).
 Proving the Invariant
Parity of S = (number of out-of-order pairs + row) mod 2

Claim: Any move will preserve the parity of the state.

? ? ? ? ? ? ? ?
? a b1 b2 ? b1 b2
b3 ? ? b3 a ? ?
? ? ? ? Row number has ? ? ? ?
changed by 1

Case 1: when a is largest, then the number of out-of-order pairs will

decrease by three, and since the row number is changed by one,
the parity is still the same.
 Proving the Invariant
Parity of S = (number of out-of-order pairs + row) mod 2

Claim: Any move will preserve the parity of the state.

? ? ? ? ? ? ? ?
? a b1 b2 ? b1 b2
b3 ? ? b3 a ? ?
? ? ? ? Row number has ? ? ? ?
changed by 1

Case 2: when a is the second largest, then the number of out-of-order pairs
will decrease by one, and since the row number is changed by one,
the parity is still the same. (The remaining case analysis is the same.)
 Proving the Invariant
Parity of S = (number of out-of-order pairs + row) mod 2

Claim: Any move will preserve the parity of the state.

? ? ? ? ? ? ? ?
? a b1 b2 ? b1 b2
b3 ? ? b3 a ? ?
? ? ? ? Row number has ? ? ? ?
changed by 1

If there are (0,1,2,3) out-of-order pairs in the current state, Difference

there will be (3,2,1,0) out-of-order pairs in the next state. is 1 or 3.

So the parity stays the same! We’ve proved the claim.

 Fifteen Puzzle

1 2 3 4 15 14 13 12
5 6 7 8 11 10 9 8
9 10 11 12 7 6 5 4
13 14 15 3 2 1
Initial configuration Target configuration

Is there a sequence of moves that allows you to start

from the initial configuration to the target
configuration?
 Fifteen Puzzle

1 2 3 4 15 14 13 12
5 6 7 8 11 10 9 8
9 10 11 12 7 6 5 4
13 14 15 3 2 1
Initial configuration Target configuration

Number of out-of-order pairs = 0 Number of out-of-order pairs

= 14 + 13 + 12 + … + 1
Row of empty square = 4 = 14(13)/2 = 91

Parity is even. Row of empty square = 4

Parity is odd.
Impossible!
 Fifteen Puzzle

If two configurations have the same parity,

is it true that we can always move from one to another?

YES, good project idea.

http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/15-puzzle.pdf
 K=4

x=0

Remember the checker game that we have seen before?

 K=5

This can also be solved by the invariant method.

Sorry there are no slides for this proof.

The proof can be found in “Mathematical Gems II” by Honsberger.

There are three books on Mathematical Gems and all are excellent.
 Covering with Trominoes

Can you cover a 8X8 board with straight trominoes?

No, since the board has 64 squares and each tromino covers 3.

So, lets remove one corner so that the board now has 63 squares.

Can we now, cover with straight trominoes?

Lets try
 Lets try our coloring trick.

Color board so that

each tromino colors 3
different colors

Of the 4 corners, say 2

are red and one each
are blue, yellow

Rotate board so that

missing corner is blue/
yellow

Now we have 22 reds, 21 yellows and 20 blues!!

 Remarks and References

Another interesting application of the invariant method is the Nim game.

See http://en.wikipedia.org/wiki/Nim.