This video has been years in the making actually.
I'm quite excited about this video, it's a problem that I've actually got a part in as well. I've been
given permission to give you an exclusive look at this new solution - it's a secret! It's not a secret,
I'm going to tell you all. So in this box we have our new solution to this old problem; and building
up to this I think I should start with what the problem is of course. Imagine four friends and
they're going to play a game and they want to decide who goes first, second, third and fourth - fine.
So to do that they decide to roll dice. They roll one each and whoever has the highest number goes
first, second highest number goes second; you get the idea. The only problem with that is two players
might roll the same number - oh no, a draw. So what are they going to do? They could roll again. Well
potentially that could go on forever. Is there a set of four dice, so each player can have one, roll
them together; there are no drawers and all equally likely to be first, second, third, and fourth.
That's the question. Well that does exist. They're called Go First dice; they were invented by
Eric Harshbarger and Robert Ford about 10 years ago. I've got these actually, so here they are. So these
are four 12-sided dice. They use the numbers from 1 to 48 so there's no repeats. So you're not going
to get a draw, that's easily solved. And they've been designed so that you're equally likely
to be first, second, third, and fourth - very nice. As a bonus though, it also works for subsets.
So if you had three friends they could pick any three of these dice and that would do
the same thing; they would be equally likely to be first, second, and third; or if you have two
friends they could pick any two of these dice and you'd be equally likely to be first and second - really nice.
So the question then was, what's it gonna look like for five players? Can we make a
set of five dice: no draws and you're equally likely to be first, second, third, fourth and fifth?
That's the question we've got a new solution for but before I show you that new solution I want to
show you the best answers we've had so far - just to build up to this. The first one I want to show you
is one of my own. Okay, I get to do this, it's my video, I can do that, right yeah okay. I don't know what you
imagine it's going to look like but this is it. So this is a set of 5 60 sided dice. They use
the numbers 1 to 300 and, just like they're supposed to, you roll them you're equally
likely to be first, second, third, fourth and fifth. Works for the subsets as well. So that's kind of
nice so there you go.
- (Brady: I can just see the numbers) You see, I should have painted in the numbers -
couldn't be bothered, couldn't be bothered. So this is my solution. I came up with this uh years
ago, not to be confused by the way with things like non-transitive dice or other things you may have
seen before. You know, it sounds similar but it is a different problem, this is a different solution
to that. So this is kind of nice. I might tell you a little bit about how we came across it. So
I did this with an internet friend of mine, Brian Pollock, and well we did a computer search but
just- to do a computer search would take a long time. If you search through every possible set of
five dice it's just a huge number, we're talking like many many many Googols of possibilities,
right. Too many to search through. So we did a clever search. So what we did is we looked
for dice with a particular nice mathematical structure and that allowed us to reject the wrong
answers really quickly. So we sort of narrowed our search down to these particularly nice kind of
dice. So you could reject the wrong ones easily, then the ones you can't reject we checked. That's
what we did, and that's what we found: we found the 60-sided dice. We knew that the answer- they're all
the same size like these are - we knew that the dice were going to be 30-sided or a multiple of 30. We
didn't find 30-sided dice but we did find these 60-sided dice. So that's nice, I was proud of this!
This was my solution to it; we can do better though. Because this solution, you're equally likely to be
first, second, third, fourth and fifth; what about if we make every order of the players equally likely?
So a, b, c, d, e is just as likely as e, d, c, b, a. That might sound like the same thing - that's
what I thought. When I said, is every order equally likely or every place equally likely?
- (As in who gets the highest, second highest-) Yeah I thought that- isn't that
the same? So no. Having every order is actually a stronger sense of fairness. This set that
I discovered, every place is equally likely, you're equally likely to be first, second,
third, fourth and fifth. Every order is not equally likely with this. In fact they're a, b,
c, d, e is less likely than e, d, c, b, a with this set. (Quick question. Is every- what about with these ones?)
- Every order is equally likely. It's something we appreciated slightly after the
fact. Oh, but should we make it every order equally likely? Yeah so that's a downfall
of those. I'm- like I said I, you know, we came up with this idea, I'm quite proud of it, but can
we make an even better set? Every order equally likely, that would be nice. Now the original
inventors of the Go First dice - that's Eric and Robert - they came up with a solution. Put my set
to one side, I'll show you Eric's solution. Got it- d'you want me- you see I've got it in this box.
- (Ok, it's a special box. ) Yeah, special box for it. Well, they look like this.
- (Ooh)
- Yeah, that's the right reaction (You answered my next question actually, do the
dice all have the same number of sides?)
- So if you relax that condition here is a set with all weird
sides. So they're not all the same number of sides but this is every order equally likely. We've got
a 20-sided dice here; we've got a 36 sided dice; here we've got two 48s and we've got a 54-sided
dice. So this is what we've got. They're all kind of weird values but every order equally likely.
And true for the subsets! I might be worth telling you how these were invented. The idea was you start
with a set that you already know is permutation fair. That's what we call it when all the orders
are equally likely. So let's start with a set of three dice. They're going to be 6-sided dice
and they're going to have these numbers on them: so let's say A here is going to be 2, 5, 7, 12, 14
and 17. B, I'll do B, is 3, 4, 8, 11, 13, 18. And we'll do C which is 1, 6, 9, 10, 15 and 16. There we go, 6-sided dice; they're using numbers 1 to 18, every
order is equally likely. What we can do though is turn that set of 3 into a set of 4. So
this is this is how you do it. What we're going to do first, we're going to double the size of these
dice, right. So we're going to repeat it: 2, 5, 7, 12, 14, 17 - I'm trying to fit
them into my piece of paper - do that again and for C, okay 1, 6, 9, 10, 15 and 16. And so that we
don't repeat the numbers, so we can tell them apart, I'm going to add 100 to the first copy and 200
to the second copy so that now they're different numbers. Look I've got gaps now; there are numbers
less than 100 that I could use. I've got a gap here between 118 and 201 - I could use that gap - and
I've got a gap here larger than 218. So we're going to create a new one called D. We're going to put
values in those gaps and we can calculate how many values to put in those gaps and keep the set of
dice still permutation fair. In this example if you put one number in the first gap; could be anything
I want, call it 50. I could put 50 here, I could put four numbers in that second gap - let's call
it 150 and then 151, 152, 153, there you go. And then one number in that last gap - 250? That will do it.
That's now a set of four dice which will still be permutation fair. We can shrink those numbers down
as well so that it's all consecutive. But now the new one I've introduced is now 6-sided; there's
no guarantee that that new die will have the same number of sides as the other dice that you started
with and that's why they start to have weird sizes. There are things you can do; like you can make the
dice like have the lowest common multiple of that- the dice start to get quite large though, the size of these
dice do get quite large. It doesn't have to be two copies either; sometimes you get a nicer set of
dice if you do like three copies and then fill those gaps. Or like five copies or ten copies -
sometimes you just get a nicer result by doing that instead. Now those two sets of dice I've just
shown you were the best answers we had up to about two months ago. And, Brady, I was going to make this
video about two months ago and that was going to be the end of the video. Just before I came and did
that video uh we were contacted; our little team of dice inventors were contacted by a mathematician
called Michael Purcell and he said I've got a new solution for you. Now I'm going to show you that,
that's it, that's what I've been building up to! (Oh, that's the box!)
- That's the box over here. So what
is it going to be? This is Michael's solution - you ready? (I'm trembling with anticipation)
- Right, here we go - this is it. This is a set of five 120-sided dice; all the same number of sides, which
is nice, and every order is equally likely as well. So I think this is one of my favorite sets so
far. His ideas were completely different to the ideas that we were using. He started with a set
of five 12-sided dice, but they weren't completely permutation fair. Any subset of four dice did work,
it was only partially there. What he did next is he made 10 copies of that, kind of like this method
here. So he made those 12-sided dice into 120-sided dice. That doesn't completely solve it,
they're still not permutation fair. What he did next is in the copies he started to swap
the rows over. So in the second copy he swapped the first row and the third row; in the third copy
he swapped the first row and the fifth row. So he started doing some permutations as we call them
on the rows within those copies that he made. By doing that it kind of balanced out all the sort of
biases, all the little problems, to sort of cancel themselves out. And the result was, this set of five
120-sided dice where every order is equally likely. The important thing about that is we kind of knew
you could do something like that; there was a team - actually they've got a YouTube channel as well so
I'm going to give them a little bit of a shout out. The polylog YouTube channel; they realised that if
you did every permutation on the rows that would balance out all the biases. They worked that out.
But if you do every permutation these are going to be huge dice. What Michael has done is he found
that you could do it with just 10 permutations, not just using every permutation. And there are some
open questions, because he did it with a computer. Is there some mathematical reason or mathematical
way to pick the permutations that balance out all those biases? We're not sure about that,
we're still thinking about that. You know, is is there a way to pick the initial seed
set of dice - that initial set of dice before we made copies? Is there a good way to pick that?
Is there a good way to pick the permutations? They're still problems we're working on but
yes at least with a computer search we can use those ideas and we can get this set of five 120-sided dice.
(Two questions)
- Yeah I'm ready (All right. First question is, I'm not questioning
your motivation for doing this, I think it's) (really cool. But are Go First dice like necessary?
Is there a demand in the gaming community for Go) (First dice?)
- No, no. So you can solve this problem
in simpler ways. So if I wanted to arrange five people in some order I would just have five
cards with 1, 2, 3, 4, 5 written on it and then you shuffle that up and they can pick
a card. I mean that's that's that's not the point. There are easier solutions to this. Another easy
solution by the way to this is you could just have one die with 120 sides on it. Each side would have
an order of the five people and then roll that. You could do it with one die; that's not the point
either, that's not fun. The fun is five players have one die each, and they all roll them, they
all have something to do, and then it orders them. That's the fun part of it.
- (And the other obvious
question that springs to mind is what about 6 dice?) Now 6, yes. So Eric uh who originally invented
this and is really like our boss in all of this; he has a website where he's collating all like the
best results. So for 6 shall I just- shall I just look at what the answer for 6 is? Ohh, no I'll save
that thought actually. Can I go back a step? Dun dun duh - cool. There is a second punch line to this video
because Michael contacted us with this new result and we were so excited by it. Our little
team of dice experts got working on it; well one in particular Bram Cohen, and he started
to mix and match our methods. So he started to use a bit of Michael's method, a bit of Eric's
method, started to match them together, just to see if he could find a better solution - and
this is his solution. So I've got another set! This is a set of four 36-sided dice and one
20-sided dice. So it's almost like they're all the same size, they're very similar sizes like oh, you're
almost all the same size. Also the dice are just so much smaller than than any of these solutions
we've got so far. So if you were just looking at adding up all the sides and seeing that- you
know, trying to minimise that number, then in that case by that measure uh this is the best set we've found.
- (So that's more efficient but that one) (there's more perfect because they're all the same)
- Yeah. Some of us like to minimise the total number of sides and some of us like to have them all
the same - because it makes it more like a toy I feel, but also minimise that number as well. So
for 6 players the best results we've got now um using actually Bram's method, the best
result we've got a set which is a 20-sided die and then five 360-sided dice.
- (That's quite asymmetrical)
- Yeah yeah yeah. Well it's- and that's because of how Bram's method worked. So
he actually used Michael's method to make these set of dice, and then by induction he created one
extra dice. Which is why this one has a different size to all the other dice. So that's why
this is the 20-sided dice there because it's fitting in the gaps. So this is why it's
a mix and match of of these two methods here. Can we do better? Can we find a smaller set of
dice? Personally I want to find a set of 5 30-sided dice. Theoretically we can make a set of five
30-sided dice but they might not exist. If they don't exist can we make a set of five 60-sided
dice? Or maybe this set of dice here, maybe this is kind of minimum in its way - or is it? Again these
are questions we still don't know the answers to. This episode's been supported by our
regular and superb sponsor, Brilliant, makers of these world-class
interactive lessons and courses. I was of course completely unsurprised to learn
they have a lot of stuff involving dice; including some of this which really dives into the sort of
stuff you've just been watching - dice competing against each other and stuff like that. Do make
sure you check it out, people. Whether it's for you or the learner in your life, I can't think
of a better way to expand your horizons than a subscription to Brilliant. They've just got so
much quality material; and new stuff's being added all the time, well designed, thoughtful and
sometimes quite funny. A bit of personality to it. Learn more at brilliant.org/Numberphile. They've
got a free 30-day trial which is amazing and using the URL on screen, that's going to get you
a 20% discount off their premium offering. There are links and details in the description
under the video.
