A 90-minute mathematics mission

GLITCH!

Can mathematics repair a broken message?

Dr. Mudassir Shabbir Department of Computer Science · LUMS

UNKNOWN ORIGIN · SIGNAL 01 H?M?N?TY H?S A PR?BL?M

Impossible mind-reading

Flip one card. I’ll find it.

Choose a random pattern—or flip as many of the 25 center cards as you like.

3After the decoration, flip one card.

Start with any pattern you want.

chosen cards added cards

Final reveal

The intersection gives it away

One flipped square trips exactly two alarms.

Every line begins even → one flip makes one row + one column odd → their intersection is the glitch

Mission briefing

Year 2090

Near-Ice Life Analyzer

Meet Near-Ice Life Analyzer (NILA)

A small robot, a frozen ocean, and one very expensive flashlight.

NILA → LUMEN → Earth

One-way journey: tens of minutes

Mission constraints

The engineering box

2×wake-ups per day

12flashes per report

1flash may flip

Protocol 0.1

One question

YES

NO

1 light → 2 messages

Card game · Human transmitter

Four volunteers

Become NILA’s laser

1Four students hold red/green cards.

2A team secretly draws one mission card.

3Turn the humans into its four-flash code.

Physical setup

Choose four volunteers. Give each a double-sided red/green card. They stand left-to-right in positions 8, 4, 2, 1. The displayed cards can also be clicked for a digital version.

Round structure

One team draws a mission card.
They silently arrange the four volunteers.
Another team reads the pattern and identifies the message.
Swap teams quickly.

The place-value labels allow a secondary route: messages 0–15 can be treated as numbers, but students do not need binary arithmetic to play.

The print button creates sixteen cut-out message cards plus red/green bit cards in a new window.

Mission Control codebook

16 possible reports

Capacity lab

Every light doubles the language

21 light

42 lights

83 lights

164 lights

325 lights

Choose the number of lights

12345678

8 patterns

Not enough for 16

Card game · Round two

Encode → transmit → decode

🧪

Ice sample collected

Secret mission card

Tap lights to build the four-flash message.

Opening transmission decoded

Code 1011

⚠

MISSION EMERGENCY

1011Mission emergency

1010Possible biological pattern

The catastrophe

One bit flip

SENT?

1010

⚡

RECEIVED

1011

“Possible life” became “Emergency.”

Engineering huddle

You have 4 minutes

🐕

Add a watchdog light

Cost: 1 extra flash

🔁

Repeat the whole message

Cost: 8–12 flashes

🏝️

Spread valid messages apart

Cost: clever code design

Idea 2 · Repetition

Simple, reliable, expensive

original message

Copy 2

Copy 3

Idea 1 · The watchdog

Even parity

Make the total number of green lights even.

Green lights: 0

Watchdog satisfied ✓

Idea 3 · Give messages personal space

Hamming distance

0000

1111

1010Message A

1011Message B

Positions that differ

1

Honest attempt 1 · Five flashes

32 possible received strings

Best-case packing attempt32 slots

message one-flip result missing slot

Be unrealistically generous

Assume every neighborhood packs perfectly.

1 original + 5 possible flips = 6 slots per message

32 ÷ 6At most 5 protected messages We need 16. The sixth message already spills over.

Honest attempt 2 · Six flashes

64 possible received strings

Best-case packing attempt64 slots

message one-flip result missing slot

Try again with twice the space

Six flashes still run out far too early.

1 original + 6 possible flips = 7 slots per message

64 ÷ 7At most 9 protected messages We need 16. The tenth message has only one slot left.

Research door 1 · Pack the message bubbles

A counting lower bound

Universe of 7-bit strings 2⁷ = 128

Each protected message occupies:

1 original + n one-flip neighbours

16(n + 1) ≤ 2ⁿ

Try n = 6, 7. Where does counting decide it—and where is the fit exact?

Group exercise

For length n, a word plus all words one flip away has size n+1. Sixteen correctable messages need sixteen disjoint balls, inside 2ⁿ total strings.

n = 6: 16×7 = 112 > 64, so impossible.
n = 7: 16×8 = 128 = 128 — an exact fit, nothing wasted.

The Hamming(7,4) code built next meets this bound with equality: a perfect code. Emphasize the research lesson: a lower bound says what cannot work; here it is tight. Determining the largest code with given length and distance is written A₂(n,d).

Extension: model all n-bit words as graph vertices, join pairs at distance 1 or 2, and seek a largest independent set.

See the whole seven-bit universe

Q₇ · 128 vertices

One flipped bit draws one edge.

Every seven-bit word appears once. Neighbors differ in exactly one position—one possible transmission error. Each bit gets its own direction in this symmetric projection.

128 possible words 7 neighbors each 448 edges total

any received word Hamming codeword one flip away

Hover or tap a point. Can two amber points ever be neighbors?

Selected word 0000000 Its seven one-flip neighbors are highlighted.

A seven-flash repair code

3 inspectors · 4 data lights

First attempt: keep the four data lights together and append all three checks.

Design requirement

Every damaged position needs its own alarm pattern.

Three inspectors each answer yes or no. How many different patterns can they report?

Start with the natural first draft: D1, D2, D3, D4, then P1, P2, P4. Ask what makes those final three positions special. Nothing yet.

First count the eight possible three-inspector signatures. Reserve 000 for “no error,” then read 001 through 111 as binary position numbers 1 through 7. Identify 001, 010, and 100 as the three solo-inspector anchors.

Assign P1, P2, and P4 to those anchors, then ask students to fill the leftover positions with D1–D4. Only after they predict the full order, reveal checks at 1, 2, and 4 and data at 3, 5, 6, and 7.

Inspector 1 watches the odd positions 1,3,5,7.
Inspector 2 watches 2,3,6,7.
Inspector 4 watches 4,5,6,7.

Each inspector enforces even parity on its group. A damaged position triggers exactly the inspectors whose labels add to that position number.

For younger groups, treat this as a detective game. For older groups, connect the pattern to binary place values.

Build NILA’s protected report

Data: 1010

Place data in positions 3, 5, 6, 7. Then satisfy every inspector.

Radiation strike

Received: 1011000

?

Message repaired

Scientific caution required

1010

POSSIBLE BIOLOGICAL PATTERN

Not proof of life—proof that Earth heard NILA correctly.

Practice lab · 1 of 7

Work alone · 3 minutes

Write one number for each pair

Hamming distance

Compare the bits in the same positions.
Count every position where the bits differ.
Circle each pair that could belong to a one-error-correcting code.

A10110101011000

B00000001110000

C11001101010101

Practice lab · 2 of 7

Pairs · 4 minutes

Explore one error bubble

One-flip neighbors

Start with0101101

Flip bit 1 and record the new word.
Restore it, then repeat for bits 2 through 7.
Count the original word and all its neighbors.

Your paper should contain seven different neighbors and one neighborhood size.

Practice lab · 3 of 7

Pairs · 4 minutes

1 means that inspector complains

Inspector signatures

For each position, decide whether P4, P2, and P1 watch it.
Write the complaint pattern in the order P4 P2 P1.
Read the pattern as a binary number.

Position	P4 P2 P1	Sum
3	___	___
5	___	___
6	___	___
7	___	___

Practice lab · 4 of 7

Guided · 4 minutes

Encode data 0110

Guided encoding

1 · P1?2 · P2? 3 · D104 · P4? 5 · D216 · D31 7 · D40

Choose P1 so positions 1, 3, 5, and 7 have even parity.
Repeat for P2 on 2, 3, 6, and 7.
Repeat for P4 on 4, 5, 6, and 7.

Practice lab · 5 of 7

Work alone · 4 minutes

Encode data 1101

Independent encoding

Data1101

Draw positions 1 through 7 and label the parity positions.
Place the four data bits in positions 3, 5, 6, and 7.
Choose all three parity bits, then audit every group.

Submit one seven-bit codeword and three parity checks.

Practice lab · 6 of 7

Guided · 4 minutes

Received word

Guided decoding

Earth sees1000111

Test P1 on positions 1, 3, 5, and 7.
Test P2 and P4 in the same way.
Add the labels of the complaining inspectors.
Flip that position, then read data positions 3, 5, 6, and 7.

Practice lab · 7 of 7

Solo check · 5 minutes

One error occurred

Complete decode

Received0101100

Find the syndrome without using a group diagram.
Repair the indicated bit.
Extract the four data bits.
Verify the repaired word with all three parity checks.

Show the syndrome, repaired codeword, recovered data, and parity audit.

Research door 2 · What if two lights flip?

Beyond single-error correction

✓

0 errorsall checks agree

🛠️

1 errorlocate and repair

⚠️

2 errorsmay imitate one error

?

More errorsstronger codes needed

🛡️

Add one overall parity light

8 flashes can correct one error and detect two.

Can you derive the four possible check outcomes?

A distance-3 Hamming code can miscorrect two errors because the syndrome may point to an innocent position. Add an eighth overall parity bit to obtain single-error correction, double-error detection (SECDED).

Challenge table

Syndrome 0, overall parity OK: no error.
Syndrome nonzero, overall parity wrong: one error in indicated position.
Syndrome 0, overall parity wrong: error in the overall parity bit.
Syndrome nonzero, overall parity OK: two errors detected; do not “repair.”

Ask what the probe should do after detecting but not correcting two errors: request retransmission, mark data uncertain, or use a stronger code.

Research door 3 · Is seven optimal?

16 messages · correct 1 flip

n = 6 → impossible

n = 7 → perfect fit

16 · 8 = 128 = 2⁷

Add a 17th report, or demand two-error correction. When does counting stop deciding it?

For sixteen messages the counting bound is tight: n = 6 is impossible, and n = 7 fits with equality. Hamming(7,4) is a perfect code, so seven flashes is provably optimal.

Push the numbers and the problem reopens. Translate it into several languages:

Coding: choose seventeen length-7 binary words with minimum distance 3 — or prove it is impossible.
Graph theory: from the graph on 128 words, choose seventeen vertices with no pair at distance 1 or 2.
Optimization: maximum independent set / integer programming.
Computation: greedy search, backtracking, SAT, or symmetry breaking.

Do not require a full solution in class. A good mini-project is to find the largest code students can construct and provide a verifiable distance table.

Choose a research door

Mini-project menu

Explorer

📦

Pack better codes

Search for large sets of far-apart bit strings. Compare constructions with counting bounds.

Explorer

🕸️

Turn it into a graph

Connect confusable messages. Error-correcting codes become independent sets.

Builder

🌩️

Burst errors

Several neighbouring flashes fail together. Can interleaving spread the damage?

Builder

🕳️

Missing flashes

A light disappears and shifts everything. Explore deletion-correcting codes.

Researcher

📡

Soft decoding

The detector reports confidence, not just red/green. How should likelihood guide repair?

Researcher

⚛️

Quantum errors

Qubits cannot simply be copied. How can parity-like ideas protect quantum states?

Suggested deliverables

A one-page problem statement defining message length, alphabet, and allowed errors.
A construction or algorithm.
A verifier that checks every pair or every error pattern.
A comparison with a simple bound or baseline.
One unanswered question discovered during the work.

Age differentiation

Grades 6–7 can build physical codebooks and test them. Grades 8–9 can write a small brute-force checker. Grade 10 can formulate graphs, matrices, or optimization models.

Important research habit: distinguish random noise, known erasures, bursts, insertions/deletions, and adversarial errors. Different channels demand different codes.

Not science fiction

Extra bits are everywhere

QR codes

Still scan when parts are dirty or covered.

Storage

Detect and repair corrupted bits on disks and memory.

Wireless

Recover messages from interference and weak signals.

Space links

Protect data when retransmission is slow and costly.

Recovery game · Round 1

A page of editable text

LIVE PAYLOAD

Can Hamming code rescue a damaged page?

Random bit flips 3%

Original text · editable

Broken text · before repair

Damaged text will appear here.

Recovered text

Recovered text will appear here.

Ready. Encode the source to begin.

Source— Encoded— Flipped— Recovered—

original→damaged→repaired

Recovery game · Round 2

The first website · recreated

FAMOUS WEBPAGE

Will damaged HTML still behave like a webpage?

Random bit flips 3%

Original · a playful 1991-style recreation

Broken webpage · before repair

Recovered webpage

Ready. Encode the source to begin.

HTML— Encoded— Flipped— Recovered—

original→damaged→repaired

Recovery game · Final round

Complete public-domain book · 3.36 MB

PROJECT GUTENBERG EBOOK #2600

Can we repair all of War and Peace?

Random bit flips 3%

Original book · opening preview

Loading book preview…

Broken book · before repair

Damaged text will appear here.

Recovered book · opening preview

Recovered text will appear here.

Ready. Encode the source to begin.

Book3.36 MB Encoded— Flipped— Recovered—

original→damaged→repaired

AURORA Mission · Link complete

NILA returns to sleep

Thank you

Mathematics did not make the light brighter.
It made the message harder to destroy.

Encore · The simplest family

One idea, any odd length

Repetition code

When in doubt, say it again.

Send one bit n times. Decode by majority vote.

Send1→111[3,1,3] corrects 1 error

Send1→11111[5,1,5] corrects 2 errors

Send1→1111111[7,1,7] corrects 3 errors

Encore · Hamming's legendary cousin

Marcel Golay · 1949

PERFECT BINARY GOLAY CODE

[23, 12, 7]

23 transmitted 12 data 7 minimum distance

Any 3 flipped bits can be corrected.

One radius-3 neighborhood

1 + 23 + 253 + 1771 = 2048

4096 messages × 2048 outcomes

= 8,388,608 = 2²³

Every possible received word belongs to exactly one message.

Encore · Add one more parity bit

From 23 bits to 24

Extended binary Golay code

[24, 12, 8]

[23,12,7]+ parity[24,12,8]

Correct any 3 flipped bits.
Detect up to 7 errors when only detecting.
Golay-family decoding served real deep-space links.

Encore · From symbols to a polynomial

Reed & Solomon · 1960

Three message symbols

231

become the coefficients of

p(x) = 2 + 3x + x²

Arithmetic wraps around modulo 11.

Sample the same shape seven times

x=02

x=16

x=21

x=39

x=48

x=59

x=61

TRANSMIT2 · 6 · 1 · 9 · 8 · 9 · 1

We did not copy the message. We sent enough points to rebuild its rule.

Encore · Two samples are corrupted

Repair the polynomial, not each bit

RECEIVED

2679841

Two symbols no longer lie on the shape.

DECODER Find the degree-2 polynomial that agrees with at least 5 points →

RECOVERED

2619891

[7,3,5] corrects any 2 symbol errors.

▦QR codessurvive dirt and missing patches

💿Storage & mediarepair clustered damage

🛰️Space linksrecover blocks of telemetry

Encore · One idea becomes a field

Your next mission

1Repetitionmajority vote

→

2Hammingone-error address

→

3Golayperfect radius 3

→

4Reed-Solomonrepair symbols

→

5LDPC · Polarmodern high-rate links

You already know how to begin:

GLITCH!

Flip one card. I’ll find it.

One flipped square trips exactly two alarms.

Meet Near-Ice Life Analyzer (NILA)

Become NILA’s laser

Choose the number of lights

Ice sample collected

MISSION EMERGENCY

Add a watchdog light

Repeat the whole message

Spread valid messages apart

Make the total number of green lights even.

Each protected message occupies:

One flipped bit draws one edge.

Every damaged position needs its own alarm pattern.

Hamming distance

One-flip neighbors

Inspector signatures

Guided encoding

Independent encoding

Guided decoding

Complete decode

Add one overall parity light

Pack better codes

Turn it into a graph

Burst errors

Missing flashes

Soft decoding

Quantum errors

QR codes

Storage

Wireless

Space links

Can Hamming code rescue a damaged page?

Will damaged HTML still behave like a webpage?

Can we repair all of War and Peace?

When in doubt, say it again.

[24, 12, 8]

What can fail? What must survive? What redundancy can we afford?