WORK IN PROGRESS

The magician lays out 21 cards face up in three columns and seven rows. He asks a person in the audience to memorize one of the cards. Then the spectator is instructed to indicate the column that holds the chosen card. The magician gathers up the cards column by column and then lays them out row by row in the same kind of grid again; three columns, seven rows. Again, the spectator is asked to indicate a column. The process is repeated a third time, after which the magician gathers up the cards and recites the magic word: 'Abracadabra!'. He then deals the cards, spelling out one letter of 'abracadabra' for each card. As he pronounces the last 'a', he deals the chosen card!

How does this work? Why does it work? Does it work for any number of cards? How many columns and rows does the trick need? How many times does the spectator have to indicate a column for the trick to work? All of these questions, believe it or not, are answered in this Entry.

How it Works

This trick is also known as The Abracadabra Card, The Eleventh Card, Sim Sala Bim, Lucky Guess and 49er Fool's Gold (in which there are 49 cards in a 7x7 grid), and is very easy. The magician only needs to gather up the cards column by column, making sure to preserve the relative order of the cards in the indicated column and sandwich the indicated column between the others. In other words, the indicated column should end up in the middle, much like the famous bologna or whatever else people might care to use as the middle layer of a sandwich. One of the easiest ways to preserve the order of the cards in a column is to make each row overlap the previous a bit but keeping the columns apart, so that each column can be scooped up swiftly and with style. This way, the magician can gather up the cards quickly, and the spectator will have a harder time spotting the fact that his column is being sandwiched. Another important part of the trick is that the cards must be lain out row by row. By repeating this process a number of times, depending on the number of cards, the chosen card is 'magically' attracted to the very middle, i.e. the 11th position when using 21 cards.

A Mathematical Point of View

By counting the cards row wise - calling the first card number zero - while laying them out in the grid, we can assign a number to the chosen card. This number is called the 'row-wise position'and is denoted p. Each time we sandwich the indicated column between the others, the chosen card receives a new row-wise position. If r is the number of rows, c is the number of columns and y is the row (zero being the top row) containing the chosen card, we can deduce the formula for the new row-wise position. Since the chosen card is in row y in the indicated column and we're using zero-based counting, there are y cards above it in that column¹. Also, we're gathering up said column after gathering up half of the columns (i.e. r(c / 2) cards). Therefore, there must be y + r(c / 2) cards before the chosen card after we've gathered them all up. Since we're using zero-based counting and the cards are lain out row wise, this is the new value of p.

p = y + r(c / 2)

(1)

Note that r(c / 2) does not equal cr / 2, since they're integer divisions. In some cases, the two are equal, but we can't take that for granted anymore in the integer domain, where the truncation makes things a bit more complicated. Consider, for example, nine cards laid out in three columns and three rows, i.e. c = 3 and r = 3. In this case, c / 2 = 1. We get this by truncating at the decimal point, so 1.5 becomes 1. Therefore r(c / 2) = 3. However, cr = 9 and cr / 2 = 4.

The variable y is redundant, since we can easily calculate which row the card is in given the row-wise position and the number of cards in a row, i.e. the number of columns.

y = p / c

(2)

Note that this is also an integer division. Let's do a sanity check using those nine cards; c = 3 and r = 3. The row-wise positions of the first three cards are 0, 1 and 2. An integer division by 3 gives us y = 0 for all of those cards. So far so good². The row-wise positions of the next three cards - 3, 4, or 5 - divided by 3 equal 1. Fine. 6, 7 or 8 divided by 3 equal 2. The formula works just as expected.

The Recursive Formula

Now we can finally produce a recursive formula for calculating the new row-wise position of the chosen card by simply substituting y in (1) with the right hand side of (2).

pi = pi - 1 / c + r(c / 2)

(3)

The formula above gives us a way to calculate the new row-wise position p_i given the old position p_{i - 1}. The 21 trick works if and only if the recursion eventually reaches p_k = cr / 2 for some positive integer k, provided that c and r are odd and 0 ≤ p₀ < cr. A reader who haven't been paying attention might wonder why c and r have to be odd. The answer is simply that otherwise the grid won't have a middle position.

There seems to be a number of different ways to prove that the 21 trick works. A few methods that seem plausible are listed below.

1. Go backwards from p_k = cr / 2 and prove that it is possible to reach any row-wise position. Although this sounds rather combinatorial and aesthetically pleasing, it seems rather complex upon closer inspection.
2. "Solve" the recursion and calculate a non-recursive function. Show that the limit of that function is cr / 2. This might be impossible due to the integer divisions, and is beyond the scope of this Entry.
3. Show that the chosen card can never move upwards if it is above the middle row and that it can never move downwards if it is below the middle row. Show that it always changes rows. Show that it never passes the middle row. Show that if it does reach the middle row, its next row-wise position is cr / 2. This method is clear, to the point and seems practical.
4. Show that | p_i - cr / 2 | < | p_{i - 1} - cr / 2 |, preferably by treating p₀ < cr / 2 and p₀ > cr / 2 as two different cases. This method seems to delve deeply into the intricacies of mathematics.

While making no claims regarding the correctness and/or plausibility of the other three methods, this Entry uses the third method to prove that the chosen card will indeed arrive at cr / 2 sooner or later.

Why it Works

The proof is in four parts, as outlined above. The first part shows that the chosen card cannot move in the wrong direction, the second shows that the card always moves, the third shows that the movement of the card is limited by the middle row and the fourth shows that the card moves to the middle column if it's in the middle row. The first two parts combined prove that the chosen card always moves towards the middle row. Combined with the third part, they show that the card is in fact always moved to the middle row. All four parts together state that the chosen card is always moved to the middle of the grid.

Direction of Movement

Since we're trying to prove something based on which row the chosen card is in, we had better construct a formula that tells us how the y-value changes. This is rather easy; just substitute the p in (2) with the right hand side of (1) to get a new recursive formula.

yi = (yi - 1 + r(c / 2)) / c

(4)

[Not done.]

Constant Movement

Let's consider a square grid, i.e. when r = c. Now let's see what happens if at some step i in the trick, the chosen card is in the same row as it was during the previous step i - 1.

1:	yi - 1	=	yi
2:	yi - 1	=	(yi - 1 + r(r / 2)) / r
3:	yi - 1	=	(r(r / 2)) / r
4:	yi - 1	=	r / 2

Apparently, if the card doesn't change rows it's already in the middle row. The omission of y_{i - 1} in line 3 might seem a bit cryptic. Naturally, this has something to do with integer division. Since we're dividing by r, an integer that is greater than y_{i - 1}, and r divides r(r / 2), the variable y_{i - 1} can be omitted without changing the result. It is, in fact, the bit that is 'shaved off' by the integer division. For example, (8 + 3) / 4 = 2, which is equal to 8 / 4. The 3 disappears completely in the process since it's less than 4.

If r < c, then y_{i - 1} < c (obviously, y_{i - 1} < r, or the chosen card wouldn't be in the grid), and in that case we can perform the same kind of omission of y_{i - 1} when dividing by c.

1:	yi - 1	=	yi
2:	yi - 1	=	(yi - 1 + r(c / 2)) / c
3:	yi - 1	=	(r(c / 2)) / c
4:	yi - 1	=	r / 2

Here, line 4 requires an explanation. It isn't perfectly obvious that r(c / 2) divided by c equals r / 2. To even begin to understand this division we must keep in mind that this is an integer division, and both r and c are odd. Therefore, c = 2m + 1 and r = 2n + 1 for some integers m and n³. Now we can express the division such that we can produce an actual result.

(r(c / 2)) / c = (2n + 1)((2m + 1) / 2) / (2m + 1) = (2n + 1)m / (2m + 1) = (2mn + m) / (2m + 1)

Now, n(2m + 1) + (m - n) = 2mn + m, and by dividing each side by 2m + 1, we see that n = (2mn + m) / (2m + 1). Note that this only works because n(2m + 1) is obviously divisible by 2m + 1, and m - n is positive (as implied by r < c) and therefore equals zero when divided by 2m + 1.

[Currently working on proof for r > c.]

Limited Movement

Remembering that c and r are odd, we move on to the next part of the proof in which we'll only have to use a bit of algebra. Let's consider the case when the chosen card is above (or in) the middle row.

1:	yi - 1	≤	r / 2
2:	yi - 1 + r(c / 2)	≤	r / 2 + r(c / 2)
3:	(yi - 1 + r(c / 2)) / c	≤	(r / 2 + r(c / 2)) / c
4:	yi	≤	(r / 2 + r(c / 2)) / c
5:	yi	≤	((2n + 1) / 2 + (2n + 1)((2m + 1) / 2)) / (2m + 1)
6:	yi	≤	(n + (2n + 1)m) / (2m + 1)
7:	yi	≤	(2mn + m + n) / (2m + 1)
8:	yi	≤	((4mn + 2m + 2n + 1) / (2m + 1)) / 2
9:	yi	≤	(2n + 1) / 2
10:	yi	≤	r / 2

Hence, if at one point the card is above or in the middle row, the next step will not move it below the middle row. Although most of the algebra above is straightforward, the extra 1 introduced in line 8 might require some justification. The following is a simplified version of the introduction of the 1; x = (2x + 1) / 2. In this case, if we keep in mind we're dealing with integers, we can plainly see that the extra one divided by two equals zero, and therefore its introduction doesn't really change anything. Not counting that without it, the proof wouldn't work.

The proof for when the chosen card is below the middle row is very similar; we can simply change the 'less than or equal' sign to a 'greater than or equal' sign. The combination of these two proofs states more than the fact that the movement of the card is limited by the middle row; it also proves that if the card is already in the middle row, it can't leave it.

Final Centering

If the chosen card is in the middle row, its row-wise position p_i divided by the number of columns equals r / 2. Combining this with (3), we see that p_{i + 1} =r / 2 + r(c / 2). Again, the key is that both c and r must be odd for the trick to work. The rest is algebra.

r / 2 + r(c / 2) = (2n + 1) / 2 + (2n + 1)((2m + 1) / 2) = n + (2n + 1)m = 2mn + m + n

cr / 2 = (2m + 1)(2n + 1) / 2 = (4mn + 2m + 2n + 1) / 2 = 2mn + m + n

Thus, p_{i + 1} = cr / 2 = p_k, which means that if the chosen card is in the middle row, it's moved to the middle of that row during the next step. This is an excellent example of something that is perfectly obvious if you look at it practically, but can be expressed in such abstract terms that everyone forgets the point.

Number of Steps

The needed number of steps to reach the middle of the grid seems to be log_ccr⁴ rounded up to the nearest integer. The reason for this is that the position to which a chosen card is moved depends on its y value (which row it's in) alone. Thus, regardless of which of the c positions in that row it inhabits, the card will move to a certain position in the grid. Therefore we can draw the grid as a tree by drawing an edge between each position in a row and the position to which the card will move from that row. This produces a c-nary tree⁵ when c = r, but the tree is only nearly c-nary otherwise.

The card always moves towards the root - the middle of the grid - and thus the maximum number of steps is equal to the height of the tree, which is log_ccr for a c-nary tree. Since the height of a tree can't be a real value, the log-value needs to be rounded up.

Final Notes

Hopefully, the readers of this Entry now know more about the 21 trick (and the sanity of the average h2g2 Researcher) than they ever hoped to know. In any case, they can sleep a little better at night knowing that there is no chance that the 21 trick won't work when performed correctly, and that it can in fact be performed with any odd number of cards (as long as each card can be uniquely identified) and odd numbers of columns and rows.