Which Card Was Flipped?

Do the trick above a few times, with New cards in between.

• a.When you laid the extra cards, did you ever have to change one you had already set?
• b.After a card was turned, count the dark cards in each row. How many rows had an odd number? How many columns?
• c.Try to catch the trick out: keep going until the page turns over one of your cards. Can you still find it?

Whether a count is even or odd is called its parity. Your extra cards are parity cards: each one is chosen to make its line’s count of dark cards even. A light card if the line already has an even number (and zero counts as even), a dark card if it has an odd number.

Now turn over one card, any card. Its row gains a dark card or loses one, so that row’s count changes by exactly one, and an even count becomes odd. The same happens to its column. No other line contains that card, so every other line stays even. The result is always the same: exactly one odd row and exactly one odd column, and they cross at the card that was turned.

So the trick has limits. One turned card is always found. Two or three are noticed, but can’t be pinned down. And four at the corners of a rectangle leave every line even: you would never know.

A card has two sides, like a bit, 1 or 0 (Grade 6). Write dark as 1 and light as 0, and each parity card is a parity bit, a bit added to make a group’s count of 1s even, which computers have used since their early days.

With blocks: the extra card

This program is the magician’s first job. It asks for a row of five cards, one at a time (1 for dark, 0 for light), counts the dark ones, and says what the extra card must be. The remainder of a count divided by 2 is 0 for an even count and 1 for an odd one.

In Python (from Grade 8): a list of lists

In Python a row of cards is a list of 0s and 1s, and the whole layout is a list of lists: a list whose items are the rows. grid[2] is row 2 (counting from 0, as Python does), and grid[2][0] is the first card in it.

grid = [    [1, 0, 0, 1, 1],    [0, 1, 1, 0, 1],    [1, 1, 0, 0, 0],    [0, 0, 1, 0, 1],    [1, 0, 1, 1, 0],]print(grid[2])print(grid[2][0])print(len(grid), 'rows of', len(grid[0]))

[1, 1, 0, 0, 0]15 rows of 5

Adding the extra cards

add_parity makes the 6 × 6 layout. For each row it counts the dark cards and puts dark % 2 on the end: 1 (dark) if the count is odd, 0 if it is even. Then it makes the bottom row the same way, column by column, including the new sixth column, so the corner card is counted too. (row + [x] is a new list with x on the end, and new.append(x) puts x on the end of new.)

from pixels import show_grid grid = [    [1, 0, 0, 1, 1],    [0, 1, 1, 0, 1],    [1, 1, 0, 0, 0],    [0, 0, 1, 0, 1],    [1, 0, 1, 1, 0],] def add_parity(grid):    new = []    for r in range(5):        dark = 0        for c in range(5):            dark = dark + grid[r][c]        new.append(grid[r] + [dark % 2])    bottom = []    for c in range(6):        dark = 0        for r in range(5):            dark = dark + new[r][c]        bottom.append(dark % 2)    new.append(bottom)    return new cards = add_parity(grid)for row in cards:    print(row)show_grid(cards, ['#fffdf4', '#3b3a36'])

[1, 0, 0, 1, 1, 1][0, 1, 1, 0, 1, 1][1, 1, 0, 0, 0, 0][0, 0, 1, 0, 1, 0][1, 0, 1, 1, 0, 1][1, 0, 1, 0, 1, 1]

Picture

show_grid is part of the page’s own pixels module: it draws one square for each number, 0 in cream and 1 in dark gray. (On your own computer you would draw it with a library such as Pillow.)

Finding the flipped card

To find the turned card, find_flip counts the dark cards in every row and remembers the one that is odd, then does the same for the columns. It gives back the place where they cross as [row, column]. The last lines turn over the card in row 2, column 3, the way your friend would, with 1 - x, which turns 0 into 1 and 1 into 0.

def add_parity(grid):    new = []    for r in range(5):        dark = 0        for c in range(5):            dark = dark + grid[r][c]        new.append(grid[r] + [dark % 2])    bottom = []    for c in range(6):        dark = 0        for r in range(5):            dark = dark + new[r][c]        bottom.append(dark % 2)    new.append(bottom)    return new def find_flip(grid):    odd_row = -1    odd_col = -1    for r in range(6):        dark = 0        for c in range(6):            dark = dark + grid[r][c]        if dark % 2 == 1:            odd_row = r    for c in range(6):        dark = 0        for r in range(6):            dark = dark + grid[r][c]        if dark % 2 == 1:            odd_col = c    return [odd_row, odd_col] cards = add_parity([[1, 0, 0, 1, 1], [0, 1, 1, 0, 1], [1, 1, 0, 0, 0], [0, 0, 1, 0, 1], [1, 0, 1, 1, 0]])cards[2][3] = 1 - cards[2][3]print(find_flip(cards))

[2, 3]

Now let your program be the magician. The widget below finds the find_flip in the program above, as you have edited it. Each trick, the page lays out new cards with their parity cards, turns one over at random, and asks your function which it was.

Try every mistake

The page tried random cards. A program can try every mistake instead and count. odd_lines gives back the lists of odd rows and odd columns (rows, cols = odd_lines(cards) puts the two lists in two variables). The program turns over each of the 36 cards in turn, then every pair of cards, then every three, and each time looks at the lines. A mistake is caught if any line is odd. The lines point at one card if exactly one row and one column are odd.

cards = [    [1, 0, 0, 1, 1, 1],    [0, 1, 1, 0, 1, 1],    [1, 1, 0, 0, 0, 0],    [0, 0, 1, 0, 1, 0],    [1, 0, 1, 1, 0, 1],    [1, 0, 1, 0, 1, 1],] def odd_lines(grid):    rows = []    cols = []    for i in range(6):        across = 0        down = 0        for j in range(6):            across = across + grid[i][j]            down = down + grid[j][i]        if across % 2 == 1:            rows.append(i)        if down % 2 == 1:            cols.append(i)    return rows, cols def flip(grid, card):    r = card // 6    c = card % 6    grid[r][c] = 1 - grid[r][c] found = 0for a in range(36):    flip(cards, a)    rows, cols = odd_lines(cards)    if rows == [a // 6] and cols == [a % 6]:        found = found + 1    flip(cards, a)print('One card: found', found, 'of 36') tried = 0caught = 0pointed = 0for a in range(36):    for b in range(a + 1, 36):        flip(cards, a)        flip(cards, b)        rows, cols = odd_lines(cards)        tried = tried + 1        if len(rows) > 0 or len(cols) > 0:            caught = caught + 1        if len(rows) == 1 and len(cols) == 1:            pointed = pointed + 1        flip(cards, a)        flip(cards, b)print('Two cards:', tried, 'tried,', caught, 'caught,', pointed, 'point at one card') tried = 0caught = 0pointed = 0for a in range(36):    for b in range(a + 1, 36):        for c in range(b + 1, 36):            flip(cards, a)            flip(cards, b)            flip(cards, c)            rows, cols = odd_lines(cards)            tried = tried + 1            if len(rows) > 0 or len(cols) > 0:                caught = caught + 1            if len(rows) == 1 and len(cols) == 1:                pointed = pointed + 1            flip(cards, a)            flip(cards, b)            flip(cards, c)print('Three cards:', tried, 'tried,', caught, 'caught,', pointed, 'point at one card')

One card: found 36 of 36Two cards: 630 tried, 630 caught, 0 point at one cardThree cards: 7140 tried, 7140 caught, 900 point at one card

(Cards are numbered 0 to 35 along the rows, so card number a is in row a // 6 and column a % 6.)

• Every single turned card was found and could be put right: 36 of 36, your friend’s cards and your own.
• Every mistake of two or three cards was caught: 630 of 630 pairs, 7,140 of 7,140 threes. Some line was always odd, so the magician always knows something has gone wrong.
• But with two cards, the lines never point at one card, and with three cards they sometimes do, 900 times out of 7,140, and then they point at the wrong card. Turning it “back” makes four turned cards at the corners of a rectangle, with every line even: the cards would look perfect, and be wrong.

So one extra row and column buy what a single check digit can’t: the barcode’s check digit says that there is a mistake, these cards say where, so it can be fixed without asking again. The price is 11 extra cards for 25, and the promise holds for one mistake at a time.

A damaged message, repaired

Cards are bits, so they can carry a message. Number the characters in ABC from 0 (a space) to 31, write each letter’s number in five bits, as Grade 6 writes numbers, and a five-letter word is a 5 × 5 grid. Add the parity bits, send it, and let one bit go wrong on the way, as a scratch on a disc would. random.seed(7) makes the same “random” bit go wrong every run, so your output matches this page; change the 7 for another.

import random ABC = ' ABCDEFGHIJKLMNOPQRSTUVWXYZ.,?!-' def to_bits(letter):    n = 0    while ABC[n] != letter:        n = n + 1    bits = []    for value in [16, 8, 4, 2, 1]:        if n >= value:            bits.append(1)            n = n - value        else:            bits.append(0)    return bits def from_bits(bits):    n = 0    for i in range(5):        n = n * 2 + bits[i]    return ABC[n] def add_parity(grid):    new = []    for r in range(5):        dark = 0        for c in range(5):            dark = dark + grid[r][c]        new.append(grid[r] + [dark % 2])    bottom = []    for c in range(6):        dark = 0        for r in range(5):            dark = dark + new[r][c]        bottom.append(dark % 2)    new.append(bottom)    return new def find_flip(grid):    odd_row = -1    odd_col = -1    for r in range(6):        dark = 0        for c in range(6):            dark = dark + grid[r][c]        if dark % 2 == 1:            odd_row = r    for c in range(6):        dark = 0        for r in range(6):            dark = dark + grid[r][c]        if dark % 2 == 1:            odd_col = c    return [odd_row, odd_col] def read(grid):    word = ''    for r in range(5):        word = word + from_bits(grid[r])    return word message = []for letter in 'NEPAL':    message.append(to_bits(letter))sent = add_parity(message) random.seed(7)r = random.randint(0, 5)c = random.randint(0, 5)sent[r][c] = 1 - sent[r][c]print('On the way, the bit at', [r, c], 'went wrong.')print('Read as it arrived:', read(sent)) place = find_flip(sent)print('find_flip says:', place)sent[place[0]][place[1]] = 1 - sent[place[0]][place[1]]print('Read after fixing:', read(sent))

On the way, the bit at [2, 1] went wrong.Read as it arrived: NEXALfind_flip says: [2, 1]Read after fixing: NEPAL

The word arrived as NEXAL, and the receiver put it right by itself, without knowing what was sent. That is an error-correcting code: send a little more than the message, arranged so that a mistake shows where it is. The codes in your phone, a QR code or a disc are cleverer than rows and columns, but do the same job.

The trick as played here is CS Unplugged’s “Parity magic” activity, from the Computer Science Education Research Group at the University of Canterbury, New Zealand (CC BY-SA 4.0). Try it with real cards on your family.

Bigger squares cost less. For a square of n × n cards, the extra row and column add 2n + 1 cards. Is that a lot or a little as the square grows? And how few check bits could do the same job? Hamming showed that with k check bits you can name 2ᵏ different things: “no error” or any one of the bits, the check bits included. This program counts both.

for n in [3, 5, 8, 10, 20]:    data = n * n    square = 2 * n + 1    k = 1    while 2 ** k < data + k + 1:        k = k + 1    print(n, 'x', n, ':', data, 'bits, the square adds', square, ', Hamming needs only', k)

3 x 3 : 9 bits, the square adds 7 , Hamming needs only 45 x 5 : 25 bits, the square adds 11 , Hamming needs only 58 x 8 : 64 bits, the square adds 17 , Hamming needs only 710 x 10 : 100 bits, the square adds 21 , Hamming needs only 720 x 20 : 400 bits, the square adds 41 , Hamming needs only 9

For your friend’s 25 cards, five well-chosen check cards would be enough instead of eleven. How Hamming chose them is the next step: see “How does a scratched QR code still scan?” below.

★ Which row is odd? (blocks)

Your friend has counted the dark cards in each of the six rows and types the counts in, one at a time. Finish the program so that it says the number of the row whose count is odd (1 to 6), or none if every row is even. Then press Test.

★★ What do the lines say? (Python, from Grade 8)

Write diagnose(grid) for a 6 × 6 grid of cards. It gives back 'fine' if every row and column is even, [row, column] if exactly one row and exactly one column are odd, and 'too many' otherwise.

def diagnose(grid):    # grid is 6 rows of 6, 1 for dark and 0 for light    return 'fine' print(diagnose([[0] * 6, [0] * 6, [0, 0, 1, 0, 0, 0], [0] * 6, [0] * 6, [0] * 6]))

★★★ Read the damaged word (Python, from Grade 8)

A five-letter word was sent as a 6 × 6 grid of bits (five rows of five letter bits, with parity bits), and at most one bit went wrong on the way. Write read_damaged(grid) that gives back the word as it was sent. ABC and from_bits are given.

ABC = ' ABCDEFGHIJKLMNOPQRSTUVWXYZ.,?!-' def from_bits(bits):    n = 0    for i in range(5):        n = n * 2 + bits[i]    return ABC[n] def read_damaged(grid):    # grid is 6 rows of 6; at most one bit is wrong    return '' print(read_damaged([[0, 1, 1, 1, 0, 1], [0, 0, 1, 0, 1, 0], [1, 1, 0, 0, 0, 1], [0, 0, 0, 0, 1, 1], [0, 1, 1, 0, 0, 0], [1, 0, 1, 1, 0, 1]]))

• How Does a Barcode Catch a Typing Mistake?: one check digit that spots a mistake but can’t say where it is.
• How Does the Mind-Reading Card Trick Work?: another card trick that is really binary.
• Grade 6, Zeros and Ones: bits, and writing numbers in binary.
• Grade 7, True or False: Logic: an XOR gate is 1 when exactly one of its two inputs is; a chain of XOR gates is 1 when an odd number of its inputs are, which is a parity check in wires.
• Grade 9, Data in Depth: how data is stored and packed into bits.
• How does a scratched QR code still scan? (Grades 9–12): Hamming’s code, which finds and fixes a wrong bit with far fewer check bits.