- Membership
- Publications
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

**June 2007**

How many ways are there to form a row of ten face-up cards, disregarding values, so that there are no adjacent red cards? The answer, which turns out to be 144, involves the standard Fibonacci sequence. This starts with seeds 1, 1, and then adds two consecutive terms to determine subsequent terms:

1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | ... |

Starting with arbitrary seeds yields what are sometimes known as Gibonacci (for generalized Fibonacci) sequences, e.g., see Art Benjamin and Jennifer Quinn's delightful MAA book *Proofs That Really Count: The Art of Combinatorial Proof*. The Gibonacci sequence starting 2, 1 produces another famous sequence, the Lucas numbers:

2 | 1 | 3 | 4 | 7 | 11 | 18 | 29 | 47 | 76 | 123 | 199 | ... |

Starting with 5, 3 instead, we obtain:

5 | 3 | 8 | 11 | 19 | 30 | 49 | 79 | 128 | 207 | 335 | 542 | ... |

In 1962, the incredibly prolific Canadian magic inventor Stewart James published "The AAG Principle," in which a volunteer filled in numbers in a grid with a pen. It was based on his discovery (dating back to at least 1958) of the periodicity of generalized Fibonacci sequences reduced mod 9. He actually considered the closely related concept of reducing each term to its digital root (also known as casting out nines). For instance, to reduce 786 to its digital root we add its digits 7 + 8 + 6 = 21, and then add those digits to get 2 + 1 = 3, which is of course the remainder when 786 is divided by 9. Reducing 81 yields 9, which is not processed any further. In general, the possible digital roots of a number n are 1, 2, ..., 8, 9, i.e., the least positive residue of n mod 9 (these mostly agree with the remainder of n upon division by 9, namely, 1, 2, 3, ..., 8, 0). We refer to these sequences reduced to digital roots as "Gibonacci sequences mod 9" (it being understood that we use 9 in place of 0).

Reducing the above three Gibonacci sequences mod 9, with a few extra terms listed this time, we get:

1 | 1 | 2 | 3 | 5 | 8 | 4 | 3 | 7 | 1 | 8 | 9 | 8 | 8 | 7 | 6 | ... |

2 | 1 | 3 | 4 | 7 | 2 | 9 | 2 | 2 | 4 | 6 | 1 | 7 | 8 | 6 | 5 | ... |

5 | 3 | 8 | 2 | 1 | 3 | 4 | 7 | 2 | 9 | 2 | 2 | 4 | 6 | 1 | 7 | ... |

Sixteen terms have been listed in each case, which is sufficient to give a hint of one key property discussed below. But first we need to focus on an even more basic fact. Let's extend the ordinary Fibonacci sequence mod 9 to show twenty-seven terms:

1 | 1 | 2 | 3 | 5 | 8 | 4 | 3 | 7 | 1 | 8 | 9 | 8 | 8 | 7 | 6 | 4 | 1 | 5 | 6 | 2 | 8 | 1 | 9 | 1 | 1 | 2 | ... |

The cat is out of the bag: the Fibonacci sequence mod 9 repeats itself after twenty-four terms. This key property holds for all Gibonacci sequences mod 9. We can thus consider the sequence to loop back on itself, yielding a Gibonacci bracelet of twenty-four beads. (Note that all bracelets considered here are oriented: if displaying these in a circle we must first agree on the direction of travel.)

But wait, there's more! If we line up the last twelve beads of the above bracelet underneath the first twelve—with the thirteenth bead going under the first one and so on—we obtain:

1 | 1 | 2 | 3 | 5 | 8 | 4 | 3 | 7 | 1 | 8 | 9 |

8 | 8 | 7 | 6 | 4 | 1 | 5 | 6 | 2 | 8 | 1 | 9 |

Clearly the beads pair up according to "complements in 9"—except that 9s pairs up with other 9s. Thus, each bead can be predicted from the one that came twelve before it; in a sense, the second half of the bracelet is the additive inverse of the first half. This property holds for all Gibonacci sequences mod 9, e.g., the seventeenth term in the Lucas sequence mod 9 above must be 2, since the fifth term is 7. The twenty-second term in the sequence starting with 5, 3, must be 9, because the tenth term is 9. If we imagine the beads of these Gibonacci bracelets arranged in a circle, then these are balanced in the sense that the sum of two diametrically opposite beads is always 0 mod 9.

It's almost true to say that the period of any Gibonacci sequence mod 9 is 24, but there are some exceptions which we avoid in what follows: if there are adjacent beads (e.g., the seeds!) which are *both* multiples of 3, namely 3, 6 or 9, then the sequence is less interesting and has a smaller period (which must divide 24). Such sequences give rise to shorter orbits/bracelets.

Leaving aside such dull exceptional cases, there is one more fact which holds for all Gibonacci sequences mod 9: they contain exactly one balanced pair of 9s per orbit. The remaining beads form eleven "complementary in 9" pairs. Thus, if we sum any consecutive twenty-four values, we must get as our total 9x11 + 9 + 9 = 117, hence the name Stewart James attached to this phenomenon, the AAG principle (A and G being the first and seventh letters of the alphabet, respectively).

Chapter 14 of the mammoth 1750-page *The James File*—*Volume One* (Hermetic Press, 2000) has some delightfully diverse applications of all of the above, including two 1978 Martin Gardner prediction tricks based on the principle. The exceptional cases are also treated there, yielding total sums of either 135 (=ACE), or in the case of all 9s, 216 (=BAF). Most of what follows is inspired by this source, with arrays of cards replacing grids of written numbers. Later on, we'll consider variations on the basic theme in a different direction. There is much (unexplored) potential for book forces inherent in all of this.

Hand out two identical decks of cards to a volunteer, requesting that the tens, Jacks, Queens and Kings be set aside, leaving the remaining seventy-two cards for use. Aces have value one. You'll often need five or six cards of some values for what follows, hence the need for a second deck. Explain digital roots and the corresponding "addition mod 9" (to yield a number between 1 and 9). While your back is turned, have any two cards placed face-up side by side to start a row, suggesting that if one of them has value a multiple of three, then the other should not, "as that leads to really boring and predictable results. We want total randomness here." If you know how to force a card, for instance using a Hindu shuffle, then have the first one selected in such a mammer before you turn away, while appearing to give a free choice, and have the second one selected by a more genuinely random method.

Now have those card values added, and a card of value equal to the digital root of the sum placed to the right of the growing row. "For instance," you say, "A deuce followed by a seven results in a nine, but a deuce followed by an eight results in an ace. Now have the values of the second and third cards added, and an appropriate fourth card placed beside those three. Have the volunteer proceed in this manner until the row contains five cards, then have the sixth card placed underneath the first one to start a second row of five, and so on, until there are twenty-five cards displayed in a five by five array. Have each card turned face-down before you turn back.

Unknown to the volunteer and audience, the following properties hold.

- The total of all twenty-five card values is 117 plus the value of the last card (which has the same value as the first card).
- The value of the twenty-fourth card added to the last one reveals the value of the second card.
- The value of the middle (thirteenth) card on display is the compliment in 9 of the first/last one.

Several presentational options suggest themselves—all the moreso if you already know the first card; but let's assume that you do not.

You might stress, "I couldn't possibly know the value of any of these twenty-five cards. Do you remember your two starting card values? Please look at them again to make sure." As the volunteer does this, start gathering up the rest of the cards in no particular order, but do make sure that the last two cards go on the bottom of the pile in your hand, in their original order. Invite the volunteer to insert the first two cards anywhere in this packet; somewhere along the line you need to find the chance to peek at the bottom two cards, it's all you need to figure out the total sum as well as the original two seed values.

For example, if the last two cards have values 4 and 8, then the first card must have been an 8 too, and the second card a 3 (since 4 + 8 reduces to 3). Shuffle the packet of twenty-five cards and hand it out for totalling, remarking that you are going to write down a prediction. On one side of a piece of paper, write the sum of 117 and the last card value, i.e., 125 = 117 + 8 in our example. On the reverse, write the two starting card values, which you now know. Place the paper on the table, with the total on top, covered by a face-up penny.

When the card values are totalled and the sum announced, you can point to the piece of paper and say, "I predicted that total and left it sitting here before you started!" If the first/last card *is* an 8, perhaps as a result of a force, go for the "gold": point to the face-up penny and say, "One two five is represented by the letters ABE, and that's why I had Abe Lincoln guarding my prediction all along." Draw attention to Lincoln on the penny, before you remove it to reveal the 125 written underneath.

You *could* add, "Of course, I knew the total was 125 because I added up all of the numbers myself, having worked them out in my head. You did start with 8 and 3 right?" before turning over the prediction slip to reveal the 8 and 3 written there. Use your judgement; it depends on your audience. There are times when it's smarter—and more mysterious—*not* to appear to know too much!

You could also start by having each of you pick one random card, so that you openly know either the first or the second card (and know which one you know!), adjusting the presentation accordingly.

Another interesting property which James considered for the kind of five by five array above is that the sum of all four corner values (two of which must be the same) is necessarily 9, 18, or 27; this too can be exploited to good effect with a little imagination.

Further variations one could investigate include constructing the five by five arrays in spiral fashion, either from the center out, or vice versa.

Recall that in the five by five arrays already discussed, the middle card value added to the first one is 9. Let's assume that you know the identity of the first card, either by having forced it at the outset, or by peeking at the last card later on (when gathering them all up). If this is a 3, then the thirteenth card is a 6. You may even be able to control what suit that 6 is, e.g., by only offering cards of one suit to the volunteer when she is working on the middle row of the array; this *can* be done with your back turned, if you fuss all along about the addition mod 9 and ditigal roots, and only hand over clumps of cards "on demand," appearing to pay no attention to them. There has been no mention of suits yet, so the heat is off in that regard!

Again, stress that you couldn't know the identity of a single card, regardless of the truth of that statement, and gather up all the cards, jumbling the first two rows but being careful to get the middle row in order underneath these ten cards and on top of the last ten cards (keeping the last card at the bottom if you need to peek at it). You can now do assorted shuffles to the top and bottom thirds of the packets, which will give the impression of genuine mixing, while maintaining the thirteenth card in the exact middle. "You picked the original two cards, and used those to generate an array of twenty-five cards, which were just thoroughly shuffled. Yet I am getting a good vibe, I believe that my lucky card (*name the card or at least the value*) is in the luckiest position." Hand the cards to the volunteer and have her count down to the thirteenth card. It should match your pronouncement.

Among the effects considered decades ago by James *et al* are ones featuring arrays (some rectangular and others circular) of twelve numbers constructed by a volunteer, who then writes the thirteenth number to one side. Needlesstosay, the magician has predicted that last number in advance.

We are free to reduce Gibonacci sequences mod any natural number m; it turns out that they are always periodic. For the Fibonacci sequence, the periods are 3, 8, 6, 20, 24, 16, 12, 24, 60 and 10 for m = 2, 3, 4, 5, 6, 7, 8, 9, 10 and 11, respectively. As Marc Renault remarks in his masters thesis, mod m there are m^{2} possible pairs of residues, and so in the Fibonacci (and likewise in any Gibonacci) sequence, the pigeonhole principle guarantees that some pair of consecutive terms must repeat. Since any pair of consecutive terms completely determines the entire sequence, periodicity is assured.

For Gibonacci sequences the period mod m may be less than the corresponding Fibonacci period. For instance, mod 5, the Fibonacci sequence itself has period 20, but the Lucas sequence has period 4 (more on this below). In what follows, we only consider odd moduli m. The cards used will of course depend on the choice of m. The interested reader can explore what happens for even m as an exercise.

When m = 3 there is a unique (non-trivial) balanced Gibonacci bracelet with eight beads and sum 15, got by looping the last bead of 1 1 2 3 2 2 1 3 back to the beginning. Note that Fibonacci and Lucas agree here!

It turns out that m = 5 is a little odd, resulting in two possible non-trivial bracelets with different sums for twenty consecutive beads, namely the Fibonacci one 1 1 2 3 5 3 3 1 4 5 4 4 3 2 5 2 2 4 1 5 with sum 60, and the Lucas one which consists of five copies of 2 1 3 4 lined-up, with total sum 50. Both bracelets are balanced.

When modifying some of the earlier presentations to the mod 5 situation, it may be worth ensuring that the first value selected is 5, leaving the volunteer four choices, each leading to a balanced orbit with sum 60 (note that there are four 5s). A seven by three array would have sum 65, predictably enough. If you do allow two totally free choices, have the volunteer stop at twenty beads, and merely ask if the resulting display has "many fives" in it; the answer will tell you all you need to know. The eleventh bead is predictable from the first one in all cases: these two must sum to 0 mod 5.

The case m = 11 seems attractive, because of the potentially small period (10), but there are some surprises in store here. Some Gibonacci sequences mod 11 have period 5 (e.g., the one with seeds 1, 4), which is not a problem, but the non-trivial ones with period 10 can have sums 44, 55 or 66, and none of them (regardless of period) is balanced!

We close by looking at the case m = 7.

All Gibonacci sequences mod 7 repeat after sixteen terms. The corresponding bracelets are balanced: the sum of two beads eight apart is 0 mod 7. Excluding the trivial case of all 7s, there are always exactly two 7s present (which are diametrically opposite each other), so that the sum of all sixteen beads is 7x7 + 7 + 7 = 63—perhaps this should be called the FC Principle. It's easy and instructive to determine the few existing Gibonacci bracelets mod 7 (not to mention those mod 9 from before!).

One possibility is to have a volunteer construct a four by four grid from two seed cards, using addition mod 7, and predict the sum (63). Since it's the same total everytime, this is not a trick to repeat. Perhaps a better idea is to note that half of sixteen, plus one, is nine: the value of the ninth card in a three by three array will be 9 minus the value of the first card. If, for the sake of variety, the array is constructed by going around the perimeter from some starting place, the last card would be placed in the center. This is certainly a more reasonably sized array; five by five (and even four by four) arrays are a bit arduous for the average volunteer to work through! Also, you can use just one deck here, and with a little thought you should be able to force the suit too, which will lead to an impressive prediction.