eduKate Singapore

VIEW THIS AS

Auto mode follows the Route Engine until you choose a viewpoint.

YOU ARE HERE

ROUTE CHECK

CONNECTED TO

WHAT NEXT

Use the canonical route for this room, or HELP if you are unsure.

Next useful routeCanonical hubHELP

Mathematics in Bukit Timah | Mathematical Invariants, Parity Puzzles and Impossible Moves

—

by

eduKate Asia
Illustration of two students discussing mathematical reasoning with square tiles and a notebook.

Can an ordinary 8×8 checkerboard be covered completely with 1×2 dominoes after two diagonally opposite corners are removed? The board has 62 squares left, and 31 dominoes cover exactly 62 squares, so area alone suggests it might work. Yet it is impossible. The missing opposite corners have the same checkerboard colour, leaving unequal counts of black and white squares. Every domino must cover one of each colour. That unchanging colour-balance rule proves the impossibility.

This Mathematics in Bukit Timah article explains mathematical invariants, parity, checkerboard colouring, modular arithmetic, grid-walk constraints, switch puzzles, sliding tiles, conserved sums, monovariants, proof by contradiction and the difference between impossibility and existence. Every board, student, coin, switch and path is fictional. The puzzles do not describe actual Bukit Timah buildings, pupil behaviour, transport routes, classroom outcomes or physical accessibility.

Quick answer: An invariant is a property that remains unchanged after every allowed operation. If an initial state has invariant value A and a proposed target has a different value B, the target is unreachable using those operations. For the corner-removed checkerboard, the black–white imbalance is an obstruction: a domino always removes one black and one white square, so a board with 30 of one colour and 32 of the other cannot be tiled by 31 dominoes.

Article contents

Original mathematics classroom illustration with tiles and counterexamples for fictional invariants, checkerboard colour balance and parity puzzles.

Why a local puzzle can have a global proof

Trying hundreds of domino arrangements might fail to find a tiling.

But failure to find one does not prove that none exists. Another arrangement may have been overlooked.

An invariant offers a different approach: find a quantity every legal move preserves, then show the desired final condition disagrees with that quantity. One short proof rules out all arrangements simultaneously.

Bukit Timah is the educational context

A learner near Sixth Avenue, Beauty World or King Albert Park can explore these puzzles with graph paper and counters.

All board dimensions and operations below are constructed mathematics. We are not examining an actual property, local pedestrian route or real classroom activity.

The important transferable skill is identifying a mathematical constraint that survives every permitted move, not making claims about any real local layout.

Define a state before looking for an invariant

A state records enough information to describe the current puzzle configuration.

For a board, it may include which squares remain uncovered. For a switch puzzle, it may specify which lamps are on.

An operation is one allowed state change. An invariant must survive every operation permitted by the rules, not merely a favourite example.

What does invariant mean?

A function I of the state is invariant when I(new state)=I(old state) for every legal move.

Once this is proved, the value stays unchanged after any finite sequence of moves, because equality can be applied repeatedly.

This is a formal property of the move system. An apparent numerical pattern in a few trials is only a clue until all legal move types are checked.

Worked example 1: a simple even-number move

Start with integer x=4. An allowed move changes x by +2 or −2.

Every move preserves whether x is even or odd, because an even number plus or minus two stays even.

Thus x can reach six or two, but cannot reach five under these operations. Parity is the invariant.

Why parity is useful

An integer is even when it is divisible by two and odd otherwise.

In modular notation, even integers have remainder zero modulo two; odd integers have remainder one.

If every legal move changes an integer by an even number, its remainder modulo two never changes. That makes parity one of the simplest and most powerful invariants.

Worked example 2: a parity equation

Suppose x starts at zero and each move adds four or subtracts six.

Both possible changes are even. Therefore x remains even after every move.

The target x=7 is odd, so it is impossible. The proof does not need to know how many moves are attempted.

An invariant does not necessarily determine every reachable state

If x begins at zero and allowed moves are +4 and −6, parity proves that odd targets cannot be reached.

But evenness alone does not tell us which even targets are reachable in a constrained number of moves.

An invariant often provides a necessary condition for reachability, not a complete constructive solution.

The checkerboard’s two colours

An ordinary 8×8 chessboard has alternating black and white squares.

Every row contains four of each colour. Across eight rows, there are 32 black and 32 white squares.

These counts are determined by the colouring pattern, independently of the sizes of any dominoes placed on the board.

Worked example 3: total board area

An 8×8 board contains 8×8=64 unit squares.

Removing two squares leaves 62.

A 1×2 domino covers two squares, so exactly 31 dominoes would be needed for a full tiling by area alone. The integer count is necessary, but it does not settle whether a tiling is geometrically possible.

Diagonally opposite corners have the same colour

Label board positions by row and column numbers from one through eight.

A square’s colour can be classified by the parity of row+column. For example, even sums may be called black.

Opposite corners (1,1) and (8,8) have sums two and sixteen, both even. Therefore the two removed corners have the same colour.

Worked example 4: count the remaining colours

Suppose the removed corners were black.

The original board had 32 black and 32 white squares. After removing two black corners, it has 30 black and 32 white.

The total remains 62. The difference between colour counts is two, which will be the crucial obstruction.

Every domino covers opposite colours

A 1×2 domino occupies two orthogonally adjacent board squares.

Moving one square horizontally or vertically changes row+column parity by one, so neighbouring squares have opposite colours.

Therefore every legal domino covers exactly one black and one white square, no matter where or how it is positioned.

Worked example 5: count colour coverage by 31 dominoes

Thirty-one dominoes cover exactly 31 black and 31 white squares if they cover distinct board squares without overlap.

But the corner-removed board has 30 black and 32 white.

Those requirements conflict. Therefore no arrangement of the dominoes can tile the entire remaining board.

Why this is a complete impossibility proof

The argument does not depend on any particular attempted tiling.

It uses a property true of every legal domino placement and compares it against the board’s required colour totals.

Because the totals cannot match, an arrangement is impossible regardless of how cleverly the dominoes are rearranged. This is much stronger than unsuccessful trial and error.

What if two corners of opposite colours are removed?

Then the remaining board has 31 black and 31 white squares.

The simple colour imbalance obstruction disappears.

But this does not, by itself, prove a tiling exists for every possible pair of removed opposite-colour squares. A necessary balance condition is not automatically a complete existence theorem for an arbitrary board shape.

Worked example 6: an easily tilable changed board

Take the 8×8 board and remove two adjacent squares from the same row, one black and one white.

For an appropriate pair such as two adjacent squares at the end of a row, the remaining six squares of that row can be tiled with three horizontal dominoes.

Each of the other seven full rows can be tiled with four horizontal dominoes. This constructs a tiling and independently proves existence for that particular changed board.

A counterexample to sufficiency is different from an invariant

The checkerboard colouring proves certain boards cannot be tiled when their colour counts are unequal.

When counts are equal, the colouring test simply does not rule out a tiling.

To establish existence, one may construct a tiling or use a stronger theorem. The distinction between necessary and sufficient conditions is central to rigorous problem solving.

A 5×5 board illustrates area parity first

A 5×5 board has 25 unit squares.

Every 1×2 domino covers exactly two. Any number of such dominoes covers an even number of squares.

Since 25 is odd, the entire 5×5 board cannot be tiled by dominoes. This impossibility needs only area parity, without a two-colour count.

Worked example 7: why area alone can be decisive

Suppose k dominoes cover a board perfectly.

The number of covered squares must equal 2k, which is even.

A board with 25 squares would require 2k=25, impossible for integer k. Therefore no perfect domino tiling exists.

When a weak invariant is not enough

For the 8×8 board with two same-coloured corners removed, the remaining area 62 is even.

Area parity therefore allows the possibility but cannot settle it.

The stronger black–white balance argument rules it out. This illustrates why mathematicians sometimes need more refined invariants than simply even versus odd.

A three-colour or modular colouring can be stronger

Some tiling puzzles involve pieces covering three or more squares.

Colouring cells by column modulo three, by diagonal classes or by another periodic pattern may reveal constraints that ordinary black–white parity cannot detect.

The colouring must be chosen to interact predictably with every legal tile placement. An attractive pattern alone is not a proof.

A move that flips exactly two switches

Imagine five fictional lamps arranged in a row, initially all off.

A legal move selects two adjacent lamps and toggles both: on becomes off, off becomes on.

The number of lamps currently on can change by minus two, zero or plus two. Therefore its parity remains unchanged.

Worked example 8: two-switch move from all off

Start 00000, where zero means off.

Toggle lamps one and two to get 11000. The number on is now two.

Toggle lamps two and three to get 10100. The number on remains two. Every example respects even parity, but checking all move types is what establishes the invariant.

An impossible one-lamp target

From five lamps all off, the number on begins at zero, which is even.

Every allowed adjacent-pair toggle preserves evenness of the on count.

Therefore the target configuration 10000, with exactly one lamp on, is unreachable. The result is independent of which adjacent pairs are chosen or how often.

Worked example 9: a reachable even target

Starting at 00000, toggle lamps one and two to obtain 11000.

Then toggle lamps three and four to obtain 11110, containing four on lamps.

This target satisfies the parity condition and we have explicitly constructed a legal sequence to reach it. Existence requires more than merely checking parity.

Two equal endpoints may be connected through cancellations

A toggle applied twice to the same lamp restores its original state.

When adjacent pairs overlap, a lamp toggled twice also returns to its starting value.

This explains how a sequence of pair toggles can move which lamps are on while preserving the parity of the total on count.

Worked example 10: turn on two endpoints only

Start 00000.

Toggle pair (1,2), then (2,3), then (3,4), then (4,5).

Interior lamps two, three and four are toggled twice and return off. Lamps one and five are toggled once, yielding 10001. The state has two on lamps and is reachable.

Modulo three gives another invariant

Suppose a fictional counter starts at zero and each legal operation adds three or subtracts six.

Every change is divisible by three.

Therefore the counter remains congruent to zero modulo three after any number of moves. A target with remainder one or two modulo three is unreachable.

Worked example 11: test a target

Starting from zero, permitted changes are +3 and −6.

Target ten has remainder one modulo three.

Since every reachable value has remainder zero modulo three, ten is impossible. We do not need to list all move sequences.

The Chinese remainder connection

A system may preserve several modular properties simultaneously.

For example, a move amount divisible by both two and three preserves the current remainder modulo six.

More complicated puzzles combine congruences, and the Chinese Remainder Theorem guide develops how such residue conditions can be reconstructed.

Worked example 12: a six-step change

Let x start at five and legal changes be +6 or −12.

Then x≡5 (mod6), equivalent to x≡5 (mod6) or remainder five.

A target eleven is compatible and can be reached by adding six. A target twelve has remainder zero modulo six and cannot be reached.

Grid walks have a colour-flipping rule

On a square integer grid, colour point (x,y) by parity of x+y.

Moving one unit up, down, left or right changes x+y by plus or minus one.

Therefore every single grid step flips colour. After an even number of steps, the walker has the starting colour; after an odd number, the opposite colour.

Worked example 13: seven steps to a point

Start at (0,0), where x+y=0 is even.

Target (4,3) has coordinate sum seven, odd.

A walk from start to target must have an odd number of unit grid steps. The shortest unconstrained length is |4|+|3|=7, which indeed has odd parity.

Why an eight-step walk is impossible here

Suppose someone asks for a path from (0,0) to (4,3) using exactly eight horizontal or vertical unit steps.

Eight steps return the walker to the starting colour, which has even coordinate-sum parity.

But the target is odd. Therefore an eight-step walk is impossible even though eight exceeds the straight Manhattan minimum of seven.

Worked example 14: a nine-step route

Take four steps right and three steps up to reach (4,3) in seven steps.

Insert a legal two-step backtrack, such as one step right followed by one step left, somewhere along the route.

The full walk now has nine steps and still ends at (4,3). The additional two moves preserve the required odd parity.

Manhattan distance is another necessary condition

For unit horizontal and vertical moves, any walk from (x₁,y₁) to (x₂,y₂) must have at least

|x₂−x₁|+|y₂−y₁|

steps.

The parity of the step count must also match that minimum distance modulo two. These combined conditions describe the unrestricted grid case, but obstacles can impose further limitations.

Worked example 15: a target with ten moves

From (0,0) to (2,2), Manhattan minimum is four.

A ten-step walk is possible on an unrestricted infinite grid because the difference ten−four=6 is even; add three two-step backtracks to a shortest path.

A nine-step walk would violate the parity condition because nine and four have different parity.

Chessboard colours illustrate graph bipartition

A chessboard’s black and white squares form two groups.

A move from one square to an orthogonally adjacent square crosses between these groups.

The resulting adjacency network is bipartite. Its paths alternate colour with every step, which is why the parity-of-path-length conclusion holds.

An odd cycle cannot exist in a bipartite graph

Imagine beginning a walk at a black vertex and traversing an edge at each step.

After an odd number of edges, the walker must be at a white vertex, not the original black vertex.

Therefore no closed odd-length walk exists in a bipartite graph. In particular, a triangle graph is not bipartite.

Worked example 16: contrast a triangle and a square

A triangle cycle has three edges. Starting at one vertex and moving along all three returns to the start after an odd number of steps.

That is incompatible with a two-colour alternating rule.

A square cycle has four edges, so returning to the starting colour after an even number is consistent. A four-cycle is bipartite.

A knight’s move also flips chessboard colour

An ordinary chess knight moves by offsets of two squares in one coordinate and one square in the other.

The sum of coordinate changes has odd parity, so a knight changes checkerboard colour on every legal move.

Therefore, after an odd number of knight moves, it must occupy the opposite colour from its starting square.

Worked example 17: knight-move parity

Suppose a knight starts on a black square.

After one move it is on white, after two on black, after three on white.

It cannot return to its original black square after exactly three knight moves, regardless of board size or the particular moves considered, because every move flips colour.

An invariant is not a complete reachability test

Knight colour alternation rules out certain targets for certain move counts.

But satisfying the correct colour parity does not guarantee that a particular sequence exists, especially with board boundaries or blocked squares.

A proof of impossibility can be complete with an invariant mismatch. A proof of existence needs an explicit construction or a suitable theorem.

Conservation of a sum is another invariant

Suppose a move transfers one token from Box A to Box B.

The count in A decreases by one and the count in B increases by one.

Their total A+B remains unchanged. More generally, transfers among boxes conserve the total number of tokens if no token is created or destroyed.

Worked example 18: two-box transfer

Start with Box A holding seven counters and Box B holding four.

Move three counters from A to B. The new counts are four and seven.

Original total is 7+4=11. Final total is 4+7=11. Any target requiring total twelve is impossible under pure transfer rules.

Invariants can be vector-valued

A puzzle can preserve more than one independent quantity.

For example, it may preserve both the total number of counters and the total value of counters modulo three.

A candidate target must satisfy every relevant invariant. A single matching quantity may not be enough if another invariant is violated.

Worked example 19: two constraints

Imagine a system that preserves total item count ten and total score congruent to two modulo three.

A proposed target with ten items and score fourteen has remainder two modulo three, so it passes these two necessary checks.

A target with ten items and score fifteen fails the modular invariant. The first target is not proved reachable merely because it passes.

A parity invariant may be hidden in an algebraic expression

Suppose an operation transforms integers x,y into x+1,y−1.

The sum x+y is unchanged.

The difference x−y changes by two, so its parity is also unchanged. These are related constraints; a learner can discover useful invariants by calculating how candidate expressions respond to each allowed move.

Worked example 20: investigate two expressions

Start with (x,y)=(2,7), so sum is nine and difference is −5, odd.

After one move, (3,6) has sum nine and difference −3, still odd.

After any number of moves, the sum stays nine. Therefore target (5,5), with sum ten, is impossible even though its difference is even for a different reason.

The shape of a proof by contradiction

To prove a target is impossible, assume a sequence of legal moves reaches it.

Then by invariance, the target must have the same invariant value as the start.

If direct calculation gives a different value, this contradicts the assumption. Therefore no legal sequence reaches the proposed target.

Worked example 21: formal checkerboard contradiction

Assume 31 dominoes tile the 62 remaining squares.

Each domino covers one black and one white square, so the tiling covers 31 of each colour.

But only 30 black and 32 white squares remain. The required counts disagree, so such a tiling cannot exist. This is a proof, not a statement about failed attempts.

Invariants need not be numerical sums

A preserved property can be a colour, parity class, orientation, product sign or connectivity characteristic.

For instance, swapping two items may change the parity of a permutation.

A good invariant matches the allowed operations. It does not have to be visible in the initial problem wording.

The parity of a permutation

A permutation of distinct objects can be called even or odd according to whether it can be produced by an even or odd number of pair swaps.

The parity is well defined because any two swap representations of the same permutation have the same parity.

One way to calculate it is by counting inversions, pairs whose relative order differs from ascending order.

Worked example 22: inversion count

Consider ordering 2,1,3.

The pair (2,1) is inverted, while the other two pairs are in ascending order.

There is one inversion, so the permutation is odd. Swapping the first two numbers produces 1,2,3, which has zero inversions and is even.

The eight-puzzle uses a permutation invariant

The classic sliding eight-puzzle has numbered tiles 1 through 8 and one empty space on a 3×3 board.

A legal move slides one numbered tile horizontally or vertically into the blank.

Ignoring the blank, read the numbered tiles in row-major order. For a three-column board, the parity of the inversion count remains unchanged under legal moves.

Why horizontal moves preserve inversion parity

In a horizontal slide into an adjacent blank, the moving numbered tile shifts by one board position but does not pass any other numbered tile in the row-major list after ignoring the blank.

The relative ordering among numbered tiles remains unchanged.

Therefore the inversion count remains the same under a horizontal blank move.

Why vertical moves preserve inversion parity on a 3×3 board

A vertical slide crosses one full row in the board representation, shifting a numbered tile by three cell positions.

After the blank is ignored, that tile passes exactly two other numbered tiles in the row-major list.

Passing two tiles changes inversion parity by an even number, so the parity remains unchanged.

Worked example 23: a forbidden tile swap

Start from the solved arrangement

1 2 3 4 5 6 7 8 blank.

The numbered list is ascending, with zero inversions.

Now imagine a target obtained by swapping only tiles one and two:

2 1 3 4 5 6 7 8 blank.

This target has one inversion and opposite parity. It is unreachable by legal slides in the 3×3 puzzle.

What the eight-puzzle proof does and does not say

It shows that a configuration with opposite inversion parity from the solved state cannot be reached by legal slides.

It does not say every imaginable move sequence is short, or that a puzzle can be solved by a trivial method when parity matches.

The invariant is a structural reachability test. An actual solution still requires a sequence of moves or a constructive algorithm.

Larger sliding puzzles require additional care

For boards with even width, the simple numbered-tile inversion parity alone is not invariant under every legal vertical blank move.

The parity of the blank’s row position must also be considered in the usual solvability rule.

Therefore one should not transfer the 3×3 inversion criterion to every rectangular sliding puzzle without checking the board geometry.

A monovariant is different from an invariant

An invariant remains constant throughout legal moves.

A monovariant changes consistently in one direction, such as strictly decreasing at every nonterminal step.

Monovariants are useful for proving that an iterative procedure must eventually stop, when the quantity takes values in a well-ordered set or has another suitable restriction.

Worked example 24: a decreasing integer quantity

Start with a positive integer n.

At each step replace n by floor(n/2), stopping when n reaches zero.

The value is a nonnegative integer and strictly decreases whenever it is positive. Therefore the process cannot continue forever without reaching zero.

Why a lower bound matters for termination

A quantity that decreases by one at each step but can become arbitrarily negative need not force termination.

For example n→n−1 can continue indefinitely over all integers if no stopping rule is imposed.

The monovariant proof requires both a direction of change and a constraint that prevents infinite descent, such as nonnegative integer values.

Worked example 25: a finite sequence

Begin at n=19 and repeatedly take floor(n/2).

The sequence is 19→9→4→2→1→0.

Each positive value strictly decreases, and zero is the stopping state. The number of steps here is five, confirming the general termination argument in one instance.

An invariant may coexist with a monovariant

A puzzle might preserve the total number of tokens while reducing the number of misplaced tokens.

The preserved total helps constrain reachable states. The decreasing error count may support termination of a correction algorithm.

These are complementary kinds of mathematical reasoning. One should choose the property suited to the proof goal.

Worked example 26: conservation with progress

Imagine ten tokens, some classified as incorrectly positioned.

A legal correction step repositions one token without adding or removing tokens. The total count stays ten.

If each correction also reduces the number misplaced by at least one and never creates a new mistake, the nonnegative integer error count must eventually reach zero after finitely many steps.

Why a monotonic property may need proof

An algorithm that appears to make progress in a few examples might later increase its error count.

A valid termination proof must establish the claimed decrease for every legal iteration in the relevant domain.

Checking just two sample steps does not establish a global monovariant.

Potential functions combine several quantities

Sometimes no single obvious count decreases at every move.

A carefully chosen weighted sum, such as 100 times one error count plus another smaller count, can decrease lexicographically under a rule.

The weights need justification so that an improvement in the first component cannot be offset by a worsening of the second.

This is advanced algorithmic proof design.

The choice of a colouring is a mathematical invention

For the corner-removed board, ordinary checkerboard colouring provides the right invariant.

For another puzzle, the appropriate colouring might cycle through three classes or use a diagonal pattern.

Finding an invariant often involves trying different representations of the same state until each legal move has a simple, predictable effect.

Worked example 27: an unhelpful colouring

If every square on an 8×8 board is coloured the same, each domino simply covers two identically coloured squares.

That colouring provides only the even-area condition, which the 62-square board already satisfies.

It does not detect the impossible opposite-corner tiling. The two-colour pattern adds the missing information.

Graph invariants are another application

The number of vertices, edges, degree sequence and connected components remain unchanged under graph isomorphism.

Those are invariants under relabelling, not under arbitrary edge modifications.

The underlying transformation determines which quantities deserve to be called invariant. A graph’s edge count is invariant under changing labels but not under adding a new edge.

Worked example 28: relabelling versus editing

Take triangle graph A,B,C with edges AB,BC,CA.

Relabel vertices 1,2,3. Edge count remains three and all degrees remain two.

If instead one edge is removed, the graph becomes a three-vertex path with two edges. Edge count changes because edge removal is a different operation from relabelling.

An impossibility proof cannot establish uniqueness

An invariant mismatch can prove a target is unreachable.

When two states share an invariant, there might be zero, one or many ways to connect them.

Additional construction or classification is needed to prove existence, uniqueness or the exact number of solutions.

Worked example 29: two reachable lamp states

From all-off lamps, 11000 is reachable by toggling pair (1,2).

The four-on state 11110 is reachable by toggling pairs (1,2) and (3,4).

Both have even on-count parity, but they are different states. The invariant class includes many arrangements, not just one.

A logical obstruction can be stronger than a numerical estimate

If the checkerboard colour condition fails, no amount of random search can discover a valid tiling.

A computer might search billions of arrangements and still fail. The invariant proof explains why failure is inevitable.

This is one reason mathematical proof is more powerful than exhaustive-looking examples when the state space is very large.

Connection to computer algorithms

Algorithms often use invariants to prove that a loop maintains a crucial property.

For example, a searching procedure may preserve that all already checked elements have a specified relationship to the current candidate.

An algorithm’s loop invariant is a statement true before the loop, preserved by each iteration, and useful when the loop terminates.

The three parts of a loop-invariant proof

First prove initialisation: the claimed property holds before the first iteration.

Next prove maintenance: one valid iteration preserves it.

Finally combine the property with the termination condition to establish the desired result. This is the same logic as a puzzle invariant, applied to code or repeated mathematical procedures.

Worked example 30: running sum invariant

Suppose a procedure scans numbers a₁,…,aₙ and maintains a variable S.

After processing the first k items, the invariant is S=a₁+⋯+aₖ.

Initially k=0 and S=0. Processing the next number updates S←S+aₖ₊₁, preserving the claim. At termination k=n, S is the total sum.

Conservation and termination serve different roles in code

The running-sum invariant proves partial correctness: the variable retains the intended meaning throughout the loop.

A separate monovariant, such as the decreasing count of unprocessed items, can prove that the scan finishes after finitely many steps.

Together they give a more complete correctness argument than simply testing a few input lists.

Worked example 31: scanning five numbers

Take the fictional list 2,3,5,7,11.

After the first two items, S=5. After three, S=10. At the end, S=28.

At each point S equals the sum of processed items. The number left to process decreases from five to zero, ensuring termination for this finite loop.

A mathematical invariant can expose an impossible game target

Suppose a puzzle begins with an even number of face-up tokens, and each move flips exactly two tokens.

Total face-up parity stays even.

Any requested target with an odd number of face-up tokens is impossible. This general reasoning holds for any number of token positions under those exact legal moves.

Worked example 32: five-token target

Start with five face-down tokens, zero face-up.

Every legal move flips exactly two distinct tokens.

Target all five face-up would have odd parity five, so it is unreachable. The proof does not depend on their arrangement in a row or circle, only on the exactly-two-flips rule.

What if a move flips three tokens?

The original two-flip parity invariant may no longer hold.

Flipping three bits changes the parity of the number on, because three is odd.

A pupil must recompute how a proposed invariant changes under the actual revised move set. A proof for one rule does not automatically survive an altered rule.

From five lamps all off, suppose a move may toggle exactly three lamps.

One move can produce 11100, containing three on lamps.

Thus “on-count parity stays even” is false under this changed rule. The modification demonstrates why an invariant claim must check every allowed operation.

Modulo reasoning generalises even–odd thinking

Parity is modular arithmetic modulo two.

More complex move increments may preserve remainders modulo three, five or another divisor.

The useful modulus often comes from the greatest common divisor of allowed numerical changes. This can reveal impossible targets not distinguished by simple evenness.

Worked example 34: a stronger modulus than two

Suppose x begins at one and every move adds twelve or subtracts eighteen.

Every change is divisible by six, so x stays 1 modulo six.

A target seven is compatible and reachable by adding twelve then subtracting six? Subtracting six is not allowed, but seven may still be reachable by adding twelve and subtracting eighteen? Their net combinations can produce six using 12×2−18=6, so from one reach seven with three moves. A target nine is incompatible because 9 mod6=3.

Check reachability separately from congruence

In the preceding example, invariant x≡1 (mod6) rules out nine.

For seven, an explicit sequence reaches it: 1→13→25→7 using +12,+12,−18.

This two-part response is ideal: use an invariant to reject impossible classes and a construction to establish a specific compatible target.

The original checkerboard puzzle has an elegant answer

Removing opposite same-colour corners does not make the area odd; it remains 62, which can be divided by two.

The obstruction comes from colour balance, not total area.

Every domino necessarily covers one of each colour. The remaining counts differ, so a perfect tiling is impossible. A single invariant defeats every possible placement.

Common error 1: use only area

Sixty-two squares need thirty-one dominoes, which is numerically possible.

But the colour counts are 30 and 32, while thirty-one dominoes cover thirty-one of each.

The correction is to search for a stronger invariant when a basic parity check does not settle the question.

Common error 2: assume all corner pairs behave alike

Diagonally opposite corners have the same checkerboard colour on an 8×8 board.

Adjacent corners have opposite colours.

Removing different pairs changes the colour balance, so their tiling possibilities require separate arguments. Specify exactly which squares are removed.

Common error 3: treat an invariant as a recipe

Knowing that a target has even parity does not supply a sequence of legal moves to reach it.

The invariant gives a necessary compatibility condition. An explicit construction is required for an existence claim unless a completeness theorem has been proved.

Common error 4: test only a few moves

If parity holds after three examples, it may look promising.

But the proof must show that every allowed move preserves it.

Check the algebraic effect of the complete legal move set, then infer preservation after any finite sequence.

Common error 5: confuse invariant and monovariant

A conserved sum stays unchanged.

A strictly decreasing error count changes each step and may prove termination.

These properties serve different purposes. A theorem about conservation cannot automatically establish that a procedure eventually stops.

Common error 6: forget the blank in sliding puzzles

The eight-puzzle inversion argument reads the numbered tiles after omitting the blank.

Horizontal and vertical moves have carefully defined effects on that order for a three-column board.

Changing the board width or counting blank inversions differently without adjusting the solvability criterion can lead to a false claim.

Common error 7: apply a graph invariant under the wrong operation

Degree sequence is preserved by vertex relabelling.

It is not preserved when an edge is added or deleted.

Always name the transformation class before claiming a quantity is invariant.

Common error 8: confuse physical moves with imaginary mathematical permissions

The examples assume precise grid or toggle moves.

A real board may have extra restrictions, blocked positions or permitted operations not included here.

The mathematical proof concerns the stated move system and is not a statement about actual Bukit Timah accessibility or physical layouts.

Primary preparation: even and odd changes

Primary pupils can place counters in two boxes and see that moving one from A to B preserves the total.

They can also discover that adding or removing two counters preserves evenness.

These are concrete precursors to conserved quantities and parity invariants.

Lower Secondary: colouring and divisibility proofs

Students can colour grids, use remainder classes and reason from algebraic changes.

The domino board provides a striking example in which an apparently sufficient area condition misses a deeper structural obstruction.

Formal proof by contradiction can then be introduced as a clear explanation of why the target cannot be reached.

Advanced reasoning and syllabus boundaries

Invariants appear in combinatorics, algebra, algorithms, graph theory and number theory.

Consult the SEAB 2027 G3 Mathematics and Additional Mathematics syllabus directory for the relevant Singapore Secondary course. Sliding-puzzle permutation proofs and loop invariants here are enrichment, not claims of compulsory examinable content for every learner.

A twenty-minute parent diagnostic

Minutes 1–5: Count 32 black and 32 white squares on an ordinary 8×8 board and identify opposite-corner colours.

Minutes 6–10: Remove the corners, obtaining 30 versus 32, and prove 31 dominoes cannot tile the board.

Minutes 11–15: Start with five off lamps and permit adjacent-pair toggles. Show one lamp on is impossible, while four lamps on can be constructed.

Minutes 16–20: Use grid-step parity to show (0,0)→(4,3) cannot take exactly eight unit moves but can take nine. Explain why compatibility is not the same as a complete construction.

Seven days of independent practice

Day one studies parity and even-change rules. Day two explores checkerboard colouring.

Day three proves the missing-corner impossibility. Day four solves toggle and grid-walk constraints.

Day five introduces modular invariants. Day six compares invariant and monovariant proofs. Day seven develops the three-part loop-invariant reasoning for a simple running-sum algorithm.

Practice questions with checked answers

A. 8×8 board original colour counts? Answer: 32 of each colour.

B. Remove opposite same-colour corners: remaining counts? Answer: 30 and 32.

C. Can 31 dominoes tile that board? Answer: no.

D. All-off lamps, toggling exactly two each move: can one lamp end on? Answer: no.

E. From (0,0) to (4,3) in exactly eight orthogonal unit steps? Answer: impossible.

F. Same grid target in nine steps? Answer: possible on an unrestricted grid.

G. Start x=0, moves multiples of three, target ten? Answer: impossible.

H. Solved 3×3 eight-puzzle with only tiles one and two swapped: reachable? Answer: no.

Frequently asked questions

What is a mathematical invariant?

A quantity or property that remains unchanged under every allowed transformation of a problem.

How can an invariant prove a puzzle is impossible?

If the starting state and target have different invariant values, no sequence of invariant-preserving moves can reach the target.

Why cannot the corner-removed checkerboard be tiled?

Removing two same-colour corners leaves unequal black and white counts, while every 1×2 domino covers exactly one of each.

Is even area enough to prove a domino tiling exists?

No. Even area is necessary but can fail to capture colour or geometric restrictions.

What is the simplest invariant?

Parity—whether an integer is even or odd—is often a useful first candidate.

What is a monovariant?

A quantity that moves in a consistent direction during legal operations, often used to show a procedure terminates.

Does a matching invariant guarantee a move sequence?

No. It shows the target has not been ruled out by that invariant, but reachability may require more conditions.

How do invariants relate to algorithms?

Loop invariants formalise a property preserved by every iteration and help prove that an algorithm’s result is correct when it terminates.

Are these actual Bukit Timah facility or pupil puzzles?

No. All boards, moves and participants are invented mathematical teaching models.

How can parents recognise mastery?

The learner can state an invariant, prove preservation for every move, identify a contradiction and distinguish that proof from a constructive existence argument.

Official context and connected Mathematics in Bukit Timah

For level-specific learning, consult the SEAB 2027 G3 Mathematics and Additional Mathematics syllabus directory. The mathematical puzzles here are original enrichment examples, not official examination questions or actual local observations.

Continue with Proof, Counterexamples and Mathematical Claims, Modular Arithmetic and Check Digits, Graph Isomorphism and Network Symmetry, Pigeonhole Principle and Guaranteed Matches and Euler’s Polyhedron Formula for complementary structural reasoning.

The immutable Clementi Secondary 1 Mathematics tutoring reference anchors first principles, worked verification, misconception diagnosis and independent explanations.

The lasting habit is to define legal moves precisely, seek what every move preserves, use a contradiction to rule out impossible targets and give an explicit construction whenever the question asks whether a compatible target can actually be reached.

Companion Mathematics in Bukit Timah articles from this November batch: Birthday Paradox, Shared Birthdays and Collision Probability · Monty Hall Problem, Switching Doors and Conditional Probability · Spherical Geometry, Great Circles and Shortest Surface Distances. These four original articles distinguish mathematical probability from certainty, conditioned decisions from naive guessing, surface geometry from flat distance, and structural invariants from trial-and-error searches.