Ok I want to talk about a very old
problem; it's gone by different names, one
of them is the theorem on friends and
strangers. So what we're going to do is -
Brady we're going to update this for the
kids, make it kind of hip - we're not
going to talk about adults at a dinner
party we're going to talk about people
on Facebook. - (Brady: Oh yeah - we're down.)
You're down with that?
You down with 1 billion people on
Facebook? We've got 6 people on Facebook,
ok, there's more than 6 people on
Facebook - you know that. Now, there's
certain relationships you can have. You
can either be connected, which we're
going to say is green. Okay, so this
dude's connected to this dude, this
person's connected to this person, this
person's connected this person; or you're
not. So you're like, this guy doesn't know
this person, this person's blocked this
person, this person here doesn't know
they exist, this person- they don't even
speak the same language. Ok, so this is
this is the situation. Now if we think
about if we're now going to try and
count how many different arrangements we
can have of 6 anonymous people on Facebook,
so there's actually 15 different
connections between people. But each
connection is either, you're friends or
you're not friends. To count that we
actually go 2 to the power 15, ok? So
that's what that- that's how to count how
many we've got. So that number is 32768.
So you've got 15 lines. Each one can
either be a friend or not a friend, sorry
I'm not going to be friends with you don't try and- stop
requesting to be friends I don't wanna be
friends with you ok? No. This is you, this
is your mum and it's like, no mum go away.
This is your dad it's like, uh uh, you know?
We're connected in the house not on
Facebook. - (You drew that quite randomly,)
(there were 30- there are nearly 33)
(thousand different ways you could have)
(done that.) - There's exactly 32768
different ways you can do that Brady,
don't round it up.
So obviously you could have, like, I don't
know it's like you could have like One
Direction, right, and their manager; they'd
all be green, they're all connected. And
then if you've got like the like members
of your family, like we said
before, nobody's connected. There's a lot of
complexity on Facebook if you think
about all those different connections.
But just looking at a very small subset
of just six people look how- look how
many connections we've got. So the
question is what can we say about every
single possible permutation? Every single
possible combination - is there anything that we
can glean? Because we want to try and
find order out of chaos as
mathematicians, we want to go what can we
learn about any possible one. If you gave
me one of these at random what could I
say? Without even looking at it I could go I
know exactly something about it. So what
we can say about any random arrangement
of friendships, or not friendships, we can
say for any single one any of these
32768 there's always three people
that are friends or three people that
are not friends.
- (But it could be more?) - And it could be
more; because like in the One Direction
band manager thing there's lots of
groups of three right? But the point is
is that it's an at least. So at least
means, okay, this is the absolute minimum.
So either three people are friends or three
people are not friends; and that's the
order that we can do. So why? Is there a
reason behind that, can we prove it? We
can, okay. So this is how we're going to
prove it: first of all we're going to try
and simplify things, okay? So now let's
just look at one- this is too complicated,
let's just look at one guy, okay, one
person. So one person has his like could
be friends here; we're just looking at
the connections, I don't want to colour
them up just yet. So it's like one, two,
three, four, five. So you think, okay, so
what can we know about these friendships
that this person has with all these
people? We've got five lines and we want
to know what colour are they? Are they going to
be green or are they going to be dotted red?
They going to be friends or not
friends? So if we look at five we could
actually see, all right, we could just
start kind of counting in a funny way. So
we can kind of go, oh yeah, there's a
situation where there could be five all
friends, and then this guy's not- not
friends with nobody, okay?
(He's a popular dude.) - He's popular, yeah yeah yeah,
he's friends with everybody,
okay? He's a bit of an Obama, he's a
politician, that's when- this is this is
the politician here, he's friends with
everybody. The other one could be instead
it could be he's friends with four people
and he's not friends with one person. So
you can keep going like this and now
actually we can just fill this out here
so we get three, two, one, zero;
one, two, three, four, five. This is the
different ways we can do it, now if we
look at every single possibility there -
so here we know one of the at least
things, so here we know, look, if it's five
friends and and zero not friends well we
know that that is that's definitely
greater than three friends there. Four, well
that's greater than three friends there;
three, that's greater than three friends
there; two, well that's not greater than
three friends there but now it's greater
than three not friends. And this is
greater than three not friends, and this
is greater than three not friends - so
you know that any way you break this up
or any combination of, like, friends or
not friends there's always one person is
always friends with at least three
people or not friends with at least
three people, and that's the kind of
tricky bit. If you can get your head
around that the next bit should be cool.
So let's just draw up another random
anonymous just to kind of keep it clean.
Here's our guy here,
so let's actually say he is friends with
at least three people, or it could be the
opposite right? But we're going to go: he's
friends with this person, he's friends
with this person, and he's friends with
this person. Now what we want to do is,
we're going to try and force the worst
situation okay? So what we're trying to
do is we're trying to show that that - the
the theorem says at least three people
know each other or at least three people
don't know each other. So let's try and
let's try and push it to the extreme. So
in that sense it's like we want to try
and make sure that- we don't want three
people to know each other, to be friends
on Facebook. So that means we are going
to go, okay so if this guy, this guy, and
this guy were all friends they would all
be green, we don't want that, we want
these ones to be red. So we put a dashed red
line there, these guys aren't friends.
But there's another triangle here, so
it's green green - no no we don't want you
to be friends. 'Cos we're trying to force-
(You're trying to- you're trying to avoid a)
(threesome at all costs?) - We are trying to
avoid a threesome at all costs, that's
exactly right Brady. So here we don't
want these guys to be friends; but look
there's another triangle there, so now we
don't want these guys to be friends. But
look what's happened - by trying to avoid
this guy making- we've created,
inadvertently, we've actually created
three people that don't know each other.
We've created like a threesome of
anonymity. - (Which was the other- which was)
(our 'and or') - Which was our 'and or'. And you
can see now if we flipped it, if now this
guy wasn't friends, nor was- wasn't friends;
and we made these guys friends it
would be the opposite situation. So this
is order out of chaos. For every single
possible 32,768, every possible
combination of being friends or not
friends, it's always the case that you always
find a clique of three people that are
friends with one another or three people
can't stand each other; or don't know
each other; or are your mum and your dad.