Okay so I'm going to talk about
splitting necklaces and about
non-constructive proofs - and this is a
story about thieves that steal, together,
a necklace. But they are not just any
thieves, they are mathematically oriented thieves.
so imagine that we have two thieves and
they steal together a necklace. And this
necklace has beads of two types, eh
let's say diamonds and rubies. They
want to split the necklace evenly among
them and they want that each of them will
get the same number of diamonds and also
the same number of rubies. So they open
the necklace at the clasp and then
they have an interval of beads. And the
necklace can be complicated but, but this
is an example. - (Brady: No pattern or intervals or-?)
That's right. We don't assume anything, let's assume for
simplicity 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
minimise the number of cuts that they do
in the necklace. What they want to
do is to cut the necklace in several
places, this will split it into
intervals of beads, and then they will
take the intervals and will distribute it
among them; and they want in this example
that each of them will get four diamonds
and three of the rubies. All together
seven beads. - (Brady: But it's important minimal cuts?)
It's not necessarily the minimum
possible number of cuts completely
but they want to have a small number of
cuts. Each of them should get seven beads
so we can try to cut the necklace in the
middle. Then we will have two intervals
of beads, the left part and the right
part, but you see that in the left part
we have too few rubies, only one, and each
of them should gain three. So this
doesn't work. What we can do is we can
take this interval of seven beads and
shift it one to the right, and then - 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 are making
progress; and then we can try to shift it
gradually and hope at some point it will
be okay. If we shift it up to this place
here, so three...one, two, three, four;
so the two cuts will be here and here,
then in the middle interval we have
exactly four diamonds and three rubies, and
therefore also we have four diamonds and
three rubies in what's left.
And this means that two cuts are enough. Now
I claim that actually what we proved
here is that two cuts are always enough. And
why is this the case? Because we started
by splitting the necklace; so imagine now
that it's a even maybe longer and
very complicated necklace with diamonds
and rubies, we split it into two halves
by cutting the middle. Now if on the left
cut there are too few rubies, then on the
right cut there will be too many, right?
Because altogether we have the right
amount. And then we use what is called
the discrete version of the Intermediate
Value Theorem. So that's a theorem in mathematics
but these are just words. What this means;
so we observe here that whenever we
shift the interval here by one to the
right, then the number of rubies in it
can change only by one. Because we lose
one bead and we gain one bead, so we can
gain at most one ruby. And therefore we
started maybe with too few rubies, at the
end we have too many, and every time we
change the number of them just by one. So
that means that somewhere in the middle
we must hit exactly the right number, so
this means that two cuts always suffice. - (Brady: So the)
(ruby number's only ever changing by one)
(so we have a firm control of that?) - That's
right. - (Brady: But the diamonds are taking care)
(of themselves as well?) - Yes so, you're right the
diamonds will be okay as
well, because the total number of beads
each one gets is a correct number. So
once we have the right number of rubies
then the number of diamonds will be, will
be correct as well. We saw also in this
example, but it's kind of obvious, that if all
the diamonds appear contiguously on the
necklace somewhere, and all the rubies
also appear contiguously, it is clear
that the number of cuts we need is at
least two because we have to have some
cut in the middle of the interval of
diamonds, and we have to have some cut in
the middle of the interval of rubies. So
it means that sometimes we need two
cuts, and what we just proved is that two
cuts are always sufficient. - (Brady: Sometimes we)
(can get away with one cut but that's only)
(when it's symmetric or-?) - Yeah so it doesn't
have to be symmetric, what it means that
exactly in the left side we have the
correct number of rubies so it's true
sometimes one cut is enough but what we
proved about two cuts is that two cuts are
always enough. So now we can try to make it a
little bit more complicated. Let's say that
still the number of types of beads
is still two, only diamonds and rubies, but now
we have instead of two thieves we have
four thieves. You know sometimes it's better to
have a bigger group so, so we have four, a
small game 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 of rubies is divisible
by four. How many cuts do they need now?
We have this necklace which is an
interval of beads. By what we saw before
we can have two cuts, maybe here and
here, so that in this interval and in
those two together we have the correct
number of rubies and the correct number
of diamonds - we split it into two fair
shares. Now we can take this interval
that contains the half that went to two
of the thieves,
we started with four of them they split
themselves into two groups of two thieves.
And then, once these two thieves got the
fair share that they deserved, then they
use another two cuts in their part in
order to split it evenly among the two
of them. And these two intervals of the
other two, we can shift them to
somewhere, let's say here, in this
interval we put it here and we
forget that they are two intervals so we
view it again as an interval of beads, and
again this other group of two additional
thieves can cut this part in two places
and split it evenly among them. So if we
go back to the original necklace this
corresponds to six cuts. The two original
ones, these two and these two. Okay? So it
means with four thieves and two types; six
cuts are always enough and it is good to
observe that sometimes six cuts are
needed. So again the simple case where
the diamonds appear contiguously, and
afterwards the rubies also appear
contiguously, if now we have four thieves
then of course we need at least three
cuts inside the interval of the diamonds,
because we have to cut it into four
parts. And we need at least three cuts
inside the interval of rubies so
altogether in this example we need six
cuts. What we showed is that six cuts are
always enough also. - (Brady: Four was very)
(convenient because you are able to use)
(what we learned from two, what about; what)
(if there were three thieves?) - Right, yes. So
it's not much more complicated, let's
leave it as an exercise to way to the
viewers, but it's not much more
complicated to see is it for two types
of beads with three then four cuts will
always be enough; for a similar reason to
what we said before. I mean with an extra
simple twist and, and sometimes we
need four. So it will be possible. It's
getting significantly more complicated
when the number of types of beads
increases. So maybe we can have diamonds
and sapphires and rubies. And let's just
say the, the general theorem. Let's
say a group of K thieves. We denote by T
the number of types of beads, and again
they stole together this necklace, it
contains beads of T different types, the
number of
beads of each type is divisible by K,
they want to split it amongst themselves,
and they want to do it with a small
number of cuts. If we have this example
in which each type appears contiguously,
so maybe all the diamonds appear here and
then all the rubies appear here, and then
all the sapphires- - (Brady: Emeralds if they're green!)
Emeralds, yeh, emeralds are better.
So they appear here and so on. Then it's clear
that we need at least K minus 1 cuts
inside the interval of each type. So for
10 thieves we would need 9 cuts inside
each interval. And altogether 9 times T
cuts. And in general we need, in this
example, we need K minus 1 times T cuts.
So it means sometimes K minus 1 times T
cuts are necessary. And the theorem says
that K minus 1 times T cuts always
suffice. There is always a way to cut the
necklace in K minus 1 times T places and
then divide the resulting intervals into
K collections, and each collection will
contain exactly the same number of beads
of each type. So this is more complicated,
and I'm not going to describe the proof,
which uses some tools from continuous
mathematics, specifically from topology,
but let me just say that the first
step is a simple step if we know the
validity of this assertion, of this
theorem for K1 thieves and T types; and we
know it also for K2 thieves and T types then
it implies that it is true for K1 times
K2 thieves and T types. And this is actually
not difficult, it's similar to what we
saw before when we dealt with 4 thieves. So for
example, if it is true for 3 thieves, and it's
true also for 5 thieves, then it will be true
for 15. If we know the statement for 3 thieves
and for 5 and we want to get
it for 15 then the way to proceed is as follows:
the 15 thieves split themselves into
three groups, each of five thieves. And then
we view each group as a super thief and
then we use the result for 3 and we
split it fairly among these three super
thieves. And then each group that corresponds
to a super thief, 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 splitting. This is simple,
but the more complicated thing is that
the second step is to kind of change the
problem into a continuous one, and I'm
not describing how exactly, and then to
use some theorem in topology to get the
result for the continuous problems that
implies the discrete version that we
need. And the nice thing is that actually
the topological result works only when
the number of thieves is a prime number;
is a number that is not divisible by any
other number besides one and itself.
(Brady: Something about the nature of that proof)
(means it only works for prime numbers?)
That's right. So it's kind of lucky that we
have this way to get the result for
three times five from the result for
three and the result for five, because
the result for three and four five we
can get it using topology, which
seems to be necessary when the number of
types of beads is at least three. Right,
we saw that with two types of beads
everything is simple, but with three or
more types of beads then we need this
topology. - (Brady: so any number of thieves can be)
(handled because any number can be built)
(from prime numbers?) - That's right. Any
number is can be expressed, even
uniquely, as a product of primes and then
we can use this result. A feature of this proof that I
want to mention, that is intriguing,
is the fact that it is non constructive.
The topological proof does not provide
any efficient procedure or algorithm to
solve the computational problem. So if,
for example, the number of thieves is
five;
and the number of types of beads is five,
so the number of cuts needed will be 4
times 5, which is 20. And the total number
of beads, let's say 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 5 thieves. And we can, 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, the
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 suspect 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 of computational problems
and- which we don't know to solve
efficiently any of them, and if we will
be able to solve efficiently this
specific problem then we will be able to
solve efficiently all of 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 thieves' point of view that
maybe they thought that the challenging
part is to get the necklace, but actually
maybe the even more challenging
thing is to split it afterwards evenly
among them. - (Brady: All the computers in the world?)
You know the total number of elementary
particles in the universe is something
like 10 to the 80, and it's really easy
to formulate a a very simple
combinatorial problem where the number
of possibilities will be more than 10 to
the 80, just because often things grow
exponentially in terms of their
parameters.
[Extra:] Much much longer, longer ago, where we
think about having maybe an interval
representing a cake... - Watch carefully. Only
time in my life I'm going to wash my
hands in diamonds.