We designed special dice using math, but there’s a catch

a while ago our board game enthusiast friend was thinking about creating a board game with several players where in each round the players would play in some order so far that sounds like pretty much every other board game but the important twist would be that in each round the players would play in a random order but how do you achieve that well you could give every player a die each of them would throw it and you would order them increasingly by the value they have thrown like this but this doesn't quite work because what should we do if there are ties remember it's us who are designing the game so maybe we could write some unique numbers on the dice so that ties do not happen can we do that in such a way that the ordering of players is still perfectly random this was the question asked by our friend we had a lot of fun thinking about it and in this video we want to share some of it with you also it turns out that our friend was not the first one to ask this question which we'll come back to at the end okay so let us explain what we want with an example let's say there are just two players a and b each of them has a die with some numbers written on it for instance like this and remember the same number shouldn't be used twice because that could lead to a tie what we want is that if we look at all 36 possible outcomes and we split them into those where a is smaller than b and those where a is larger there is the same number of both kinds for example these dice do not work since there are more red squares than blue squares a would have the smaller number more often but there is a solution do you see it feel free to pause the video and try and find it ok here is one way we can just fix the first attempt by swapping the higher three numbers of the two dice you can see that there is now exactly as many red squares as blue squares there are other solutions as well like this one so the case of two players is simple but the case of three players is already a lot more interesting there are now six times six times six possible outcomes and we can visualize them using a cube like this just like we used a square in the two-player case now there are already three factorial or six possible orderings of the three players we want to write different numbers on the dice so that among all six cubed possible outcomes all six orderings of the three players appear the same number of times meaning they are all equally likely in other words we want each ordering to occur 36 times we will call dice satisfying this condition fair i hope you can see how we can generalize this notion to more than three players as well by the way calling the dice fair is a small mathematical sin because that name is already used for something different but i hope you can forgive us so how can we approach the problem of finding three paradise well it would be a bit hypocritical to ask you to figure it out because we actually didn't think about it too much either instead we just wrote a program to find all solutions the number of candidates is not that big you may have already noticed that although the numbers on the dice can in principle be arbitrary we only care about their order so we can assume they are just the integers from 1 to 18. then there are 18 choose 6 ways of picking the numbers for the first die next we pick 6 numbers for the second die which we can do in 12 choose 6 ways and after this the numbers for the third eye are fixed if you do the math you'll find that there are only about 17 million candidates so we just checked all of them and found that there actually are some fair dice up to some symmetries there are these six solutions in fact the fancy 3d animation you saw earlier featured the first of these okay but after looking at these for some time we didn't have much of an intuition about the problem so we thought maybe looking at the solutions for four players could help us so again we wrote a program to find them now there are no longer solutions with six sided dice but there are plenty with 12 sided ones like this one unfortunately we then realized that even 12 sided dice wouldn't be enough for 5 players there we'd need at least 30 sides let me explain why it'll be easier if we first consider the 3 player case remember that we did find some solutions for three six sided dice but could we also have a solution with three five-sided dice it turns out that we could not do you see why well since we have three dice with five sides each there are 5 cubed or 125 possible outcomes in total we group these into 6 groups based on what ordering the result indicates for the dice to be fair we need each group to have the same number of outcomes but this can never happen we would need to have 125 over 6 outcomes in each group but because 125 is not divisible by 6 this is not an integer applying this reasoning to five players let's say all dice have s sides then there would be s to the fifth possible outcomes so s to the fifth needs to be divisible by five factorial since that's how many orderings of players there are but this implies that s to the fifth needs to be divisible by 5 factorial and that in turn means that s must be divisible by 2 3 and 5. so it's at least 30. so five equally sized dice must have 30 sides or more and for seven dice this minimum becomes 210 sides this made us a little sad since it shows that fair dice are not very scalable to more than 4 players at the same time if you want a random ordering of players for a board game there are other simple solutions for example you could use a deck with unique cards you let each player draw a card from the deck and have that decide the order okay so there are other more reasonable solutions to the original board game problem but the inner mathematician in you may have already asked the following question is it possible to construct fair dice for any number of players by that i mean if you invite your friends and there are now 10 people who want to play can you create a set of 10 fair dice possibly with a really really big number of sides as you may have guessed it turns out the answer is yes here is how we prove this the fact that we started by coding a program to find all solutions was actually really helpful because in the process we realized there is a different way of looking at the problem basically you can write the numbers on the dice from left to right like this which means that you can represent the dice with just one string of six a's six b's and six c's it doesn't matter whether we represent the dice using numbers like on the left or as a string like on the right since the two are just two different representations of the same thing and now the numbers on player ace dice are telling us at which positions of the string there are a's so when player a throws an 8 on their die it corresponds to selecting the 8th letter in the string which must be an a similarly if b throws a 16 this corresponds to selecting this letter b and if c throws a 3 it corresponds to this letter c with this particular outcome player c would go first then a and finally b notice that in the string we can just read the highlighted letters from left to right and it gives us the order of players this is great because it allows us to check whether a set of dice is fair by looking at their string representation we need to go over all possible triplets of different letters and check that the number of occurrences of abc acb and so on are all the same if they are all six orders of players are equally likely which means that the corresponding dice are fair as you can see this is the case here because we are looking at the first of the six solutions we found using the computer here's all six of them in their string representation it would be nice if we could find some general rule in them that would allow us to construct fair strings for any number of players if you look at the first two solutions they are actually kind of interesting because they are just the triplet abc repeated six times each time with its letters permuted differently so maybe this is the way to approach the problem let's see if we just take the six permutations of the triplet abc and we concatenate them in some arbitrary way and then count the triplets ah too bad it's not fair but not all hope is lost even though we didn't solve the problem entirely we still made some partial progress because it turns out that in this string if we count the number of all pairs instead of triplets they are all the same do you see why if you want pause for a bit and think about it okay let's look at what contributes to the count of a b pairs and compare it to the count of for instance c a's first there are those where a is in one of the six short parts of the string and b is in a different one whenever you take two different parts they will generate exactly one a b pair and then there are also three more a b's where both a and b are from the same part but if you now look at the count of c a's you'll notice that again two different parts generate exactly one ca and again there are three cas that are fully in one part the parts where we found abs are not the same ones as those where we found cas but it really doesn't matter it's kind of clear that if they are in total three abs generated inside a single part there has to be the same number of cas generated inside a single part this is because the parts are just all possible permuted versions of the same starting string so they cannot favor a b over c a in general we can see that no matter how we order the six parts of the string we always get the same counts of every pair but it turns out that we can generalize this argument here's how we can use it to build a fair string for three players we start with the string abc then we do this construction where we write it six times permute their letters and concatenate the strings in any order and then well we just do it once more what i mean is that we take this string of 18 letters and create six copies of it then we permute the letters i want to stress that we are changing the letters not their positions and as the last step just take all of those strings and concatenate them in any order if we do that we get this beauty let's compute the counts of all six possible triplets in it and it's a fair string but why well it's basically the same argument as before let's think about for example why the counts of abcs and cabs are equal kind of like before there are multiple types of contributions to the number of abcs based on which letters come from what part of the big string for instance there are a bunch of contributions where a comes from one part b from another and c from yet another or a b could be in one part and c in another one or a in one part and b c somewhere else or finally the whole abc could be inside a single part trying to find a formula for how many abcs there are in total seems like it would be a horrible mess so it comes in handy that we actually don't care about that we only want to show that they are the same number of abcs as cabs and so on and this turns out to be much simpler for example look at the contributions where a b comes from this part and c from that part their number is just the product of the number of a b's in the left part and the number of c's in the right part but look the left part already has the same number of abs and cas and the right part well it certainly has the same number of c's and b's so the contribution to the number of abcs is the same as that to the number of cabs and the great thing is that for this argument it really doesn't matter how we split the triplet there is just one exception and that's the case where we don't split abc at all so all letters are in the same part for abc there are 36 occurrences in the first part 43 in the second part etc if we now look at the cab contributions where all letters are in the same part the individual numbers are different but in fact these are just the same six numbers only in a different order this follows from the fact that the six strings are really just six permuted versions of the same starting string so they cannot prefer abc over cab so the number of abcs and cabs is the same and the string is fair and this kind of argument works for any number of players so this way we can create fair dice for any number of people let's try out the construction for 4 players we start with the string abcd and what's important about it is that it has the same number of a's b's c's and d's we create all its 24 versions and concatenate them in some order to get a string where the number of pairs is correct then we repeat and get a string where the number of triplets is correct then we do it one last time and the resulting string which doesn't fit on the screen anymore corresponds to four fair dice and the size of this string grows quite a lot our string for 4 players has about 55 000 letters i'm not sure how hard it is to create 13 000 sided dice but this is just an implementation detail so we are quite wasteful compared to the computer which found strings with just 48 letters corresponding to four 12 sided dice so if you have a different solution that doesn't produce insanely long strings definitely let us know i think that the tricks we've used to work out the construction of fair dice are actually quite general so let me quickly sum them up the most helpful observation was that we can think about strings instead of dice at first we thought this was just a nice trick that made it easier to write a program but then it really helped lead us towards the general construction i mean if you think of strings it's quite natural to try and concatenate a few of them or think about counting pairs instead of triplets but this would not come naturally at all if we were thinking about building dice in general having two different ways of looking at the same thing may well be the most powerful matrix known to mankind a different trick we used was to look at small examples by trying to decipher the meaning behind the solution for three people we got the idea that if you concatenate permuted versions of a short string good things might happen and the last trick was trying to split one heart problem into many manageable ones like instead of getting the counts of all triplets right at once we just got the pairs right in the first step and then used it in the next iteration to get an even better string okay and here comes the final plot twist at some point we found out that we were not the first ones who had thought about this cute concept of fair dice in fact about 10 years earlier eric hershberger came across it for a similar reason as our friend you should totally check out his website that we link in the video description he and his collaborators really delved much deeper into the topic and had some pretty amazing results for example about constructing dice for five or 6 people you can really see the difference between theoreticians and practitioners at work here because whereas eric even constructed physical prototypes of fair dice for 5 and 6 players we instead focused on proving that you can play with as many friends as you like as long as you don't mind that for 10 players the number of sides is like 10 to the 60th and the only practical thing that we got out of it was that we made it into this insanely hard math olympiad problem that was used this year in a certain math competition but what we and eric clearly had in common was that we had a great time thinking about fair dice and i hope we managed to share a bit of that fun with you as well see you next time

Channel: polylog

Views: 527,344

Keywords:

Id: -64UT8yikng

Length: 18min 1sec (1081 seconds)

Published: Tue Aug 16 2022