Chinese Remainder Theorem and Cards - Numberphile

Summary

This video describes a card trick called 'The Last Cards Match,' originally popularized by Martin Gardner, with a unique mathematical twist. Two decks of cards, arranged in opposite orders, are shuffled based on the letters of the word 'Numberphile.' The trick relies on modular arithmetic and cyclic permutations, where the number of shuffles matches specific modular properties. By using the Chinese Remainder Theorem, the trick guarantees that all card pairs will match, regardless of the shuffle order. The video showcases how mathematics can create surprising outcomes in card tricks, illustrating the interplay between magic and math.

Takeaways

• 🃏 The trick involves two sets of cards, each containing the numbers 1, 2, 3, 4, arranged in opposite orders (one ascending, one descending).
• 🔄 Shuffling in this context means taking the top card and placing it at the bottom, and the participant chooses which deck to shuffle for each letter of the word 'numberphile.'
• 🎩 After multiple shuffles based on the letters of 'numberphile,' pairs of cards are set aside, eventually revealing that all pairs match in number.
• 🤔 The trick is mathematically based on modular arithmetic, with the number of letters in 'numberphile' (11) being congruent to -1 modulo the number of cards (4).
• ⏳ The shuffling process cyclically permutes the cards in each deck, with the left deck (red) moving forward and the right deck (black) moving backward.
• 🧮 The trick works with any number of cards, not just four, and relies on the relationship between the number of shuffles in each deck (L + R = 11).
• 📏 The trick generalizes to any M-number of cards, and the shuffles result in the same top card emerging from both decks after each round.
• 🧙‍♂️ The number 11 is special because it is congruent to -1 modulo 4, 3, and 2, which ensures the trick works as the decks are reduced in size.
• 📚 The method to determine the key number (like 11) for any M involves solving a system of congruences using the Chinese remainder theorem.
• 🔗 The script encourages viewers to try the trick themselves, noting that the number or phrase used can vary depending on the number of cards.

Q & A

What is the main concept of the card trick described in the script?

The card trick, known as 'The Last Cards Match,' involves shuffling two sets of cards in opposite orders and performing specific shuffles to ensure that the top cards of both decks match at the end. The trick leverages modular arithmetic to achieve this outcome.

How are the two sets of cards initially arranged?

The two sets of cards are arranged in opposite orders: one set is in the order 1, 2, 3, 4 (ace is one), and the other set is in reverse order 4, 3, 2, 1 (ace is also one).

What is the specific method of shuffling used in this trick?

The shuffling method used involves taking the top card of a deck and placing it at the bottom. This process is repeated as many times as specified by the letters in the word 'numberphile.'

How does the concept of modular arithmetic apply to the trick?

Modular arithmetic is used to track the positions of the cards after each shuffle. The trick exploits the fact that the total number of shuffles corresponds to a number that is congruent to -1 modulo the number of cards in the deck.

Why is the number 11 significant in this card trick?

The number 11 is significant because it corresponds to the number of letters in the word 'numberphile' and is congruent to -1 modulo 4 (the number of cards in each deck). This property ensures that the trick works as intended.

What happens after each set of shuffles in the trick?

After each set of shuffles, the top cards of both decks are set aside. The process is repeated until all cards have been set aside, and in the end, the pairs of cards that were set aside match in value.

What mathematical concept is used to solve the system of congruences in the trick?

The Chinese Remainder Theorem is used to solve the system of congruences in the trick. This theorem helps find a number that satisfies multiple congruences simultaneously, even when the moduli are not co-prime.

What is the significance of the phrase 'numberphile' in the trick?

The phrase 'numberphile' is used as a mnemonic device to dictate the number of shuffles for each deck. Each letter in the word corresponds to a shuffle, ensuring that the sequence of shuffles follows a specific pattern that leads to the cards matching.

Can this trick be performed with a different number of cards?

Yes, the trick can be performed with a different number of cards. However, a new key number that satisfies the necessary modular congruences must be chosen to ensure the trick works.

What would change if the trick were performed with more cards?

If the trick were performed with more cards, a longer phrase with a number of letters corresponding to a number congruent to -1 modulo the number of cards would be required. The modular arithmetic calculations would also be adjusted to account for the increased number of cards.

Outlines

00:00

🃏 Magic Card Trick: A Shuffle Challenge

The first paragraph introduces a card trick using two sets of cards, one arranged in ascending order (1, 2, 3, 4) and the other in descending order (4, 3, 2, 1), with spades and hearts representing the suits. The trick involves shuffling the decks by moving the top card to the bottom based on choices dictated by the letters in the word 'Numberphile.' The participant is asked to select which deck to shuffle for each letter, and the outcome is that certain cards emerge on top, which are set aside. The process is repeated three times, and the final result is that all remaining pairs of cards match, leading to the reveal that the trick was based on a concept called 'The Last Cards Match,' originally described by Martin Gardner.

05:07

🔢 The Mathematical Secret Behind the Trick

The second paragraph dives into the mathematical explanation behind the card trick. It details how the trick works with any number of cards, using modular arithmetic to explain the cyclic nature of the shuffling process. The paragraph describes how the number of shuffles (dictated by the letters in 'Numberphile') leads to a specific outcome where the top cards of both decks match due to their positions being congruent modulo the number of cards. The key lies in the number 11, which is congruent to -1 modulo 4, 3, and 2, making it a 'magic' number that ensures the trick works as described.

10:14

🃏 Applying the Trick with Other Numbers

The third paragraph extends the discussion by generalizing the card trick to different numbers of cards and different key numbers. It explains that the trick can be adapted using larger sets of cards by solving a system of simultaneous congruences, a concept tied to the Chinese Remainder Theorem. The paragraph concludes by suggesting that any key number that is congruent to -1 modulo the sequence of card numbers will work, and hints that different words or phrases could be used for different setups, maintaining the trick's magical effect. The paragraph also directs viewers to additional resources for trying out mathematical card tricks.

Keywords

💡Shuffling

In the video, shuffling refers to the specific action of taking the top card from a deck and placing it at the bottom, repeatedly. This controlled form of shuffling is used to manipulate the order of cards in a predictable way, forming the core mechanism of the card trick. It’s central to understanding how the positions of cards change and match between the two decks during the performance.

💡Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers where numbers 'wrap around' upon reaching a certain value, known as the modulus. In the context of the card trick, modular arithmetic is used to describe how cards cycle through positions as they are shuffled. For example, with four cards in a deck, the values cycle between 1 to 4, and then back to 1, mimicking a clock’s behavior. This concept is crucial for understanding how the cards match up after a series of shuffles.

💡Numberphile

Numberphile is used as both a phrase and a sequence to determine the number of shuffles in the card trick. Each letter in 'NUMBERPHILE' corresponds to a shuffle of either the left or right deck. This sequence, chosen for its length of 11 characters, also symbolizes the fascination with numbers and their properties, which is a thematic element of the trick and the broader content produced by Numberphile.

💡Chinese Remainder Theorem

The Chinese Remainder Theorem is a mathematical theorem used to solve systems of simultaneous congruences. In the video, it’s mentioned as a method to generalize the card trick for any number of cards by finding a key number (like 11) that fits specific modular conditions across different deck sizes. It illustrates the deeper mathematical underpinning of the trick and shows how the trick can be adapted to different scenarios.

💡Cyclic Permutation

A cyclic permutation is a specific type of permutation where elements are rotated in a cycle. In the context of the card trick, each shuffle acts as a cyclic permutation, rotating the cards in a specific order within each deck. This concept is important for understanding how shuffles affect the arrangement of cards, leading to the final matched pairs in the trick.

💡Pairwise Matching

Pairwise matching refers to the outcome of the trick where cards from the two decks are compared in pairs, and they match in value. This surprising result is the climax of the trick and relies on the mathematical properties of the shuffling process. It illustrates the power of the underlying mathematics to produce seemingly impossible results through controlled randomness.

💡Martin Gardner

Martin Gardner was a popular mathematics and science writer who introduced the original version of the card trick called 'The Last Cards Match.' The video’s variation of this trick builds on Gardner’s work by adding layers of mathematical complexity, making the trick not only a demonstration of probability but also a deeper exploration of modular arithmetic and cyclic permutations.

💡Magic Number

The 'magic number' in the context of the trick refers to 11, which is the number of letters in 'numberphile' and also has special properties in modular arithmetic (e.g., -1 modulo 4, 3, and 2). This number’s unique relationship with the sequence of card arrangements underpins the trick’s success, demonstrating how specific numbers can create order in seemingly chaotic processes.

💡Simultaneous System of Congruences

A simultaneous system of congruences involves multiple congruence equations that need to be satisfied simultaneously. In the card trick, finding a number that fits specific modular conditions across different deck sizes (like mod 4, 3, and 2) is crucial. This system helps in choosing the right number of shuffles (like 11) that make the trick work, revealing the interplay between various levels of the problem.

💡Reverse Order

Reverse order in the video refers to one of the decks being arranged in descending order (4, 3, 2, 1) while the other is in ascending order (1, 2, 3, 4). This opposite ordering is crucial because it sets up the conditions for the trick to work as the shuffles gradually align the cards in a way that results in matching pairs. The contrast between the two orders is a key aspect of the trick’s setup.

Highlights

Introduction to a card trick involving two sets of cards in opposite orders (spades and hearts).

Explanation of the shuffling method: taking the top card and placing it at the bottom.

The shuffling process is guided by the letters in the word 'numberphile', allowing for interactive decision-making.

First round of shuffling reveals two matching cards at the top of the decks.

Second round of shuffling with the word 'numberphile' also results in matching cards at the top.

Final round of shuffling reveals all pairs of cards match, surprising the audience.

The trick is a variation of 'The Last Cards Match', a classic card trick popularized by Martin Gardner.

Introduction to the concept of modular arithmetic and its application in the card trick.

Explanation of the cyclic permutation of cards in both decks during shuffling.

Discussion on the mathematical principle behind the trick, using modular arithmetic and the Chinese Remainder Theorem.

Demonstration of how the number 11 (from 'numberphile') is crucial to the trick's success.

Explanation of the relationship between the number of shuffles and the emergence of matching cards.

Discussion of the mathematical proof that L + 1 and M - R are congruent modulo M, ensuring matching cards.

Generalization of the card trick to any number of cards, using a system of congruences.

Final remarks on how the trick can be adapted to different scenarios with larger sets of cards.

Transcripts

Two sets of cards, 1 2 3 4, ace is one, 4 3 2 1, again ace is one,

spades and hearts, black and red. They're in opposite orders. I now turn them over

and

we're going to shuffle them and you decide which one to shuffle but the shuffling means always to take the top card and

put it at the bottom. That's shuffling.

Okay, that's one shuffle.

And, each time we shuffle, you tell me which one to shuffle, I'll shuffle that one.

Okay, so let's shuffle a number of times. Well, what can we say? Oh, let's use the phrase numberphile shall we?

So numberphile: N-U-M-B-E-R-P-H-I-L-E

So, for each of these letters you say well, shuffle the right one or the left one. And you can say

You know, N-U-M

B-E-R-P-H and so forth.

You can choose whatever you like. Okay, so Brady, you tell me which one to shuffle, then. So left or right?

-So, N -Yeah

U

M

B

-E -Yes, sorry, E

R

P

H

I

L

E

Okay, so those two cards emerged to the top as a result of your choice, I didn't choose this.

So I'm going to set them aside. Yeah, two of them.

Now, we repeat numberphile again and for each of those letters

We shuffle either of these and you choose which ones shuffle for each of those data. So which one do you want?

Let's do . . . Let's do all of them that one.

Oh my god. So, okay N-U-M

B-E-R

P-H-I

L-E

I wasn't expecting this. Okay those two cards emerged to top.

In fact, this one didn't move but this emerged to the top so I put these aside.

Now one last time, numberphile, and you choose which one to shuffle.

OK

N

U

M

B

E

R

P

H

I

L

E

OK, these two emerged to the top,

and these two are left over.

OK.

Now if we were really lucky and luck doesn't come except to the deserving.

Because numberphile is such a magic phrase,

these two

may be the same number.

You know numberphile means "liking numbers" and these two numbers like each other, of course, 2 and 2, but that might have been luck.

But if we really believe in that magical numberphile, these two might have matched

Remember, you chose which one to shuffle, yeah? I didn't. That's surely not possible.

But what's really impossible would be impossible?

Is for the next two to match and the surprise par surprise, the last two also match.

So they all match pair-wise.

Lovely! Numberphile -- I knew it was magic.

We knew it was magic.

So the trick that I have just shown you is a classic trick which was described for the first time as far as I know

by the late Martin Gardner called The Last Cards Match

and I made a variation on this and the variation is a little slower than the original trick

But it's also mathematically more interesting. So I'd like to reveal the secret.

What we had was two piles of cards

You have 1, 2, 3, 4 in one order

and 1, 2, 3, 4

Or if you like 4 3 2 1 in the reverse order, and these should be thought of as like clocks

Okay, so a clock has you know, 1, 2, 3, 4 all the way to 12 and then it starts all over again.

So you are doing modular arithmetic here

Also, if you go one two, three four, and if you want to go five here six here seven here eight here

And so we can keep going. Okay, you remember that our way of shuffling was very special

We took the top card and then put it at the bottom

So you . . . as you keep repeating this you are cyclically or cyclically depending on the side of the Atlantic

Permuting those cards so you go from here to here to here to here and keep going

Whereas in the other deck which had the reverse order you go from to here to here to here, okay?

We had four cars but let's generalize and explain a little bit because this card trick works with any number of cards in general.

Let's say that you have cards one two three and so on

Arranged in a cyclic fashion all the way to M

So let's say M minus 2

M minus 1. M is number . . . total number of cards and I choose that M for a purpose on the other side you have because

In the reverse order M, M minus 1, M minus 2 and dotto dotto

You keep going and then 3 2 1 you come back like that. OK?

So in our card trick M was four, but in general it works and one shuffle does this:

you start from one and go to 2 and

2 goes to 3 and here you go from M to M minus 1 and M minus 1 to M minus 2 and that kind of thing.

Suppose that on the left, that is the red pile you made

L

shuffles

On the right you made R shuffles, L as in left, R as in right.

Well, the total number of shuffles that we made was the number of letters in "numberphile"

N-U-M-B-E-R-P-H-I-L-E

11 letters. So we know that L plus R was 11 for us.

So L and R are not independent. If you chose to shuffle the red deck L times,

automatically you are shuffling, whatever you else you do, the right deck R times, but R equals 11 minus L.

And if you choose to shuffle the right deck, that is the black deck, R times,

you cannot help shuffling the left deck, that is the red deck, 11 minus R times. So you have that relationship.

So let's start shuffling.

Say that you shuffle the red deck L times: 1 goes to 2. So each time you increase by one. 2 goes 3 and

if you keep going after L shuffles, it takes a little bit of thinking to

convince ourselves

You arrived at not L, but L plus 1

after L shuffles.

On the right, black deck

After one shuffle, you go from M to M minus 1, M minus 1 to M minus 2,

And if you keep going, and that is slightly less confusing,

at the end, you arrive at, after R shuffles, M minus R.

So, after those shuffles

the cards that emerge on the top of each deck is L plus 1 and M minus R. Those two cards emerge.

We used eleven

But let's say that L plus R was some number more generally which was chosen to be some number

Which is congruent minus 1 modulo M where M is the number of cards in each deck

So for us M was 4 and for us 11 was the chosen number and eleven is minus 1 mod 4, by the way.

Where have you pulled . . .yeah, where have you pulled that minus one mod M from?

We'll see why this minus 1 becomes useful in a moment

That's . . . that's part of the magic

OK.

You have to do magic at some point, okay?

So, let's see what L plus 1 is compared with M minus R and we'll see that they are actually the same thing. You see?

Because L we see is equal to . . . look at this,

L plus R equals minus 1, or congruent minus 1, so L equals minus 1 minus R.

Let's not forget plus 1, so minus 1 plus 1 cancel, and you are left with only

Minus R. So this is modulo M

But minus R can be written by modulism again as M minus R. That's the same thing, module M.

Doing it like that. Ok, and so what we see is that

Module M, L plus 1, the top of the red deck and M minus R

top of the black deck,

are actually the same. So after those shuffles, the same cards

emerge on the top. You put them aside now you have to start over again.

And then the number of cards M changes, but that's where minus 1 becomes useful.

11, that we chose,

that's the number of letters in numberphile, has the beautiful property that it is

indeed congruent minus 1 mod 4.

That's the initial number of cards in each deck. After I set out the top cards together, you have now . . .

Do the same thing mod three?

But 11 is also

minus 1 mod 3 and

Next stage, you have you lost one pair of cards

You have to do mod 2, but amazingly 11 is also

Minus 1 mod 2 and that is why this number, magic number, key number, 11, worked.

Just as you descended those different moduli, the chain of order, mod 4, mod 3, mod 2

Okay, and that's how I chose 11.

Or, if you want to do this card trick in other . . . with other parameters

For example with larger number of cards and 10 and 12 and so forth and so forth

All you have to do is to solve this, what is called simultaneous system of congruences.

Like a simultaneous system of equations but you are doing modular arithmetic and

There is a way of doing it's called Chinese remainder theorem

By the way, the standard way we teach and learn Chinese remainder theorem has modules all co-prime.

They should all be co-prime, but this is a tricky case

of Chinese remainder theorem because for example 2 and 4 are not co-prime.

But even there there is a version of Chinese remainder theorem that works.

So this kind of congruence . . . system of congruence is always solvable. So you give me any M,

so use a lot of cards if you like

but just reverse the orders here and here and you find some key number which is equivalent to 11

But some X which is minus 1 mod M

also minus 1 mod M minus 1, minus 1 mod M minus 2,

so all the way down all those moduli. You should always be minus 1. You should solve

those simultaneous equations for X and using that

number of phrases, this trick always works.

So if I had two powers of ten, there'd be some other word I'd be having to use?

That's right, but it could be a longer phrase and longer word and

But I'm sure it would be some word, like numberphile, which would be special significance to you.

If you'd like to try your hand at some of the mathematical card tricks you've seen on numberphile, but don't own a deck of cards

Well, you could try these numberphile ones. There's a link with more information about them down in the video description

And if you'd like to see more videos about playing cards, well,

we've got a playlist for that. Links are on the screen and again down in the description.