Chinese Remainder Theorem and Cards - Numberphile
Ғылым және технология
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
Пікірлер: 400
Numberphile Playing Cards: bit.ly/NumberphileCards More card videos: bit.ly/Cards_Shuffling
@X_Baron
5 жыл бұрын
What's the back of the cards like? The ones on the video have non-symmetrical backs, meaning they are cheaters' cards.
@jamescolovos
5 жыл бұрын
In this video, it looks something like the Penrose tiling
@htmlguy88
5 жыл бұрын
the number you want for 10 cards is 2519 lol
Tadashi has the most soothing voice.
@rmcunningham3874
5 жыл бұрын
I could listen to his voice and accent forever.
@bandaral-qordi5645
5 жыл бұрын
Very close to George Takei
@Triantalex
8 ай бұрын
false.
@mashroom2927
2 ай бұрын
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.
@MyAccountOnYouTube
5 жыл бұрын
Happy Friday (also eleven letters)
@norcalfrost1140
5 жыл бұрын
"Eleventy One" has 11 letters
@alexwang982
5 жыл бұрын
Four has four letters
@datboi7678
5 жыл бұрын
@@alexwang982 does pi have pi letters?
@alexwang982
5 жыл бұрын
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.
@knightriderultimate
5 жыл бұрын
Conor O'Neill you could use a sentence/phrase instead of a word for 5 and 6 though.
@garmo1968
5 жыл бұрын
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
@diribigal
5 жыл бұрын
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"
@karlmuster263
5 жыл бұрын
For 7 cards, "America" + up to the end of the first paragraph of the Declaration of Independence.
@abcdefg54321x
5 жыл бұрын
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.
@MagicDoorHinge
5 жыл бұрын
Second favorite for me. Gotta love Cliff Stoll!
@dAGriddo
5 жыл бұрын
And don't forget about James Grime, Matt Parker, ... ;)
@pierregirardeau806
5 жыл бұрын
And Hannah Fry !
@NICHOLSON7777
5 жыл бұрын
He is to Numberphile what Copeland is to 60 symbols for me. Can't help but like the guy.
@Bigpimping-by6yj
5 жыл бұрын
Tom Michalak cliff is a legend
"You gotta do magic at some point" -- Dr. Tadashi
Always love a video with 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.
@ellaenchanted2399
5 жыл бұрын
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.
@twwc960
5 жыл бұрын
According to his Wikipedia page, he speaks at least nine languages and he studied philology before turning to mathematics.
@LeoStaley
5 жыл бұрын
This is why I love him. He just jumped into my top 3 favorite scholars.
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!
@numberphile
5 жыл бұрын
Cheers
Dr. Tadashi's videos never cease to amaze!
Tadashi is amazing. Keep doing videos with him!!!!
I could listen to him talk all day!
i love tadashi videos i hope i can meet him in my life and tell him he's awesome
Tadashi had the best presentation in the whole ICM 2018!
Look Who Is Back My fav Tadashi is back😍
Tadashi once again with the goods!!
I could listen to Prof. Tokieda forever.
A Tadashi video? feelsgoodman
Tadashi is always correct
@hazenoki628
5 жыл бұрын
I got that! (at least with an extra i)
@shirou9790
5 жыл бұрын
Well his given name is indeed 正 in Japanese, so the same kanji as in 正しい (tadashii)
I'm a simple man. I see Tadashi in the thumbnail, I click.
@faastex
5 жыл бұрын
I'm a simpler man. I see a Numberphile video, I click.
@vka337
5 жыл бұрын
Fastex I'm the simplest man. I see any video I click.
@hazenoki628
5 жыл бұрын
I was going to comment the same thing, but you beat me to it. He's great!
@Alpha-1-Omega
5 жыл бұрын
I'm even more simple. I start internet and I click.
@Pacvalham
5 жыл бұрын
I'm the most simple: I just click; that's it.
Awesome as always
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
You're a wizard, Tadashi!
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)
You'd need a phrase with 2519 letters (that's the shortest) to get the trick to work with 10 cards.
@NestorAbad
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.
@charlottedarroch
5 жыл бұрын
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.
@shirou9790
5 жыл бұрын
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
@robin888official
5 жыл бұрын
Might work in German.
@sp10sn
2 жыл бұрын
"It was the best of times, it was the worst of times..."
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 ^.^
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.
@fatchoumagharbi9939
3 ай бұрын
what do you mean
3:10 cyclic order is preserved when doing straight cuts
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 loved this and I loved that deck ;)
I love this video! I wonder is there anything similar for 3 piles of cards?
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.
@NestorAbad
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.
@andymcl92
5 жыл бұрын
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 :)
@TheArmyofWin
5 жыл бұрын
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!
@bilonay
5 жыл бұрын
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!!
@CacchiusMan
5 жыл бұрын
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
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
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!
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.
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
Wow yaar, awesome 👏 you guys are amazing 🤩
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!
Amazing trick
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...
@bestserg
5 жыл бұрын
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.
@raydarable
5 жыл бұрын
Another problem would be that the person you're doing the trick on may only want to shuffle one deck.
"Luck comes to the deserving" -Tadashi
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
I feel this is the most mathematical video he's done.
Tadashi is the real spirit of numberphile
What a wonderful voice
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
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.
Tadashi is my spirit animal.
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.
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
@TechnoHackerVid
5 жыл бұрын
Use the full chemical name of the Titin protein. 180K letters
@CGoody564
5 жыл бұрын
Is this correct? I always thought pneumonoultramicroscopicsilicovolcanoconiosis was the full word. Would logisticalization be the process in which it forms?
@TechnoHackerVid
5 жыл бұрын
You can always twist long words. Not many bother to read :P
@nayutaito9421
5 жыл бұрын
I just added random suffixes to the word, so it's not a real word (Of course you can guess the meaning easily).
@alexwang982
5 жыл бұрын
Logisticalization, to make it a noun
What would the general case for a system of equations to use the chinese remainder theorem look like?
How many Math tricks and puzzles were NOT published by Martin Gardner. Probably a shorter list.
@andymcl92
5 жыл бұрын
Try watching Scam School and you'll find that list will gradually shrink even further!
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)
Or you can just use Lowest Common Multiple(for 1,2,3 and 4 in this case) - 1
@samus88
5 жыл бұрын
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.
can’t wait for the video on h
Reminds me of arithmetic sequences. Very interesting
I just saw this guy's Wikipedia page and can confirm he is an all-round genius.
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.
Excellent voice
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.
nice card tricks!)
Can someone tell me for 3 cards how many letters does the word has to have?
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
That's actually a very cool trick. Hard to believe that this actually works when you see it.
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.
This reminds me of the Nim video Matt Parker did. This seems to work pretty much like that.
I miss Tadashi
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?
@xahiru
5 жыл бұрын
I'd love to see that
@andymcl92
5 жыл бұрын
There's a Maths Gear video with them in, but it's serious Grime Time TV!
@KatanaBart
5 жыл бұрын
And collaborate with Scam School.
i love this guy
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.
@DanDart
5 жыл бұрын
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.
@MrCyanGaming
5 жыл бұрын
I don't think thats how it works since 4 has factor 2
@DanDart
5 жыл бұрын
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
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
I wish he explained the whole -1 mod M thing more. Felt rushed.
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 ?
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.
Isn't the Chinese Remainder Theorem overkill to find the required "magic" number? The CRT works great if the remainder differs for each modulus, but since for this trick you need it to be equivalent to -1 mod m, for m = 2 .. N, wouldn't one less than the Least Common Multiply of the numbers 2 .. n be the right number? So, for 5 (and 6) cards, 59 works, for 7 cards 419, for 8 cards 839, for 9 and 10 cards, 2519, etc.
@MathNerd1729
5 жыл бұрын
I know right? I was thinking that same thing!
Of course Tadashi is the King card.
@KuraIthys
5 жыл бұрын
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
So you need a *LCM(2,3,4,...,N)-1* letters long word for N cards, right? Wouldn't this just be *-1mod M* for all of them?
"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"
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.
10:35 Tadashi... why do you adjust your glasses with your middle finger...
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.
Oh I love magic!
What a voice.
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.
*My favorite ninja in disguise, Tadashi.* 😊
Blue pen, red pen, green pen. Yay!
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
Dang. M Tadashi is right again
Isn't this sort of modular convalescence essentially how RSA encryption works?
Beautifull
I love tadashi
“Luck doesn’t come...except to the deserving.”
Luck only comes to the deserving. 😊
@guest_informant
5 жыл бұрын
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._
@diwakarism
5 жыл бұрын
There's Mathematics for less-deserving.
My first time watching I saw him switch cards to the other pile
His playing cards are from the Norwegian Center of Mathematics (Matematikksenteret).
What about the Chinese remainder theorem?
Hi !.. I'm really new to Number Theory. This video was very interesting. Now when I think cards I think of probabilities. So there's this question in my mind now. How, if at all, is Number Theory is linked to Probability Theory ?.. It would be very helpful if someone could guide me. Thank You.
@francoisbruel9163
Жыл бұрын
No probability at all in this trick
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