We designed special dice using math, but there’s a catch
How would you order the players randomly? Tell us in the comments. :)
Our Patreon: / polylog
Some proposals that already appeared in the comments section:
- Put cards with player names in a sack, shuffle, then take them out one by one to get the order.
- Simulate the above process using dice (see the comments by Jordan Weitz and samuraiwarm for how to do it).
- Just reroll the dice if there are ties. More precisely, the tied guys go to the next round where they decide the order between themselves (or some of them need to go to the third round etc.).
- One die with n! sides, write the final permutations on it.
The first two solutions are also similar to our solution with cards and to a so-called Fisher-Yates algorithm for sampling a random permutation.
If you consider the third solution with coins instead of dice, what it is doing is that each player is basically sampling a uniformly random number from [0,1], bit by bit. Then, they are ordered by the size of sampled numbers. This corresponds to a simple and popular algorithm to create a random permutation: just sample n random reals from [0,1] and order them by size; the probability of ties is negligible.
#SoME2
00:00 Intro
06:53 General Construction
15:26 Final Thoughts
Eric's webpage: www.ericharshbarger.org/dice/g...
Also: • James Grime 'Go First ...
The code for the animations and for finding fair dice:
github.com/polylog-cs/fair_dice
github.com/gavento/permutatio...
To make this video, we used manim, a Python library: docs.manim.community/en/stable/
The color palette we use:
ethanschoonover.com/solarized/
A few more facts and (open) problems if you are interested:
-- You can generalize the lower bound on the number of sides of fair dice for general n; concretely, you can use the prime number theorem (or bounds on the so-called primorial) to show that n same-sized fair dice have to have 2^{\Omega(n)} sides each.
-- On the other hand, our construction gives dice with (n!)^{n-1} = 2^{O(n^2 \log n)} sides. It would be interesting to see these two bounds getting closer, if you have progress on that, let us know!
-- The lower bound on the number of sides can be generalized to the case when the dice are allowed to have different numbers of sides, then it tells you that for any n fair dice, at least 99% of them have to have 2^{\Omega(n)} sides. But we don't know whether all dice have to have exponentially many sides.
-- Suppose I give you a string of length n over alphabet with k letters and ask you whether it is fair. The naive way to check it has time complexity O(n^k). Can you do it in time O(f(k) * n) for some function f?
Rolls 10^60 sided dice Still rolls crit-fail 1
OKAY BUT IMAGINE GETTING THAT CRIT THOUGH!!!
You will check had failed. Hive managed to touch your mind directly. With this touch your own personality began to melt away under pressure of chaotic fragments of minds from thousands of already assimilated before you people. With time passing on, your ego get more and more "washed out". Little bit more and you will be consumed by thoughts of horde of puppets that were assimilated to hive mind before you. Good bye! Sorry if my english wasn't perfect there to sound well enough. It is not my native langauge.
@@ScarletStump and it’s on a useless check
Okay but is 20 still the nat? Or is it Nat10^60?
@@Zacian2.0 yes
My first thought was to use rock-paper-scissors style dice, where absolute value doesn't matter.
Interesting idea!
sadly 3 way ties can still happen, can't they? unless I'm misinterpreting how you hoped they would be used
@@Glennjamyyyn... Just tie break.
@@Mernom ik, that's what I wanted to say when watching this entire video too, but I'm just humoring this person's idea and wondering how it would work
Check out Oskar van Deventer's seven no transitive dice video!
The Queen flip at 17:56 is absolutely savage, how could someone do such a thing, especially with another Queen in play?
so glad we caught this clutch play on camera
What game is this?
@@spaghettiking653 Chess
@@tayloresformes2789 I'm still not sure I understand... chess isn't played with cards, so what's going on?
@@spaghettiking653 They're joking
2:01 while this IS technically a solution, it's my a very fun one imo. with this setup, only player A would even need to roll their die to know who goes first
Yeah, we basically reinvented one guy flipping a coin... :D
@@PolylogCS Yeah. I paused the video to come up with solutions, and one of them was this, but (a) it's a trivial and uninteresting solution, and more importantly (b) it won't scale.
I actually quite like that solution. Not because it's the best way to do it, but just because of how it gets your mind out of complicated ways of interpreting the problem. It sort of grounds you into looking at the amount of A>B vs the amount of B>A, it shows that the end the result of each match up is the important bit. In fact, I feel like the video could have stayed on that frame for a bit longer :)
Adds a 4th player, now needs a hyper cube to graph it
After adding 5th player, he creates a... Pentacube.
@@fangier0 would the 6th player cause an omegacube
@@gamerhurley Probably
The 5D and 6D cases are called a penteract and a hexeract, respectively.
@@danielsebald5639 Ok, thx, I will correct my month old comment
for any 'normal-sized dice, the Planck length and blackholes would seem to come into play for 10 people
What’s that nonsense even supposed to mean? And I know about the Planck length and black holes decently.
@@coleozaeta6344 the 200+ thumbs up and your statement that you understand Plank Length & Black's Holes would seem to indicate you do not. Any attempt to probe or make structures smaller than the Plank length would require enough energy that it would collapse into a black hole- thus the sarcastic humor about such a dice turning into a black hole while attempting to make its sides
@@coleozaeta6344 made fun of yourself
@@wallstreetoneil it probably wouldnt have to increase it's density, and therefore make a black hole, but planck length would still possible be an issue
@@karlcole5617no, it’s not the dice increasing density that’s the issue. The issue is whatever machine you try to use in order to build such a dice and carve with such precision would require so much energy that a black hole would form. This is the same reason why plank length is an issue to begin with.
I'm pretty sure you're trying to trick us into group theory using shiny dices.
Is it group theory? Always has been.
@@watchableraven3517 *holds gun
Game theory
Everything is group theory
The solution of 2:02 is clearly equivalent to a single coin flip. Player A *_rolls_* a 2-sided dice with the values "high" and "low" and Player B *_rolls_* a one-sided dice with the value "medium".
How about n - 1 dice, with 2,3,4...n sides? First player is the player number (choose numbers arbitrarily) of the n-sided, then the kth highest remaining from the n-1 sided, etc? This set is minimal.
This is also a nice solution to the original ordering problem! Let me explain it in my own words. We somehow want to simulate the process where we put the nametags of the players in a bag, then shuffle the bag, then pick the nametags from the bag one by one to get the random order of players. To simulate this process, we first roll the first, n-sided, die with numbers 1..n to tell us which one of the n players goes first. Then, we roll the second, n-1-sided, die with numbers 1..n-1 to tell us which of the remaining n-1 players goes second. The second roll is a bit tricky, since we do not know a priori who was picked first. So, we say that if the number i comes up on that die, it will mean that we pick the guy with the i-th smallest number from the set of remaining players. This will be either the player i or the player i+1, depending on the first roll. And then we continue in this fashion, until everybody is picked, with the throw of the final two-sided die choosing the order of the last two players. See also the similar solution of Samuraiwarm that is related to Jordan's the same way as insertionsort is related to selectionsort. By the way, both of these proposals are similar to the so-called Fisher-Yates algorithm for sampling a random permutation. On the other hand, fair dice aim to simulate a different process that you would probably use in practice if you wanted to code a program that samples a random permutation: You would give each player a uniform random number from [0,1] and then you would order them by the size of this number. Since the probability of tie is zero, it works. The whole problem with fair dice is that we are trying to simulate this process, which is very natural in the continuous, infinite, world using only our finite dice. :)
I don't understand wat the smart peoples are saying
@@Hyperdal well, you only need to pass algebra 1 and 1st grade reading to understand the comment
@@Hyperdal he's basically saying roll a dice to pick the next player
@@danielyuan9862 Dude.... that's... that's not what they're saying. They're talking about rolling n-1 dice with n sides where n is the player count. That is not "a dice" that is multiple. Plus I think the phrase "First player is the player number" is really bizarre, can someone clear that up for me?
Just imagine you and 9 of your friends go play a board game with random orders every turn then the host just pulls out 10 MASSIVE ball and tells everyone to roll it.
That is the most shoehorned 20xx I've ever seen in an olympiad problem
Idt this is an Olympiad problem.
Oops, I didn't watch the rest of the video.
How do you solve that part, I have a solution but I dont think its the intended one. I got a 2^(n+1)-1 lower limit for general n.
yeah, isn't that part trivial? there are way more than 2022 permutations of 26 elements
This shows how sometimes, trying to find a solution to a problem is way harder than finding a way around it
How are we going to create 13th thousand-sided dice? "This is just an implementation detail" Why is it so funny to me?
Great video! The way things started with a simple problem that slowly increased in complexity was super engaging.
Here's an interesting point about possible repeats. Sure, it's necessary that no two dice share values, but why can't different faces of one dice share values? That is how I got a relatively simple fix for the 2 person on 6-sided dice problematic solution provided. This increases the search area significantly, and may lead to significant simplifications. One problem, however, is that the string representation no longer works as-is. One fix is to have equal faces on one dice correspond to equal consecutive letters in a string. This keeps the functionality of the string representation, but raises another question: does that mean that any solution with repeated faces is translatable to one of the simplest no-repeats type? I believe so, so this realistically changes nothing in the solution itself. One thing it changes, however: for each sequence of repeating digits in the string representation, the final dice's largest needed number can be shrunk by one less than that sequence's length. This leads to the interesting question of what is the lowest maximal number possible?
Very nice observation! As you say, whenever you have e.g. a solution with two sides with fives on one die, you can change the two sides to one five and one six and increment all original numbers of size at least six by one. This way we get the numbering as in the video. So this trick is mostly good for making the numbers smaller which can be helpful in practice. A related thing: if you look carefully at the 4 twelve-sided dice in the video, you can notice that it is in fact two 12-sided dice and two 6-sided. This is how we found it, since the search space was much smaller than looking for all 12-sided dice! Then we "expanded" the six sided dice into twelve side ones to make the story simple. But this means that with your trick we could make the largest number in use smaller by 12 just by always using the same number twice in the originally 6-sided dice.
@@PolylogCS Thank you. On the subject of the fix for the problematic solution, your proposed transformation turns my fix into yours. Also, I'm not sure how much more helpful it would be in practice, but the algorithm for writing dice faces based on the string representation is no more complex than it is for the no repeats scenario. You made a very interesting point about the 48-letter solution (at 15:17). The idea here is that all sequences of A's and B's are of even length. In general, if all sequences (totalling k instances)of X's come in lengths that divide m, then the dice represented by X's can be modeled by a dice of k/m faces, and vice versa.
@@minamagdy4126 hm sorry I don't understand the second paragraph
@@PolylogCS As an example, the A's in the 48-letter solution come in even length substrings, and there are 12 of the letter in total. One can then imagine grouping pairs "AA" into a new symbol S, replacing the 12-sided A dice with a 6-sided S dice. Another example would be having six B's in a sequence like "ABBBAABBBAAA", where they come in substrings of length 3. One can then imagine grouping up the "BBB" into a single symbol S, replacing the B dice with an S coin.
I would say the solution to the problem is to number the players, have a die with a number of faces equal to or greater than the number of players, roll it until it gets to a number less than or equal to the number of players; then that is the player who goes first. Do this again with repeated rolls until you find a number corresponding to a different player who will then go second, and so on until you have a smaller number of remaining players that you can use the method described in the video on (when this method would otherwise have too many re-rolls).
Math isn't normally my cup of tea, but you definitely managed to make an interesting video
Thanks!
My first thought is to just create a base- *n* string of length *p* , where each of *p* players contributes a single place. Then you can arbitrarily assign strings to each of the *p!* player ordering. For example, for *p=2* players each would flip an *n=2* -sided dice, and say 00 or 01 is player 1 first, and 10 or 11 is player 2 first. For larger *p* , you'd need to find an *n* such that the *n^p* strings can evenly divide the *p!* orderings. Hope that the last step doesn't create problems...
This is an interesting take! If all your dice have the same number of sides, then it does not matter how you translate thrown values into final orders, you still can use the divisibility argument from the video to show that the n needs to be big with respect to p. If you allow the dice to have different sizes, then the solution of Jordan Weitz (pinned comment) is maybe what you are looking for. :)
🤓
@@PolylogCS Following from the same argument, we could create a set of fair dice with max n! sides: - let the first player have a n-sided die numbered 1-n. This determines which order they go in directly. - let the second player have a n-1-sided die. This determines which of the remaining spots they go in. - continue to the second to last player who will flip a coin, and the last player doesn't do anything. Now you have n different dice, but that could be solved by increasing their size to n! and letting each player take their answer modulo some number. Ex for 3 players with 6 sided dice: - player 1 takes their answer modulo 3 and goes into that place (1, 2 or 3) - player 2 takes their answer modulo 2 and goes into that remaining place (1 or 2, offset by player 1's position) - player 3 takes their answer modulo 1, effectively always rolling a 1 and goes into the last remaining position
@@MaserXYZ Nice trick how to make the Jordan Weitz's solution work with same sized dice! It would in fact be slightly better than n! factorial as the least common multiple of 1...n suffices.
just have players reroll if they tie, the one who gets highest in that roll has priority (i.e three people roll as follows: 3 5 5. the two 5's reroll and get 2 and 4. now the order is the 3, then the 2, then the 4)
Not the best solution, as the time it takes to select turn order is potentially unbounded. Imagine playing with a million friends: with the solution in the video, everyone simply rolls their larger-than-the-known-universe dice once. With d6s, it would take 7 or 8 rounds of rolling to get to a turn order, and possibly many more.
@@jasperday9020 did you read what you wrote? 🤣 It's better to have 1 million dices that have more sides than atoms on the universe than having 1 million people having to reroll their 6s die a couple of times (and the more times the less likely its happen)
@@meunomejaestavaemuso not in mathematics
@@jasperday9020 Taking 7 rolls to determine turn order among a million friends ain't too bad, all things considered. You can't do too much better than this, because you need log_2(1,000,000!) random bits to select a permutation. And each die roll gives you log_2(6) bits. A quick calculation shows that at the absolute minimum you need 7,152,473 rolls of a d6 to determine the order of a million players.
I think the main issue is that with normal die there is the chance (albeit a slim one) for there to be an infinite number of rerolls. I know this is pedantic but mathematicians usually are about things like this. So, the solution we’re looking for makes it impossible for there to be any rerolls whatsoever.
Amazing video, there’s so much effort put into it, and the math is just beautiful, congrats!!!
As you broke down the ABC matrix and possibilities, it just struck me how similar that is to the gene A/C/G/T combination possibilities. It would be interesting to see an analysis of if the gene "dice" are fair.
Plot twist: Life on earth is a side effect of a multidimensional being trying to construct a set of fair dice for 4 players by brute-forcing, but they forgot the stop condition in the algorithm
After I watch this, I think I would write 4 labels (1, 2, 3, 4) into 4 pieces of paper and let 4 people blind picking the letters instead of using dice. 😅
Thinking about this from a game design perspective, I think I found an interesting tweak to the problem that gives a nice alternative. The thing that's nice about having all the players roll is that it gives them a feeling of *agency*. (This is one reason that the dealer or dice roller rotates in games even though, probabilistically, it doesn't matter.) And the common suggestion of "just have one player roll a n!-die" doesn't have that. That also makes me think that, no matter how fair the unique dice, there's still the potential for "I don't want the die with the 1 on it" complaints. So here's my alternative problem idea: each player rolls an identical die once, and all the rolls impact the outcome. Sketch of a solution: Every player rolls a n!-sided die, and you pick which one to use using the sum of the rolls modulo n. n! is a multiple of n, so even though the sum of the rolls is highly non-uniform, the sum modulo n is still perfectly uniform, so it's a fair choice between the rolls, and each roll has sufficient impact on the choice that it's always possible to change one roll to set the desired roller. (And humans could actually compute it, since you can take modulo n before doing the sum, so even for 10 players you're just adding single digits, not 7-digit numbers.) That also has the nice property that there's no way for the first roller to be certain they're going first (or last) because they rolled the max (or min) possible value, nor even to be pretty sure they're going early or late like rolling for initiative in D&D. This is like the classic "how do you do a fair coin flip when neither of you trust the other's coin" problem -- you flip both coins, and use match/mismatch (aka sum modulo 2) to make the decision, so that it's fair if either of the coins is fair. (And if both are unfair there's no way to know which choice to make to get an advantage, so it still works for one choice, just not for repeated choices.) Of course, the sample-without-replacement solution also gives agency, so long as you don't use a dealer. TransAmerica does this well -- the official way is to spread the cards on the table (face down, of course) and then people pick the cards that will make up their hand, and there's always more cards than players so everyone is making a choice. And because there are 5 categories of cards, this is also way easier than trying to deal them. (It also doesn't have unambiguously-much-better cards like Euchre or BlackJack do, as it's the combinations that really matter, so cheating from marking is less of a concern.)
I like your solution and I think that your comments about agency are very much to the point! :)
Your channel is really amazing. I've only seen a few videos but taking practical problems like this makes them genuinely applicable. I could see these literally being used for lesson plans in school.
If statistics had been explained to me with examples like this, I think I would have been far more interested in learning instead of just treating it like a chore.
Really good video. I usually leave a whole list of suggestions, but for this video, I really only had one issue. You show that the fair ordering in a list translates into fairness in a concatenated list (starting around 11:00), but you don’t really show why the concatenation assembles the sub-lists in a fair manner. I believe it. You do a good job proving that they are fair. But if I tried to explain this video to someone; the part where I explain why it works out that way would get really hand wavy... which is a shame because that’s pretty important. At 2:10, I appreciate the numbers being drawn on top of the 3d mesh so they aren’t hidden. It so rare that a math video gets to say “so we just check all of them.” That’s great.
Thanks for the feedback! :)
brute force ain't the prettiest thing, but it does contains a lot of hidden and ignored treasures :^)
🤓
My immediate thought was that you have 6 possible outcomes and a 6 sided dice, just write the order on each side
No way! I added this to my watch later a while ago and I just around to it now that I’m taking an intro to combinatorics class. Converting to the string representation is such a simple yet crucial injection. Everything else in the video is great too but that little detail made me smile.
Excellent work and presentation
I mean if were being practical, you can have each player just flip a coin, assign tails a value of 0, and assign heads 1/2ⁿ, where n is the (positive integer) number of the flip, starting at 1, and each time theres two or more players with a tie, have each of those players flip another coin, then find the sum of each player's flips to this point, then repeat until no values are equal, it's a brute force solution, but you don't need impossible to construct 3d objects. If we're just doing maths to make it as convenient as possible (only 1 roll per player), as far as I can tell, the absolute minimum number of sides a dice needs is all possible ways to arrange the group of players (P!, where P is the number of players), divided by the number of players, so why not just cut out the middleman and make 1 single dice which has P! sides, one side for each combination? ie, for 3 players, make a dice with sides {ABC, ACB, BAC, BCA, CAB, CBA}, and for 4, {ABCD, ABDC, ACBD... DCBA)
Agree! See the reply to ગણિતી :)
@@PolylogCS I have submitted a possible method for your review, very long comment, please check if you have to approve it manually!
@@GioLasarDesign Hi, I never encountered manually checking comments, I cannot see anything to approve.
@@PolylogCS I will try writing here in a few chunks, please let me know if this could help investigating the problem. PART 1 I am not a Mathematician, so for fun I tried looking from a different perspective, that is starting from two sides instead of six. For two players, you need two coins having the same probability to win against each other: Player 1: value A1 / value B1 Player 2: value A2 / value B2 Let’s say that value A1 should be higher than A2, and lower than B2, so that we have A2 < A1 < B2 Doing the same for B1, we see that it can’t be lower than A2 and higher than B2, but it can be the opposite. So we have that B1 must be higher than A2 and lower than B2, as in A2 < B1 < B2. By joining both propositions, we have A2 < (A1 < B1) or (B1 < A1) < B2 so A1 and B1 must be consequential. Using only numbers 1 to 4, we have only one possible combination, because swapping A1 and B1 is pointless. Player 1: 2 / 3 Player 2: 1 / 4 If we try the possible outcomes, player 1 wins for 2 > 1 and 3 > 1, while player 2 for 4 > 2 and 4 > 3.
@@PolylogCS PART 2 We notice three possible “rules” or patterns: Rule 1) the sum of all sides for each coin is the same Rule 2) because of Rule 1, first side increases bottom to top (1, 2) and second side top to bottom (3, 4) Rule 3) the sum of candidates with higher values opposing each outcome, is the same, making the coins “fair” To explain #3 with an example, against player 1 we have one value higher than 2, and one value higher than 3 (in both cases, that is the 4), while against player 2 we have two values higher than 1 (that is 2 and 3), and zero higher than 4.
Very interesting. Also the level of complexity increased at good speed
I just new you were using Solarized as soon as I saw the miniature. That's so cool! I love it.
Absolutely brilliant video!
How do you only have 277 subs? This content is amazing!
amazing video it should have many more views...very well done you defiantly have a lot of potential
definitely*
Thanks for your great Ideas
Great video! Thank you for not being happy with just getting a solution with the computer, but rather trying to understand that solution and trying to generalize. That's the beauty that math can offer. 16:05 "Having two different ways of looking at the same thing may well be the most powerful math trick known to mankind" Indeed! I've always found it fascinating how there are many interpretations and many frameworks that can be used to solve the same problem. This is one of the reasons why it's important to have all different kinds of people doing math and thinking about problems. Hypothetically: If every mathematician in the world came from one country, all with a completely standardized curriculum the whole way through... We would still have variation in thought process, but way less than the current variation throughout the math community. So keep doing math! You will offer a unique and valuable perspective :)
WONDERFUL now i can calculate the chance of my character entering and winning a lottery on a winter tuesday whilst listening to bach on a gramophone invented 20 years earlier than historically recorded.
My approach would have been just to take the initial ordering provided by the "everyone rolls a standard D6", then break ties recursively by rolling again, or by some other method like flipping a D2 for binary tiebreaks.
Rerolling to break ties obviously works well enough as a practical solution, but mathematically it's not a great solution because there's no guarantee it'll successfully break the tie within any given amount of time. That is, you could theoretically just keep rolling ties over and over again and never actually produce a winner.
@@SSM24_ but that's statistically unlikely
Yeah, it's like how the best way to pick a random point in a circle is just to pick a random point in a square, and try again if it was outside the circle. The odds of needing to retry are so low that it's just not a problem.
You can also think of this as just rolling a dice with more sides -- every roll is just the next decimal place for a number between 0 and 1, where you only "calculate" as much precision as is needed to resolve the predicate.
Basically, lets say the roll is 3 3 6, so third is set to go first, and the other two roll for second and third turn.
damn, this is a very in depth video about a subject I never even considered. really well explained!
14:12 My eureka moment! Nice proof! I love that the programmatic way of thinking helped you come up with this proof. I do programming too, but I thought mathematics as this distant field where you have to have a different mindset to be successful. But apparently you proved me wrong!
Here's my shot at a better proof using an algorithm. We can try keep tweaking the state until it is fair, like in the case of 1:51, red is leading blue by 3 (or 6 depending on how you count the difference). So we can change the column 7 to 13, and that will add 3 extra blocks to blocks to the blue field. Finally we can reassign the number to fit in 1-12 range. We can probably do the same thing in higher dimensions when the hyper cube is divisible by the number of players. We just need to come up with a way to "transfer" blocks between different players that is guaranteed to exist in every case, like if we could find a way to transfer a single (or two depending on how you count difference) block from one player to another reliably in any situation, that would make it a proof by induction.
Interesting approach! Though I currently don't see how to make it work, for larger n there are a lot of things depending on every one number...
15:19 After 2 hours, I was just able to slightly improve the construction from n*((n!)^(n-1)) output string size to (2n)*((n!/2)^(n-2)). I can't think of any more improvement in asymptotic complexity O(n * (n!)^(n-2) * 2^(-n)), and certainly not anything that can remove the (n!)^n side from the creation. If anyone finds anything related to this, please let me know; below is how I improved my string size: - Start from initial string "A B C ... chr(N-1) chr(N) chr(N) chr(N-1) ... C B A" instead of "A B C ... chr(N-1) chr(N)". There are two advantages of this : -> Every pair of characters are counted equally, bringing down N-1 iteration steps by 1 to N-2 iteration steps. -> Every possible subsequence of a permutation (pairs, triplets, quadruplets, etc.) has exactly the equal number of instances in the string as its reverse. So ABEDC comes the same number of times as CDEBA. This property is important for my algorithm and this is going to be maintained over all iterations. - For each iteration, permute the previous string into (N!/2) different strings, such that no pair of permutations selected are reverses of each other. An example of such set is all the permutations where 2 always comes after 1. Place these strings side by side, this is the new string for next iteration. -> Say we have shown in the previous iteration that the string contains all (x-1)-lets (subsequences of a permutation of size x-1) with equal count, then in this iteration we want to show this for x-lets. For this we compare two x-lets A and B -> If A and B are constructed from some different permuted strings then we can prove it using strong induction (same as in video) -> If A and B are reverses of each other, then from the property that I stated in 1.2, they have equal count here. -> For the other cases where A and B are picked whole from a single permuted string, we can show that the sum of counts over all all such strings will be equal for A and B. This is because for all such A and B, A can be converted to B or the reverse of B using one of the (N!/2) permutations.
This sounds very interesting! But why is property 1.2 preserved?
Also try to search comments for "cotes" - this is a construction of Erik that would be probably asymptotically better but I don't know how to make it work
@@PolylogCS Shit I forgot to preserve 1.2 😔😔, I though it might be trivial using the last 3 points of my proof, but yea it isnt necessarily true
@@PolylogCS I can't find that comment, is it one of those methods where you initialize some specific unfair string of size n!n or similar, and then try to make it fair by some small number of changes? You can get permalink for some specific comment by clicking on its timestamp, like kzhead.info/sun/YJpthbhwsJuhoZ8/bejne.html&lc=Ugwp5vV0NAR_QrweUHp4AaABAg Edit: I don't know why but if you click on the link it doesn't retain the comment info, but you can copy paste it into your address bar.
@@nishchaymanwani36 the comment by Austin Conner
Dokoukal jsem celé video, přečetl komentáře, pustil si videoznova a pak jsem si v intru všiml vašich jmen. Celou tu dobu jsem neměl tušení že jste Češi XD. Jo a video bylo skvělé 👍
Čau:)
great video!
Wow very beautiful editing! Beautiful and interesting vedio. Great Job!
At my table, people with tie have to re-roll. It works like that: Let's assume we have 4 people, and we roll d20 for order. Rolls are 10, 13, 13, 18. In that situation, player with 18 is 1st, player with 10 is 4th. Two players with 13 fight for 2nd and 3rd place. Now those 2 re-roll until there is no tie and the one with higher number gets 2nd place, and with lower gets 3rd. Works for any amount of people and with any dice. Tho, it requires re-rolls. But it's still more convenient than rolling 10^60 dice. Lmao. But anyway, interesting video and solution.
There's still a little probability that they will always roll tie dice.
@@Igorious92 That's true. Probability of always rolling ties approaches 0 with each roll. But never become 0.
for 3 players, you only need one six sided die with faces saying: 123 132 213 231 312 321 essentially, have the one die describe all possible outcomes.
Really I think this is a far superior solution. Because a 10!-sided die for 10 players is just as (im)practical to make as a 10^60-sided die, and is much easier to use since you don't have people comparing 60-digit numbers to figure out who goes first.
Yes, or you could use the cards
My KZhead recommendations are now actually giving me math problems that are slightly over my head
Wouw. I didn't expect this. Really good and informative but still fun video.
If you allow the dice the have a different number of sides there is a simple solution: Dice 1. 0 Dice 2. -1, 1 Dice 3. -2 -0.5 0.5 2 Dice 4. -3 -1.5 -0.75 -0.25 0.25 0.75 1.5 3 ... This although this still requires an exponential number of total sides.
Hi, this actually does not work: because of the divisibility, if you have >=3 dice with possibly different numbers of sides, there still has to be at least one of them with number of sides divisible by 3. But nice try! :)
Fejfo, you need to consider the percentage chance of winning for each new dice you add, you only deal with halves here as you just have 2n sides to each dice. Thus for your 3 dice example dice 1 will only have a 25% chance of winning, and for 3 dice the chance should be 33.33%. For the 2nd dice in the 3 dice example, it has 37.5% chance of winning. And the 3rd dice have 37.5% chance of winning as well. That's not fair, when the distribution of wins is 0.25, 0.375, 0.375. For the dice to have a fair distribution of 3 dice it has to be 1/3 for all dice. And in your example, the more dice you add, the lower the chance of winning for the first dice. In the 4 dice example, the math is more annoying but, it has 1/8 chance of winning, instead of the 1/4 it should have if it was fair.
@@livedandletdie thanks, this is much better explanation than ours. The divisibility argument is just telling you it cannot work without explaining why. :)
9:24 Does this mean that you would get fair 2p dice if you just removed the C's?
yes!
@@PolylogCS Is this generalizable to all n-player dice?
@@electroflame6188 yes! if you got the k-tuple numbers right in a string, this means that if you restrict it to any k letters, the restriction is fair. :)
OMG I wrote a similar thing about how using the permutations of n+1 symbols one could construct fair dices for n players
@@leirumf5476 Interesting!, can you expand on it?
by far the best and most fun math viedeo i saw in a long time
My intuition, looking at the strings, is that there must be some sort of compression scheme that you could apply. Just as a rough sketch of my idea without any rigor... There may be a way to construct a mapping after each step that replaces a run of letters with a single letter -- perhaps you can replace AB with D, AC with E, and so on, and then apply a transformation that maps each new symbol back to one of the players. The key to my intuition is that you're making assertions about the properties of the longer strings that must hold true because of the relationship to the smaller strings. This directly implies that there must be reducible entropy that a compression scheme could exploit.
I love how one player "corrects" the played card in the last scene! 🤣 Definitely a candidate for some applied group theory 😊
2:02 The single coin toss solution is so much easier and scales elegantly. All you really need is a die with n! sides (and a mapping) to permute n players. The problem posed here is interesting but really needs a better motivation. Beautiful solutions are usually surprisingly simple for the problem at hand, but the formulation here doesn’t satisfy that property.
incredible video and very underrated channel❤
My instinct is to assign a (set of) number to each of the players and the person whose turn it is rolls a Dn die (where N is the number of players or a multiple of N where a dice of Dn can’t be found similar to the case described for the case of games with less than 4 players below) at the end of their turn. For cases where the number of players is lower than 4 (D4 is the smallest regular die) a D6 can be used with players being assigned 3 or 2 numbers each for the case of 2 and 3 players respectively. Alternative a dice shaped like a three sided prism can be rolled when there are 3 players and coin flips for 2 players. Using a single die instead of a pair of more dice completely removes the problem of some outcomes being more likely than others and impossible outcomes (where the outcome is less than the number of dice being used)
I like how this goes from a board game player order to having a string of letters that could be comparable to making dna.
For practicality, I'd go with "everyone throws a die, if two players are tied they throw again to know wich of these two go first" BUT I would also add that turns go clockwise. So no matter who wins by going first, they next players simply must go clockwise. Or the cards approach you suggested
TNice tutorials is one of the best intro soft softs I've ever seen. The entire basic worksoftow with no B.S.!
About 1:30 in, this is my solution: Take the faces of the dice, put them in a grid nxn, where n is the number of the faces on each die. The grid should be arranged as such: row 1 columns: 1,...,n. row 2 columns: n+1,...2n. Row m columns: 1+n(m-1),...,nm Take each column and adjust them as such: start at the first column, and move all following columns down by 1. Repeat the following step until the nth column is reached: move to the next column, and move all following columns down by 1. Note: the number that leaves the grid in any given column should be placed at the top of the column. In this fashion, each column C should have each of its entries rotated C-1 times. The main flaw here is that it may not work with fewer than n players. I have not given it the due consideration as to if that is the case.
This video gets to the essence of what I love about math
Group theory + a very hard super specific upper limit problem is ♥️
For n players you could do it with one n sided dice thrown once. Assign each player a number (e.g. 1, 2, 3, 4, 5, 6) and establish an ordering for the the dice faces (e.g. top > bottom > front > back > left > right) and what the POV will be. Roll the dice, each number will be in one of the positions and each position already has an assigned order. In the example ordering the person with the number that appeared on top goes first, the person with the number on the bottom goes second, etc. P.S.: I'm pretty sure I just made up a more complicated way of picking a card from a deck. P.P.S: I guess you should be able to define a fair POV by saying something like "however the dice lands, turn it clockwise until one face is fully facing the thrower if it's not doing so already". Might be hard to mathematically define this for a 256 sided dice of something but what do I know.
If I were to implement this in a video game, I would just do like you showed where they just pick cards, but the players all pick at the same time, like how people pick characters in for example mario kart, or super smash bros. So when they all say that they agree on a selection, the selected cards flip, and the game continues. Also I would just scale it by increasing the amount of selections, and have the amount be something like 1.25 * the amount of players (and probably have some kind of player cap to limit the insanity)
Once I saw the general construction with the string of letters I realized I had seen the problem before. Definitely hid it from me for a while
i retained none of that info but enjoyed it either way, thanks man
You know I reallya am enjoying this SOME2 thing
super cool (albeit insanely large) construction!
Awesome video
You could use up to a ten-sided die with any number of people by using decimals. Example: four people each roll a 6-sided die. They get: 2, 4, 4, 5. The two players who rolled a 4 reroll and get 1 and 3. The final order is 2, 4.1, 4.3, 5. Every time you have to reroll to break a tie, the new value is an additional decimal place.
Granted I haven't watched the rest of this video yet but I'm wondering if there are solutions if you give each player a pair of dice and the dynamics of that...i.e. if you could still prevent ties with the additional element of a second die with generated numbers while also keeping fair odds for all players
the problem is an intersting one, but for a practical solution to random turn order you should just reroll the ties e.g. for 4, 5, 5: 4 goes first and the 5s reroll to determine who goes second this is how you decide seating order for playing a game like perudo (liars dice) where you can have as many people in the game as want to play.
i play dnd so ties like that happen at some points so what i do is the people who tied will roll again to see which of the those ones goes first so say you have 5 people and 2 of them roll 15 but the others get like 18, 4, 6, and 13. the two that got 15 would still be inbetween 18 and 13 but they would roll to see which of the 15s go first
Úžasný video. Máte skvělou angličtinu, beze jmen bych to nepoznal.
The lowest number of sides would be the prime factorial(the product of the primes that are smaller or equal to the number) of the number of players So a 10 player game can have dice with only 210 sides and it could be contain fair dice
Divide the integers into 6 sets of subsequent integers (1,2,3),(4,5,6),... Then give each dice 2 of the lowest 2 of the middle and 2 of the highest in a set. This provides an intuitive set of solutions. Technically, you can generalise this more, except for states where the integers aren't subsequent. Sometimes, the probability of winning is continuously distributed, which means that the probability of winning isn't equal for all dice w.r.t each other, but in the game of 3.
It only works in a semi-sane way for exactly 3 people playing, but you could get away with exactly one roll of a d6, in something akin to a three-sided coinflip, if you assign a directional value, for example even numbers go left, odd - right. So for 1 the person throwing the die would go first, then pass the turn in a counterclockwise direction, for 2 - clockwise; 3 and 4 mean they would go second, and 5 and 6 - they go last, effectively "choosing" what triplet would be the order for the round: 1 for ABC, 2 for ACB, 3 for BAC, and so on, if player A throws the die. Sounds a bit convoluted but should be easy enough to figure out on the spot - 6 bits is exactly enough to encode the order for all the unique 3! permutations. (Figuring out the 1d24 throws for 4 people however already will be kinda insane lol.)
If there are 6 different orderings that we want to occur with the same likely hood. We can use a cube dice with the 6 different orderings on it.
What a fun problem! After a bunch of noodling, here’s my idea for 3 people picking their order (avoids ties, and makes feel like there’s strategy, but not as elegant as I wanted). The 3 people are ordered by some natural aspect (they can stand in a line, or ordering is by height, birthday, whatever). Like the video we’ll call them A, B, and C. All 3 will make their choice at the same time like RPS. A is choosing what spot they want, 1, 2, or 3 (by holding up that many fingers) B is choosing the remaining order (thumbs up for alphabetical, down reverse) C is choosing who gets the spot A picked - A or B (by pointing at one of them, or Thumbs up for A, down for B) For example, A holds up 2 fingers, B is thumbs up, C is pointing at B: C says B should get spot 2, B says the other spots are alphabetical - ABC Another one - A holds up 1, B is thumbs down, C is pointing at A: C picks A, B says reverse order: ACB There are 6 orderings but 12 possible outcomes, and it seems to work out that each of the orderings has exactly 2 outcomes
I love dice problems. I myself thought to make as few chess960 dices as possible. Chess960 is a game where your pieces at the bottom is shuffled randomly before the game. Two constraints. Your bishops use different colours on the chessboard and your King starts between your rooks. Turns out there are 959 alien positions with those rules (normal setup is one that can occur randomly). I came up with bishop dice, queen dice and knight dice, so three dices. Throw them all at once but read them in that order. Bishop dice is a D16 (light squared Bishop can occupy 4 and dark squared also 4). One side would read AB meaning you put your bishops marked A and B on the bottom. Now 6 squares remain. Throw a D6, the most common dice. Count available squares from A to H and place your queen there. Now there is 5 available squares. There are 20 different ways to make two different numbers from 1 to 5 but only 10 ways if you have to sort them chronologically or non-chronologically. In this case, a D10 with a non chronological order of two numbers from 5 to 1. First number tells you where to put the first knight on available squares, second number tells you where to put the next one. Now there are three squares left. You don't need a dice though cause the King has to be placed between the rooks.
Roll a 6-sided dice, 1 or 2 means player 1 is first, 3 or 4 means player 2 is first, 5 or 6 means player 3 is first Roll again with other two players choosing even/odd and player who wins is second
This was a lot of extra work for something that could’ve been solved by saying “ties roll again until they no longer get a tie”
That 10^60 number only comes from your gaurantee system, which is of course x((x!)^(x-1)), but the actual number of required sides is likely much much lower, as seen with the 4 player case, where you got 13,000 but the computer found 12
0:45 Multiple die with different values will weigh the probability distribution unevenly. The best way would be with a single set of numbers that each player chooses from randomly: deck of cards, bag of numbered chips, etc.
From description -- Suppose I give you a string of length n over alphabet with k letters and ask you whether it is fair. The naive way to check it has time complexity O(n^k). Can you do it in time O(f(k) * n) for some function f? Can't we iterate over all permutations of k letters, and for any particular permutation p1,p2...pk, use O(n*k) DP to calculate the number of occurrences of this permutation. The DP state would be like dp[i][j] for all 0
Also I just realised that these dp numbers may be very large (O((n/k)^k). So to remove that arithmetic time (O(k log(n/k)) per addition), you can calculate these values modulo some small number of large prime numbers (which fit int data type) to get an algorithm with some very very small false positive rates.
Yes! Its nice to see that somebody reads video description! :D This is what we implemented to speed up the fair dice search. I did not realize the issue with large numbers, good catch! :)
There's a much easier, simpler, straightforward solution to this that most tabletop games that do this already employ. You just roll again among those who tied until you're no longer tied.
There are probably neat solutions when we allow for dice with different number of sides to avoid the divisibility dilemma. However, finding the shortest sequence of letters is an interesting problem in it's own right. I might think about this a bit.
Great video! I was wondering if it makes any sense to work per side of each dice. Essentially doing a high-mid-low split: H: 3,6,9,12,15,18 (Winning side) M: 2,5,8,11,14,17 (Non-loser/non-winner side) L: 1,4,7,10,13,16 (Losing side) Assigning an evenly distributed amount of highs/mids/lows per dice. Dice 1: H,M,L,H,M,L Dice 2: M,L,H,M,L,H Dice 3: L,H,M,L,H,M It’s extendable in the same fashion as the ABCD. I don’t know too much about statistics, so maybe I’m completely wrong in my assumptions. Regardless you made a wonderful video that I and many others enjoyed watching and finding the fun in this topic. Thank you!
Nice idea! I think this way you could construct dice that would be approximately fair in the sense that the probabilities would be very close to what we want. However, if you want the probabilities to be exactly what we want, the problem is much harder and I am not sure whether this could lead to a construction of fair dice. But nice try nevertheless! :)
Just make them all roll dice, highest number goes first, if there are ties each player in the tie rolls again and the highest number goes first in the tie, repeating as necessary. With this method it doesn't matter how many sides the dice have, though the more sides the better (to reduce chances of getting ties). You can visualize this, let's use a 10-sided die as an example, by "everyone rolls the ones digit of the number, if there are any ties, the people in the tie roll for the tenths digit, if there are still ties, they roll for the hundreds digit", and so on. Or you could have a die with n sides, one for each player. You roll the dice to determine a random starting player, then they roll the dice to find out the next player (rerolling if the player has already come up), repeating until all but one player has been chosen, who automatically becomes the last player.
I feel like the solutions could be shortened by using super permutations somehow, but I haven’t yet found out how.
That was a fun journey!
I think building a directed graph would be a good start. Maybe something like coloring or something would lead to some insights.
Hm, what kind of graph would you build?
my idea as just "if theres a tie, those players repeat the dice role"
The cards and then string of As, Bs, and Cs reminded me a lot of modern Tetris games' piece queue RNG Iirc it's commonly called "7-bag" and the idea is kinda like going through a deck of cards and shuffling it back together when you empty the deck; the queue consists of 7-piece long "blocks" which have one instance of each possible tetromino (I, O, S, Z, T, J, and L), so you only ever see 2 of the same piece in a row at best, and there's no I-piece droughts (which matters a lot when more lines cleared at once = more points or garbage sent to your opponent)
Much quicker and more practical to deal a card to each player, highest goes first, second highest goes second, etc. Make the rules clear beforehand whether Ace represents the highest or the lowest. For ties, refer to the first letter of the suit and where this letter appears in the alphabet. The later in the alphabet, the higher the rank. So Clubs (lowest), Diamonds, Hearts, Spades (highest). So for example a 7 of Hearts beats a 6 of Spades since 7 is greater than 6, so we don't rely on the suit. But for Ace of Diamonds and Ace of Clubs, we have a tie so we refer to the suit. The "D" in Diamonds comes later in the alphabet than the "C" in Clubs, so the Ace of Diamonds is higher. As long as you make all these rules clear beforehand, for example that Ace of Spades is the absolute highest (and any other card shouldn't beat it, so for example jokers shouldn't be in the deck and would require a re-draw), then this is a pretty simple way to order the players. You could even do something like have a bunch of index cards with different numbers written on each of them. Shuffle a bunch of them to reduce the chance of encountering a marked card. Deal them out, and highest number goes first, etc.
Sounds like a tough gamble.
I wonder how it would look if we simplify the problem from "fair" to "fair enough". E.G. every player has an equal chance of being in any particular place, but not every permutation has an equal chance of occuring. For example, in the 3 player case, given player 1 is 1st, player 2 would have an increased probability of being 2nd, but if player 3 is 1st it's lowered so it balances out.
Alternate solution for the original problem: Instead of assigning a number to each player and then ordering them by that number, each player would roll for their position in the order directly. It's easier than intuition tells us! My idea comes from pulling straws: say there are 4 straws of which one is shorter, no matter if you pull 1st, 2nd, 3ed or 4th you always have a 1 in 4 chance of getting the short straw. So to convert this into generating an order: We first have player A determin their position in the order, there's currently only one player so he automatically goes to #1. Next player B, there's one player in the current order so he rolls a d2 to determine if he goes to position #1 (bumping player A down to #2) or to position #2. Same thing for player C, only he rolls a d3. Rolling a 1 means position #1 bumping every one else down. Rolling a 2 means position #2 pumping the previous player in that spot down. And rolling a 3 results in position #3. This goes on for however many players you have. Now you can use a separate dice for each player or you could use one with !n sides where n is the number of players. Now for the fun part, let's calculate each player's chance to go first when there's 4 players... Player A: 1 * ½ * ⅔ * ¾ = ¼ Player B: ½ * ⅔ * ¾ = ¼ Player C: ⅓ * ¾ = ¼ Player D: ¼ = ¼ Again, look up how the chance on pulling the straw works for an elaborate explanation.
It's pretty obvious how to order the three dice. You have 18 numbers. Put them in groups of three, starting with [123], [456].. etc. then just distribute the numbers so that they fulfil the six conditions given earlier,. The first group is distributed to match AC, the third AC, etc. Done.
Man this feels just like ramsey theory.... I love it!
Thanks, that is a pretty interesting take that did not occur to us. I believe it feels like ramsey theory because it is an "intricate inductive construction that ends up with insanely large object"? :D
@@PolylogCS Yeah pretty much, you're combinatorically brute forcing a set to have certain properties with a coloring. And as you say, like most ramsey theory problems, the object is much larger than it needs to be.
Renumbering the dice makes for an interesting degrees of freedom exercise and video, but now the game requires special dice. Rules to handle ties are much easier. TR1: Dice that tie are equivalent to 0. TR2: If a roll results in all 0s the last person to play plays again. Now more people can play with less hassle.