Placeholder Image

字幕表 動画を再生する

  • Okay, so I'm going to talk about face pleating, necklaces and about known constructive proofs.

  • And this is a story about thieves.

  • They still together a necklace, but they are not just any thief.

  • They are mathematically oriented.

  • So imagine that we have two thieves and they still together A necklace, and this necklace has a beads off two types say, Let's say, diamonds and Rubies.

  • They want toe split the necklace evenly among them, and he wants it.

  • Each off them will get the same number off diamonds and also the same number off Rubies.

  • So the old paint the necklace.

  • It's a class, and then they have the Interfax speeds, and the necklace could be complicated.

  • But But this is no hat.

  • No intervals are.

  • That's right.

  • We don't assume anything.

  • Let's assume for simplistically that the number of diamonds and also the number of Rubies, is even so that it is possible to split it evenly among the two thieves.

  • Now they want to minimize the number off cuts that they do in the Nicolas.

  • What they want to do is to cut the necklace in several places.

  • This will split it in tow, intervals off speeds and then they will take the intervals and will distribute it among them.

  • And they want in these examples that each off them we get four diamonds and in three off the roof or together seven.

  • But it's important.

  • Minimal cuts, not necessarily the minimum possible number off completely, but they want to have a small number.

  • Each of them should get seven beads so we can try toe cut the necklace in the middle.

  • Then we will have two intervals off with the left part and they write part.

  • But you see this in the lift part.

  • We have too few rupees, only one and each of them should get three.

  • So this doesn't work.

  • What we can do is we can take this Cinderella seven beats and shift it one to the right in vain.

  • So this corresponds to having the cuts here and here.

  • And then in this interval we have two Rubies, which is still too few.

  • But we're making progress and then we can try to shift it great lately and hopes at some point it will be okay if we shifted upto this place here.

  • So 31234 So the two cuts will be here and here.

  • Then in the middle interval, we have exactly four diamonds in three Rubies.

  • Therefore, also we have four diamonds and three Ruiz in what's left.

  • And this means that two cuts are enough.

  • Now he claims that actually what we proved here, they pay cuts are always enough.

  • And wise is the case because we started by splitting the necklace.

  • So imagine now that you say, and even, maybe longer and very complicated necklace with diamonds and Rubies we split it in tow two halfs by cutting the middle.

  • Now, if on the left cut there are too few rupees then on the right card, they will be too many, right?

  • Because all together we have the right amount.

  • And then we use what is called the discreet version off the intermediate value serum.

  • So that's a few.

  • Remain with my kicks with these are just words.

  • What this means so we observe here is that whenever we shift, they inter filed here by want with right Then the number off Rubies in it can change only by one because we lose one bead and we gain one beat so we can gain at most one ruby and therefore we started maybe was to fuel its the end.

  • We have too many.

  • And every time we change the number off them, just one.

  • It means it's somewhere in the meeting.

  • We must heat exactly the right number, for this means IQ to cuts always so five.

  • So the really numbers only ever changing by one.

  • So we have a firm control of that.

  • But the diamonds are taking care of themselves as well.

  • Yes, Okay, you're right.

  • Say the diamond will be OK as well, because the total number off beads each one gets is a correct number.

  • So once we have the right number of Rubies, then the number of time ones will be will be correct is what we saw in this example.

  • That's kind of obvious if it if all the diamonds appear continuously on the necklace somewhere and all the Rubies also appear continuously, it is clear that the number of cuts we need is it least too, because we have to have some cut in the middle off interval off diamonds and we have to have some cart in the middle of faint of ALF Rubies.

  • So it means that sometimes we need to cut.

  • And what we just proved is that two cuts are always sufficient.

  • Sometimes we can get away with one cut.

  • That's only when it's symmetric or yeah, so you don't have to be symmetric.

  • What it means that exactly in the left side we have the correct number, Ruby.

  • So it's true.

  • Sometimes one cart is enough, but what we proved about to cut is a two cuts are always so.

  • Now we can try to make it a little bit more complicated.

  • Let's say that's still the number off types off me.

  • This Saito, only diamonds and Rubies.

  • But now we have instead off.

  • Two thieves were fourth.

  • You know, sometimes it's better to have a bigger group.

  • So So we have four small gang of thieves and they still are mathematically oriented.

  • Still, they want to split it evenly and still they are lucky.

  • And the number of diamonds and also the number off Rubies is divisible by four.

  • How many cuts do they need now?

  • We have this necklace which is an interval off by what we sold before we can have two carts, maybe here and here, so they tend this interval and those two together, we have the correct number off Rubies in the correct number off that we split it into two fair ships.

  • Now we can take this interval that contains 1/2 that went toe to toe with thieves.

  • We started with four off them.

  • They split themselves into two groups off toothy.

  • And then once these two thief's got the fair shares that they deserve, then the use another two cuts in their part in order to split it evenly among the poor fame in thes two intervals off other two, we can shift them to somewhere.

  • Let's say, here in this interval we put the pier and which forget that they are two intervals for review it again as an interval feeds and again, this other group off.

  • Two additional thieves can cut this part in two places in split it evenly among them.

  • So if we go baked with originally place, this corresponds to six cuts.

  • The two original ones this toe end this okay, so it means with four thief's in two types.

  • Six cuts are always enough, and it is good to observe.

  • It's sometimes six cuts are needed.

  • So again the simply case, Where's the diamonds?

  • Appear continuously and afterwards they Ruby's also appear continuously.

  • If now we have four thieves, then off course.

  • We need at least three carts inside the interval off the diamonds because we have to cut it into four parts and we need at least three cuts inside.

  • Interval off Ruby's soul together.

  • In this example, we need six cuts.

  • What we showed is it.

  • Six cuts are always enough was very convenient because you are able to use what we learned from two.

  • What if?

  • What if there were three things right?

  • Hey, so it's not much more complicated.

  • Let's leave it as an exercise to tow the viewers, but it's not much more complicated to seize it For two types, off beads with three, then four cuts will always be enough for a similar reason toward, we said before, I mean with an extra simple tweet.

  • Stay in the end.

  • Sometimes we need for so so it will be possible.

  • It's getting significantly more complicated when the number off types off beads increases.

  • So maybe we can have diamonds and sapphires and Rubies.

  • And let's just say the general fury.

  • It's a group off K thieves we denote by T is a number off types off beat in the game they told together as a necklace.

  • It contains beads off T different types.

  • The number off beads off each type is divisible by K.

  • They want to split it among themselves, and they want to do it with a small number.

  • If we have this example in which each type appears continuously.

  • So maybe all say diamonds appear here in vain or they Rubies here, here and then they say Emeralds, grain.

  • Murat the emerald Better for the Peary here.

  • And then it's clear that we need it.

  • Least K minus one cuts inside the interval off each time.

  • So for 10 feasts we would need nine cuts inside.

  • Each interview endorsed weather nine times T cuts.

  • And in general, we need in this example we need K minus one times t cuts.

  • So it means sometimes Kate, my new fun times T carts are necessary in the Fury says they came.

  • I knew Swan Times.

  • T cuts always suffice.

  • There is always a way to cut the necklace.

  • It came in foreign Times T places and then divide the resulting intervals in Tok collections, and each collection will contain exactly the same number off beads off each time.

  • So this is more complicated, and I'm not going to describe the proof, which uses some tools from continuous mathematics, specifically from apology.

  • But let me just say it.

  • The first ape is a simple stay.

  • If we no validity off this assertion off the theory for K one fiefs and tea types and we know it also for K two thief's and he types, then it implies that it is true for K one times K two Thief NT types, and this is actually not difficult.

  • It's similar to what we saw before when we dealt with fourth.

  • So, for example, if it is true for a three thieves and it's true also for five thieves, then it will be true for 15.

  • If we know the statement for three thieves and for five and we want to get it for 15 then the way to proceed is that follows.

  • The 15 thief split themselves into three groups, each of five and then review.

  • Each group is a super thief, and then we use the result for three and we split it fairly among these three Super fit and then each groups, of course, want way to supersede, which consists of five normal thieves.

  • They use the result for five inside the group, and then if we just work out the numbers, then it will give us the correct statement is simple.

  • But say more complicated thing is that the second step is to kind off change the problem into a continuous one.

  • And I'm not exploiting how exactly.

  • I intend to use some theorem in topology toe.

  • Get the result for the continuous problems that implies the discreet version that we need.

  • And the nice thing is that actually stop.

  • A logical result works only when the number of thieves is a prime number is the numbers.

  • It is not divisible by any other number besides one in it's safe.

  • Something about the nature of that proof means it only works for prime numbers.

  • This right, so it's kindof lucky that we have the say way toe gets a result for three times five from the result for three and the result for five because a result for three and 45 we can get you use exist apology, which seems to be necessary when the number of types off beads is that least three right?

  • We saw that with two types of means.

  • Everything is simple, but with three or more types off beads and we need this topology so any number of thieves can be handled because any number can be built from prime numbers.

  • The trade any number is they can be expressed their even uniquely is a product off primes, and then we can use feature off these proofs that I've gone toe.

  • To mention that is intriguing is effect that it is known constructive that biological proof does not provide any efficient procedure or Alderete him to solve the computational problem.

  • So if, for example, the number of thieves is five in the number of types off satisfied, so the number of cuts needed will be four times five, which is 20 and the total number of beans.

  • Let's Hayes is 200.

  • Then we can always check all possibilities.

  • We know for sure that we can cut it in 20 places and divide the resulting intervals evenly among the fi thief.

  • And we came, at least in principle, check all possibilities.

  • But even if we use all the computers in the world for years and years, we will not be able to check all possibilities.

  • Numbers are just too big, and some of the proof does not provide an efficient way to solve this problem.

  • And moreover, it is likely to speak that there is no such efficient procedure because it is known that this problem is what is called complete for some specific complexity class.

  • And this means that there is a large number off computational problems in which we don't know to solve efficiently, any off them.

  • And if we will be able to solve efficiently this specific problem, then we will be able to sort efficiently all off those problems.

  • And because we do not know to solve any of them, then maybe it's likely to believe that this is impossible.

  • And that means from the thief's point off you that maybe they fought.

  • That's a challenging parties to get necklace.

  • But actually, maybe they're even more challenging.

  • Thing is, toe split it afterwards evenly.

  • All the computers in the world.

  • You know, the total number of elementary particles in the universe is something like a tent with eight, and it's really easy to formulate a very simple combinatorial problem where the number of possibilities will be more than 10 toes A.

  • Just because often things grow exponentially in terms off the parameters much, much longer, longer ago where we think about having a baby and interval representing a cake.

  • Watch carefully.

  • Only time in my life I'm going to wash my hands in diamonds.

Okay, so I'm going to talk about face pleating, necklaces and about known constructive proofs.

字幕と単語

動画の操作 ここで「動画」の調整と「字幕」の表示を設定することができます

B1 中級

ネックレスの分割(宝石泥棒のレッスン) - Numberphile (Necklace Splitting (a lesson for jewel thieves) - Numberphile)

  • 0 0
    林宜悉 に公開 2021 年 01 月 14 日
動画の中の単語