ไม่สามารถเล่นวิดีโอนี้
ขออภัยในความไม่สะดวก
Chinese Remainder Theorem and Cards - Numberphile
ฝัง
- เผยแพร่เมื่อ 7 ส.ค. 2018
- Numberphile Playing Cards: bit.ly/NumberphileCards
More card videos: bit.ly/Cards_Shuffling
More links & stuff in full description below ↓↓↓
Featuring Tadashi Tokieda, a professor of mathematics at Stanford University.
More Tadashi Videos: bit.ly/tadashi_vids
Discuss this video on Brady's subreddit: redd.it/95llyc
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from Math For America - www.mathforamerica.org/
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Editing and animation in this video by Pete McPartlan
Patreon: / numberphile
Numberphile T-Shirts: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9
Numberphile Playing Cards: bit.ly/NumberphileCards
More card videos: bit.ly/Cards_Shuffling
What's the back of the cards like? The ones on the video have non-symmetrical backs, meaning they are cheaters' cards.
In this video, it looks something like the Penrose tiling
the number you want for 10 cards is 2519 lol
Tadashi has the most soothing voice.
I could listen to his voice and accent forever.
Very close to George Takei
false.
for real I need him to read a mythology book or smth
Just a heads up if you want to try this trick on the masses: Abracadabra has 11 letters.
Happy Friday
(also eleven letters)
"Eleventy One" has 11 letters
Four has four letters
@@alexwang982 does pi have pi letters?
Dat Boi no
For those wondering, here is the smallest word length needed for a certain number of cards:
2 cards: 1
3 cards: 5
4 cards: 11
5 cards: 59
6 cards: 59
7 cards: 419
8 cards: 839
9 cards: 2519
10 cards: 2519
In general, it must be the LCM(2,3,4,...,m)-1 where m is the number of cards.
So, while Tadashi is right that it's theoretically possible to get a word length that's the appropriate length for this trick to work, it doesn't work so well in practice for longer than four letters.
Conor O'Neill you could use a sentence/phrase instead of a word for 5 and 6 though.
with a bit of fiddling with the mathamatics behind LCM i started calcluating by hand farther up the table. the largest stagnant part so far is 32, 33, 34, 35, 36 all having a value of 144,403,552,893,600 (minus one). the answer for 52 is over 3 sextillion
So for 5 or 6 cards I could use "This may be really tedious but it will soon turn out to have been worth it"
For 7 cards, "America" + up to the end of the first paragraph of the Declaration of Independence.
Conor O'Neill You sure your last name isn’t Chang🤓 rather than O’Neill🍺?
Tadashi is by far my favorite person on Numberphile! His videos are always fun and interesting and he is a great teacher.
Second favorite for me. Gotta love Cliff Stoll!
And don't forget about James Grime, Matt Parker, ... ;)
And Hannah Fry !
He is to Numberphile what Copeland is to 60 symbols for me. Can't help but like the guy.
Tom Michalak cliff is a legend
"You gotta do magic at some point" -- Dr. Tadashi
I learned this one with a story. You pick 4 Jacks, 4 Queens, 4 Kings and 4 Aces. You explain that there is a hotel with four rooms and that when the Jacks arrive they all get a room. Now the Queens arrive and they all get added to the Jacks, etc. etc. up to 4 Aces. During the night they start to visit eachother and argue and fight (gather the stacks clockwise and shuffling) and as long as you do not leave 1 card on the table or pick up 1 card the order will never ever change from what you need it to be to after shuffling say something along the lines of. OKAY! Now the manager of the hotel is sick and tired of the arguing and will re-order the people into the rooms. If you now take off the top card and go into 4 piles again you end up with 4 neat piles of All Jacks, All Queens, All Kings and All Aces.
how do you shuffle?
I really appreciate Professor Tadashi Tokieda's command of the English language. He speaks with more wit, clarity, and awareness in English than 99% of native English speakers that he meets. I hear him communicate so masterfully in English that my ear almost wants to start hearing his Japanese accent as the natural way to speak English.
According to his Wikipedia page, he speaks at least nine languages and he studied philology before turning to mathematics.
This is why I love him. He just jumped into my top 3 favorite scholars.
Always love a video with Tadashi!
Tadashi is one of my Numberphile favorites! He doesn't use confusing jargon to explain stuff. He gives it straight, so that you can understand these concepts intuitively!
Cheers
Dr. Tadashi's videos never cease to amaze!
Tadashi is amazing. Keep doing videos with him!!!!
I'm a simple man. I see Tadashi in the thumbnail, I click.
I'm a simpler man. I see a Numberphile video, I click.
Fastex I'm the simplest man. I see any video I click.
I was going to comment the same thing, but you beat me to it. He's great!
I'm even more simple. I start internet and I click.
I'm the most simple: I just click; that's it.
i love tadashi videos i hope i can meet him in my life and tell him he's awesome
I could listen to him talk all day!
Tadashi had the best presentation in the whole ICM 2018!
I think this would require a phrase of 59 characters to do it with a set of 5 cards; that is, 59 is the smallest number I can find which is equivalent to -1 mod 2, 3, 4 and 5.
That's right. And generally, if you want to do it with sets of m cards, the magic number is LCM(2,3,...,m)-1.
The general method (I think) is to work out the prime decomposition for each number, find the highest power for each prime, and then multiply those primes with those powers together, and take off 1. So for 6 cards, we have 2,3,2*2,5,2*3. The highest powers of 2, 3 and 5 in this sequence are 2, 1 and 1. So 2*2*3*5-1=59, which is the same as for 5 cards :)
We can verify that pretty easily. It must end with either 4 or 9 (-1 mod 5), But must be odd (-1 mod 2). That leaves us with 9, 19, 29, 39,... now for -1 mod 3 leaves us with every third on that list (9 is congruent to 0 mod 3, 19 = +1 mod 3, 29 is -1 mod 3), so the list becomes:
29, 59, 89, 119,...
Then we check for mod 4:
+1, -1, +1, -1...
And the first number that is -1 in mods 2 through 5 is indeed 59
Edit: the smallest solution for 10 cards is 2519!
That's correct. To further generalize, the number of "shuffles" required would be LCM [m,m-1,m-2,...] - 1 so for 10 cards like suggested in the end of the video, you would need 2519 shuffles!!
zh84 29 should also work, because the solution is unique up to adding or subtracting multiples of 30 (30=5*3*2, the coprime numbers of the sistem). And in fact it works!
29=25+4=30-1
29=27+2=30-1
29=28+1=30-1
Tadashi once again with the goods!!
Awesome as always
I could listen to Prof. Tokieda forever.
To find 11, you can also just take the LCM of 2, 3, and 4 and subtract 1. You know this'll be -1 mod all of them, b/c their LCM is mod 0 all of them. Similarly, you can take the LCM of 2, 3, 4, and 5 and subtract 1 to get 59, to get the smallest positive integer that is -1 (mod 2, 3, 4, and 5)
Look Who Is Back
My fav Tadashi is back😍
You'd need a phrase with 2519 letters (that's the shortest) to get the trick to work with 10 cards.
That's right. And generally, if you want to do it with sets of m cards, the magic number is LCM(2,3,...,m)-1.
Right. And that grows at least as fast as 2^(m/log(m)) and at most as fast as m^(m/log(m)). The reason is that LCM(2,3,...,m) is the product of the highest power of each prime less than m. For example 2^3 < 10 < 2^4, so 2^3 divides LCM(2,3,...,10) and 3^2 < 10 < 3^3, so 3^2 divides LCM(2,3,...,10). The number of primes up to m grows like m/log(m) and each of these primes at least 2, hence the lower bound. The upper bound comes from the fact that the prime powers are at most m.
I would suggest you'd rather use consecutive words of a given sentence so that :
The 1st word (10 cards) has length 9 (or 19, 29...)
The 2nd word (9 cards) has length 8 (or 17, 26...)
The 3rd word (8 cards) has length 7 (or 15, 23...)
...
The 8th word (3 cards) has length 2 (or 5, 8...)
The 9th word (2 cards) has length 1 (or 3, 5...)
Well you still have to find such a sentence
Might work in German.
"It was the best of times, it was the worst of times..."
Tadashi is always correct
I got that!
(at least with an extra i)
Well his given name is indeed 正 in Japanese, so the same kanji as in 正しい (tadashii)
Tadashi teaches complex topics in a way that is so simple I am amazed he look like he would be the most confusing lesson of my life
I remember reading about Chinese Remainder Theorem in the number theory book one of my professors gave me. It's cool to see a practical application ^.^
A Tadashi video?
feelsgoodman
Another way of visualising why the trick works is to superpose the two cycles (with one flipped) and go clockwise or counterclockwise for right and left. If you shuffle right m times (or any multiple of m) you end up at the starting point, but 1 less and you end up at the same point that left starts at and vice versa. With a constant sum, the variation of l and r just shifts the end point around the clock.
i don't know how to evaluate a mod function, but i did manage to get to the answer anyway. the answer is the [least common multiple of 1, 2, 3, ..., M] minus one.
so here's the table
1 card needs 0 shuffles to match
2 cards needs 1 shuffle to match
3 cards needs 5 shuffles to match
4 cards needs 11 shuffles to match
5 cards needs 59 shuffles to match
6 cards also needs 59 shuffles to match
7 cards needs 419 shuffles to match
8 cards needs 839 shuffles to match
9 cards needs 2919 shuffles to match
10 cards also needs 2919 shuffles to match
this number explodes really rapidly. especially each time you reach and pass a prime number
11 cards needs 27,719 shuffles
12 cards also needs 27, 719 shuffles
13 cards needs 360,359 shuffles
14 cards also needs 360,359 shuffles
15 cards also also needs 360,359 shuffles
every time you reach a new power of a prime, the LCM jumps by a factor of that prime
the next number of cards in this table would be 2^4 so 360,360 will double (raise by a factor of 2), and the number after that is 17^1 so it will go up by a factor of 17.
16 cards needs 720,720 - 1
17 cards needs 12,252,240 - 1
it won't change until 19^1 where it will multiply by a factor of 19, and so on
23^1 (23)
5^2 (25)
3^3 (27)
29^1 (29)
31^1 (31)
2^5 (32)
where we reach our longest stagnant break yet. 32, 33, 34, 35, 36 all share the same answer of 144,403,552,893,600... minus one shuffles needed.
whelp we are in this for the long haul we better make our way to 52 and do the whole deck, we are almost there anyway
37^1 (37)
41^1 (41)
43^1 (43)
47^1 (47)
7^2 (49)
before finally reaching our answer that 49, 50, 51, and 52 (but not 53 because that's our next prime) requires a whopping 3 sextillion shuffles
3,099,044,504,245,996,706,400 ... minus one
You're a wizard, Tadashi!
An easier way to do this trick is to ask the espectator a number from one to m (current number of cards) to shuffle from one pile. Then you choose a number from the other pile so that the sum of those numbers is k*m-1 (if there are 12 cards and the espectator chooses 11, you choose 12; if chooses 2, you choose 10).
Also, I've calculated the lowest common number for each posssible number of cards:
1 card -> 1
2 cards -> 1
3 cards -> 2
4 cards -> 11
5 cards -> 59
6 cards -> 59
7 cards -> 419
8 cards -> 839
9 cards -> 2 519
10 cards -> 2 519
11 cards -> 27 719
12 cards -> 27 719
13 cards -> 360 359
Tbh, this is the first video with Tadashi, that i didn't understood.
Doesn't matter, was still fun.
I like how he explained the -1 mod m for about five minures and never mentioned the number 12, which is sort of the key.
what do you mean
I loved this and I loved that deck ;)
Me trying to do it with 5 cards: Since there are 5 cards, we need to use a truly magic word.
You: What is it?
Me: pneumonoultramicroscopicsilicovolcanoconiosisologisticalize
You: OMG
Use the full chemical name of the Titin protein. 180K letters
Is this correct? I always thought pneumonoultramicroscopicsilicovolcanoconiosis was the full word. Would logisticalization be the process in which it forms?
You can always twist long words. Not many bother to read :P
I just added random suffixes to the word, so it's not a real word (Of course you can guess the meaning easily).
Logisticalization, to make it a noun
Whether numbers or equations or vectors or matrix etc division gives sometimes reminder. The left outs of filling called gaps. Gaps are usually prime. So division is process of opposite time patterns. When you hit a drum with sand piles the pattern is a division patterns. So spin angles are called time. It can be relative to each other. What is distance. Prime variations of angle.
Wow yaar, awesome 👏 you guys are amazing 🤩
If you want to do this exact thing at home, a simple way to force 11 is to use the phrase “magic tricks” to get your 11 letters!
that's awesome, also you could use a different phrase or key, one that works for 4, another for 3 and so on, so you don't have to figure out a super large phrase if you wanna try the trick with 10 cards
What a wonderful voice
3:10 cyclic order is preserved when doing straight cuts
How many Math tricks and puzzles were NOT published by Martin Gardner. Probably a shorter list.
Try watching Scam School and you'll find that list will gradually shrink even further!
I feel happy I could at least partially stay ahead of this one. As soon as you put down that numberphile is 11 characters I realised, oh, that's -1mod4 XD
Nice deck of cards ;o) I wish I could have attended the conference in Trondheim (the deck is from the host of the conference, Matematikksenteret) in November and heard dr. Tokieda live!
"Luck comes to the deserving" -Tadashi
Tadashi is my spirit animal.
Amazing trick
In danish he word for a magic act is "tryllekunst", which as you can see is eleven characters long, making it the ideal word for this trick as you can use it in all kind of scenarios while still maintaining the illusion of the magic the specific word possess.
Reminds me of arithmetic sequences. Very interesting
Tadashi is the real spirit of numberphile
So much this! Seeing "tricks" like this in a theatrical manner, once you realize that it is maths behind it the magic is gone.
You guys should do a video on more such tricks, the way you're presenting it is such an incredible introduction to different maths that you never lose that sense of wonder as one seeks to understand why this does what it does.
I wonder if you could somehow get three (or more) piles to do the same thing. You would probably have to change the rules a bit...
The main thing here that you shuffle two sets in different order. If you have 3 or more, two of them would be shuffled in the same order, so you always have to shuffle them the same number of times (or with some constant difference) and these sets would be dependent on each other. In case of two sets you can solve these equations l+r=x (mod m) and l+1=m-r (mod m) and solution is -1.
Another problem would be that the person you're doing the trick on may only want to shuffle one deck.
Tadashi mentioning the Chinese Remainder Theorem was the answer to a question I've had for about 20 years. A friend introduced me to the 3/5/7 version in a 15th century Hebrew book, and we worked out why it worked, and the significance of multiplying the remainders by 70, 21, and 15, respectively.
I wrote a small program (in QBasic) to figure out the multipliers for other sets of numbers. However, I had no idea what the source of this "trick" was, its purpose, uses, or popularity.
Now I know it's (literally) the textbook case of the Chinese Remainder Theorem. Perhaps a video on this specific topic would be of interest to others, as well.
Every number congruent to -1 (mod 4) is also congruent to -1 (mod 2). So, in fact we can just ignore modulo 2 for CRT. And we see that 11 is congruent to -1(Mod 3x4=12)
I love this video! I wonder is there anything similar for 3 piles of cards?
Excellent voice
Or you can just use Lowest Common Multiple(for 1,2,3 and 4 in this case) - 1
Yeah, I have no idea what "mod" is, but I gathered from the video that 11 + 1 is definitely 12, and it's divisible by 4, 3, 2 and 1.
I found that the formula (m!/(m/2)!)-1 where m is the number of cards will give you the number of shuffles needed for this to be true. You need to round the m/2 term down to the nearest integer.
I feel this is the most mathematical video he's done.
nice card tricks!)
can’t wait for the video on h
i love this guy
I miss Tadashi
I just saw this guy's Wikipedia page and can confirm he is an all-round genius.
Paul Daniels used to do a great version of this. And just by coincidence, his name has 11 letters in it, so he used that as the key.
That's actually a very cool trick. Hard to believe that this actually works when you see it.
Starting from 3 and go to the number of cards you have: for 4 cards(3*4-1) for 5 cards(3*4*5-1) and so on, this will give you how many times you need to shuffle the cards. This is only if you want to use the same about of shuffles each time, otherwise you can just shuffle it the number of times of cards you have left.
When you get to 6 you'll get a number that works but isn't the minimum, since you already have a 3 and a 2 from the prime factors of 6, you can miss it out. So the number you have for 5 will also work for 6 for this reason.
I don't think thats how it works since 4 has factor 2
Yes, that's why it worked, as you started at 3 and missed out the first 2 which you'd normally have
so:
for 2: 2
for 3: 2 x 3
for 4: 2 x 3 x 2 (don't need the second 2 in the 4 as we already have 2 2s now)
for 5: 2 x 3 x 2 x 5
for 6: 2 x 3 x 2 x 5 again (since we already have a 2 and 3 in the 6, we don't need to add any more in, there are no new original primes)
for 7: 2 x 3 x 2 x 5 x 7 (new prime factors)
etc
You can always have a equation arrangements to get the solution for normal pattern analysis. That's called number magic tricks. Time sequester is different arrangements pattern.
“Luck doesn’t come...except to the deserving.”
If you have m cards, you can always choose a phrase which has m!-1 letters in it. However, this would grow really fast (with 10 cards, you will need a phrase with 3,628,999 letters lol); and this does not seem to always give the smallest required number. Case in point: 4 cards works with m=11, smaller than m=4!-1=23.
I just had this fascinating thought!
How does our brain cope with randomness? I thought of this when Tadashi pointed to the cards in the beginning randomly while spelling out Numberphile. How does my brain know what random or the non existence of a pattern is? I don't know how to phrase this question.
Of course Tadashi is the King card.
Well, what are your options? XD
Realistically you can only assign people to King, Queen, Jack, and depending on the deck, the two jokers.
Still... King of hearts huh... Interesting... XD
if Tadashi sensei is talking about the chinese remainder theory through a card trick, then the next video might be a lesson about RSA cryptography using a bunny in a hat trick
This reminds me of the Nim video Matt Parker did. This seems to work pretty much like that.
*Checks dictionary to see if there is a word with -1 letters*
Indeed the word would have to be long to perform this trick with 10 cards; it would have to be 2,519 letters long! That's longer than standard words in any language--you would need to resort to so-called "verbal formulae" to achieve such staggering lengths. Or, you could just use a few short paragraphs, but that seems much less impressive.
For anybody concerned with the details of how I got this number, I'll give some hints for those interested:
1) Solve directly for n+1 instead of n, so that the congruences are all equal to 0 instead of -1, then get n by subtracting 1 at the end.
2) Think of this as a divisibility problem.
3) Use prime decomposition.
Counting cards is hard. Keeping track of the cards at the top was about the limit of my ability. I really take my hat off for people who can do a running count in blackjack.
Also, obviously Tadashi is awesome.
You have to practice, practice, practice and, BTW, you also have to practice.
Dang. M Tadashi is right again
I love tadashi
I wish he explained the whole -1 mod M thing more. Felt rushed.
What would the general case for a system of equations to use the chinese remainder theorem look like?
What a voice.
"So if I had two piles of ten, there'd be some other word I would be having to find". That would be twice the video description plus 15 times "Numberphile" plus 10 times "Brady"
Id quite like to see a video on how you actually work out the shuffle number, and what being equal to -1 mod m means
His playing cards are from the Norwegian Center of Mathematics (Matematikksenteret).
I'd love to see a plot with m on the x-axis and the lowest value of r+l such that mod(r+l,n)=mod(-1,n) and n is a list containing every natural number less than and equal to m, on the y-axis.
Would it ever be worth doing a video with, say, both James and Matt? Or will we always be seeing one person at a time?
I'd love to see that
There's a Maths Gear video with them in, but it's serious Grime Time TV!
And collaborate with Scam School.
Seems to me that the easiest way to get that number is to get the least common multiple of those numbers and subtract one.
So, for 5 cards, it would be LCM(2,3,4,5) - 1= (2^2*3*5) - 1 = 59
6 cards: LCM(2,3,4,5,6) - 1 = (2^2*3*5) - 1 = 59
7 cards: LCM(2,3,4,5,6,7) - 1 = (2^2*3*5*7) - 1 = 419.
8 cards: LCM(2,3,4,5,6,7,8) - 1 = (2^3*3*5*7) - 1 = 839
9 cards: LCM(2,3,4,5,6,7,8,9) - 1 = (2^3*3^2*5*7) - 1 = 2519
10 cards: LCM(2,3,4,5,6,7,8,9,10) - 1 = (2^3*3^2*5*7) - 1 = 2519
Blue pen, red pen, green pen. Yay!
Voice of gold
So the number of shuffles necessary for the 10 first cards are.
1 Card/Pile = 0 ; 2 Cards/Pile = 1 ; 3 Cards/Pile = 5 ; 4 Cards/Pile = 11 ; 5 Cards/Pile = 59 ; 6 Cards/Pile = 59 ; 7 Cards/Pile = 419 ; 8 Cards/Pile = 839 ; 9 Cards/Pile = 2519 ; 10 Cards/Pile = 2519
*My favorite ninja in disguise, Tadashi.* 😊
Why are the cards moved 1 step ahead in clockwise direction for each shuffle shouldn't it be moving in anticlockwise direction as in each shuffle the top card goes to bottom ? And which is the L + 1 position ? can someone please clarify it
Luck only comes to the deserving. 😊
Alternatively:
_The rain it raineth on the just_
_And also on the unjust fella;_
_But chiefly on the just, because_
_The unjust hath the just’s umbrella._
There's Mathematics for less-deserving.
Beautifull
The fact that I guessed each shuffle on the first round before you picked it proves humans are terrible at randomness.
Oh I love magic!
Can someone tell me for 3 cards how many letters does the word has to have?
more takashi!
wouldn't the number of letters required in the word that we will use for "M" cards be equal to LowestCommonMultiple( M , M -1 , M -2 , ... , 2 ) -1 ?