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

[@TechSY730]

Rolls 10^60 sided dice Still rolls crit-fail 1

[@ScarletStump]

OKAY BUT IMAGINE GETTING THAT CRIT THOUGH!!!

[@DimkaTsv]

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.

[@Lilly-Lilac]

@@ScarletStump and it’s on a useless check

[@Zacian2.0]

Okay but is 20 still the nat? Or is it Nat10^60?

[@The_WhitePencil]

@@Zacian2.0 yes

[@dumnor]

My first thought was to use rock-paper-scissors style dice, where absolute value doesn't matter.

[@PolylogCS]

Interesting idea!

[@Glennjamyyyn]

sadly 3 way ties can still happen, can't they? unless I'm misinterpreting how you hoped they would be used

[@Mernom]

@@Glennjamyyyn... Just tie break.

[@Glennjamyyyn]

@@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

[@LeoStaley]

Check out Oskar van Deventer's seven no transitive dice video!

[@Jelly420]

The Queen flip at 17:56 is absolutely savage, how could someone do such a thing, especially with another Queen in play?

[@PolylogCS]

so glad we caught this clutch play on camera

[@spaghettiking653]

What game is this?

[@tayloresformes2789]

@@spaghettiking653 Chess

[@spaghettiking653]

@@tayloresformes2789 I'm still not sure I understand... chess isn't played with cards, so what's going on?

[@madyingermany]

@@spaghettiking653 They're joking

[@AlexPies1]

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

[@PolylogCS]

Yeah, we basically reinvented one guy flipping a coin... :D

[@rosuav]

@@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.

[@Vezur-MathPuzzles]

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 :)

[@wallstreetoneil]

for any 'normal-sized dice, the Planck length and blackholes would seem to come into play for 10 people

[@coleozaeta6344]

What’s that nonsense even supposed to mean? And I know about the Planck length and black holes decently.

[@wallstreetoneil]

@@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

[@Annihilator_5024]

@@coleozaeta6344 made fun of yourself

[@karlcole5617]

@@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

[@andrewkarsten5268]

@@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.

[@Firestar9]

Adds a 4th player, now needs a hyper cube to graph it

[@fangier0]

After adding 5th player, he creates a... Pentacube.

[@gamerhurley]

@@fangier0 would the 6th player cause an omegacube

[@fangier0]

@@gamerhurley Probably

[@danielsebald5639]

The 5D and 6D cases are called a penteract and a hexeract, respectively.

[@fangier0]

@@danielsebald5639 Ok, thx, I will correct my month old comment

[@crumblinggolem6327]

I'm pretty sure you're trying to trick us into group theory using shiny dices.

[@watchableraven3517]

Is it group theory? Always has been.

[@kosuken]

@@watchableraven3517 *holds gun

[@muk_is_superior]

Game theory

[@jackwilliams1468]

Everything is group theory

[@nomukun1138]

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".

[@JordanWeitz]

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.

[@PolylogCS]

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. :)

[@Hyperdal]

I don't understand wat the smart peoples are saying

[@danielyuan9862]

@@Hyperdal well, you only need to pass algebra 1 and 1st grade reading to understand the comment

[@danielyuan9862]

@@Hyperdal he's basically saying roll a dice to pick the next player

[@brendandangelo715]

@@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?

[@iwersonsch5131]

That is the most shoehorned 20xx I've ever seen in an olympiad problem

[@danielyuan9862]

Idt this is an Olympiad problem.

[@danielyuan9862]

Oops, I didn't watch the rest of the video.

[@nishchaymanwani36]

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.

[@galoomba5559]

yeah, isn't that part trivial? there are way more than 2022 permutations of 26 elements

[@RGC_animation]

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.

[@leonardofilho7397]

This shows how sometimes, trying to find a solution to a problem is way harder than finding a way around it

[@noahbrooks4030]

Great video! The way things started with a simple problem that slowly increased in complexity was super engaging.

[@minamagdy4126]

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?

[@PolylogCS]

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.

[@minamagdy4126]

@@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.

[@PolylogCS]

@@minamagdy4126 hm sorry I don't understand the second paragraph

[@minamagdy4126]

@@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.

[@evannibbe9375]

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).

[@ugd_insanitystar4732]

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)

[@jasperday9020]

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.

[@meunomejaestavaemuso]

@@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)

[@rz2374]

@@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.

[@secluded_little_spot]

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.

[@mangle9143]

Math isn't normally my cup of tea, but you definitely managed to make an interesting video

[@PolylogCS]

Thanks!

[@samiramin5895]

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...

[@PolylogCS]

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. :)

[@Deeznuts-gd6lm]

🤓

[@MaserXYZ]

@@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

[@PolylogCS]

@@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.

[@maratburnaev7089]

How are we going to create 13th thousand-sided dice? "This is just an implementation detail" Why is it so funny to me?

[@hightechredneck3362]

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.

[@JonathanWinterflood]

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

[@pfeilspitze]

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.)

[@PolylogCS]

I like your solution and I think that your comments about agency are very much to the point! :)

[@justinwatson1510]

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.

[@syllabusgames2681]

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.

[@PolylogCS]

Thanks for the feedback! :)

[@aloysiuskurnia7643]

brute force ain't the prettiest thing, but it does contains a lot of hidden and ignored treasures :^)

[@Deeznuts-gd6lm]

🤓

[@ananpinya835]

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. 😅

[@michaelmam1490]

How do you only have 277 subs? This content is amazing!

[@LucasRibeiro-zn6qi]

Amazing video, there’s so much effort put into it, and the math is just beautiful, congrats!!!

[@reesespieces5386]

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.

[@Balderdashes]

My immediate thought was that you have 6 possible outcomes and a 6 sided dice, just write the order on each side

[@thatonepersonyouknowtheone7781]

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)

[@PolylogCS]

Agree! See the reply to ગણિતી :)

[@GioLasarDesign]

@@PolylogCS I have submitted a possible method for your review, very long comment, please check if you have to approve it manually!

[@PolylogCS]

@@GioLasarDesign Hi, I never encountered manually checking comments, I cannot see anything to approve.

[@GioLasarDesign]

@@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.

[@GioLasarDesign]

@@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.

[@Homieslice]

amazing video it should have many more views...very well done you defiantly have a lot of potential

[@2520WasTaken]

definitely*

[@DingleFlop]

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.

[@anonimosu7425]

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.

[@zefile]

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.

[@pfeilspitze]

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.

[@goatgamer001]

Yes, or you could use the cards

[@polecat3]

Very interesting. Also the level of complexity increased at good speed

[@Jorge-xf9gs]

I just new you were using Solarized as soon as I saw the miniature. That's so cool! I love it.

[@fuuryuuSKK]

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.

[@SSM24_]

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.

[@meunomejaestavaemuso]

@@SSM24_ but that's statistically unlikely

[@pfeilspitze]

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.

[@pfeilspitze]

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.

[@arahman56]

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.

[@Vezur-MathPuzzles]

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 :)

[@nishchaymanwani36]

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.

[@PolylogCS]

This sounds very interesting! But why is property 1.2 preserved?

[@PolylogCS]

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

[@nishchaymanwani36]

@@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

[@nishchaymanwani36]

@@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 kzbin.info/www/bejne/Y2eXhodurs6epMk&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.

[@PolylogCS]

@@nishchaymanwani36 the comment by Austin Conner

[@edgarallenhoe3518]

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.

[@DasherDash]

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.

[@Igorious92]

There's still a little probability that they will always roll tie dice.

[@DasherDash]

@@Igorious92 That's true. Probability of always rolling ties approaches 0 with each roll. But never become 0.

[@Censeo]

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.

[@fejfo6559]

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.

[@PolylogCS]

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! :)

[@livedandletdie]

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.

[@PolylogCS]

@@livedandletdie thanks, this is much better explanation than ours. The divisibility argument is just telling you it cannot work without explaining why. :)

[@SiiKiiN]

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.

[@brekol9545]

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é 👍

[@PolylogCS]

Čau:)

[@1337w0n]

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.

[@electroflame6188]

9:24 Does this mean that you would get fair 2p dice if you just removed the C's?

[@PolylogCS]

yes!

[@electroflame6188]

@@PolylogCS Is this generalizable to all n-player dice?

[@PolylogCS]

@@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. :)

[@leirumf5476]

OMG I wrote a similar thing about how using the permutations of n+1 symbols one could construct fair dices for n players

[@PolylogCS]

@@leirumf5476 Interesting!, can you expand on it?

[@mercylessplayer]

My KZbin recommendations are now actually giving me math problems that are slightly over my head

[@Wolfsspinne]

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.

[@Shandolum2]

Look at it another way. In a 3 player example. You want player 1 to win 1/3rd of the time. If that player loses, you should have a 1/2 change that player 2 wins. If player 2 loses, then player 3 wins. To satisfy this requirement, you need a dice that can be divided by 2 and 3. The first number that satisfies this is 6. A 4 player game needs to satisfy 2, 3 and 4. Which the first number is 12. 5 players -> 30, 6 players to 30, 7 players to 210, 8 players to 840 In the 3 player example, you assign 1/3rd of the lowest numbers (1, 2) to player 1, and assign 2/3rd of the highest numbers (15, 16, 17, 18) Then assign the lowest remaining 1/2 of the numbers to player 2 (3, 4, 5), and 1/2 of the remaining highest numbers as well (12, 13, 14). Lastly assign the rest to the 3rd player, and you have fair dice. This can be accomplished with any amount of dice, and is way easier and simpler than the solution presented above.

[@PolylogCS]

This is a nice way how to randomly select the first person! It is by the way implementing a procedure known as reservoir sampling. But it does not solve our requirement that all permutations have the same probability - in your dice the probability of 3rd, 1st, 2nd is equal to zero.

[@Shandolum2]

@@PolylogCS ah right, I was too focused on selecting the winner.

[@FerousFolly]

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.

[@efkastner]

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

[@electricengine8407]

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

[@dyvel]

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.

[@7GLuke]

5d30 is my holy grail. I've been obsessed with this problem since the numberphile video came out

[@RichieD993]

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.

[@battlesheep2552]

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.

[@samsibbens8164]

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

[@elorz007]

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.

[@jasonpatterson8091]

As an upper bound for possibilities, for n players I think n dice with n! sides that are numbered from 1 to n(n!) should always work. Consider 10 players: Each face could have values from 1-10, 11-20, 21-30, etc. Call these sides A, B, C, etc. Since A always goes before B the only time it matters what particular number is on a face is when there is a tie. Worst case scenario is all 10 players rolling the same face. If there is a face for each possible ordering of players (i.e. n! faces) then any ties will result in a fair distribution of orderings.

[@PolylogCS]

Hm but you also have all of these cases where e.g. two players roll the same face. How do you handle these?

[@nishchaymanwani36]

If I understood your solution correctly, I think there is a flaw here. Your worst case is when some players (say 5) roll dice on 1 face, and the others on another face. Because you have put your n! permutations on your faces in some particular order, these types of situations will cause your count to be favoured in some orderings more than others.

[@nishchaymanwani36]

Say for example the ordering of players 1,2,3,4,5,10,9,8,7,6. If you placed the permutations with high probability of a

[@jasonpatterson8091]

@@PolylogCS Right, so each of the n! faces has a range of n values. The ordering of the n values is such that there is one face with each possible ordering of players. So if multiple players roll side A, the ordering might be 1,2,3,4,5,6,7,8,9,10 for the 10 dice. If multiple players roll side B, the ordering might be 1,2,3,4,5,6,7,8,10,9. And so on, for each of the n! arrangements of the players 1 - 10. Since there is no bias in which face A - ZZZZZ (whatever 10! would be in alphanumeric code) is rolled, it is equally likely that a player would roll a permutation that is winning or losing for them against any combination of the 10 players. I used this thinking when you started the video and almost instantly had an ordering for 3 players in my head, and it was one of the 6 you showed (which involved n(n!) values on n dice with n! sides, mind you...). It's not reasonable to type a solution for 4 players into a youtube comment, but I'll share a google sheet with a set showing what I mean in a separate comment here in a few minutes (it will take a bit to generate 24 sided dice values). Not sure if it will cause it to be deleted as an outside link or not.

[@jasonpatterson8091]

@@nishchaymanwani36 That's just it, there is a face for each ordering of players, n!. So for 10 players the dice would have 10! faces (3,628,800) with values up to n(n!) (36,288,000). Adam, Bob, Chuck, ... and Jim are playing and as long as they roll unique faces, the values sort themselves out like normal dice (side 1 for the 10 dice = 1,2,3,4,5,6,7,8,9,10 would always beat side 2 for the dice = 11,12,13,14,15,16,17,18,20,19, and so on). If any two players roll the same face, then we have to decide who wins the " face tie." If there is a face for every possible arrangement of the 10 players (i.e. Each side i of the n! sides has a unique arrangement of players featuring an ordering of 10i + (1 through 10)) then it is equally likely for any player to win or lose against any arrangement of other players because the face that they happen to tie on is equally likely. If it doesn't get autodeleted, check the google sheet I posted for a solution for 4 players to see what I mean if this isn't clear. It should extend to any number of players fairly cleanly, and the solution for 3 players given in the video is an example of what I'm talking about. For a super simple 2 player example: Coins with side values 1, 4 and 2, 3. Again, n "dice" with n! sides with values over a range of n(n!). I don't think there's a simpler legit arrangement for 2 players where each has a die.

[@OblivionWonderlust]

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)

[@BlackSoap361]

Or use a single 6-sided die, where each side has the order for the players given. (abc, acb, bac, bca, cab, cba) Or just use a lookup table. Or, for any n players, make a die with n! sides.

[@danelyn.1374]

damn, this is a very in depth video about a subject I never even considered. really well explained!

[@luckylmj]

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.

[@CathodeRayKobold]

Here's a solution I thought of on the spot: A middling die (For example, -3 -2 -1 1 2 3), an outer extremes die (-9 -8 -7 7 8 9) and some dice between them (-6 -5 -4 4 5 6), etc. No die would have a statistical advantage over any other yet they all have completely unique numbers. Then interleave the numbers to give the extreme dice a chance of going in the middle. (a b c c b a, not a b c a b c) Only thing is some dice would have a slightly higher chance of going either first or last, while others would have a slightly higher chance of going in the middle.

[@pfeilspitze]

Fun idea! There's probably a way to resolve the issue you raised. But all I can think of is having people randomly pick which die they'll use from an urn, at which point we're back to sampling without replacement, and if we were ok with using that in the solution then we'd be using the deck-of-card approach and not bothering with dice rolls at all.

[@byeguyssry]

I might be missing something, but can't figure out what it is. My thought was, You mentioned at 9:25 that in any string of 6 permutations of ABC in any order, the strings AB, BA, BC, etc. all appear the same amount of times. In that case, say we want a fair dice for 2 players. Why not just make the random string of 6 permutations of ABC, then remove all Cs? Since AB=BA before removing Cs, this should hold after removing Cs as well. Therefore, for 3 players, make the string of the 24 permutations of ABCD in a random order, then remove all Ds. The remaining string ought to be a fair dice.

[@Yutaro-Yoshii]

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!

[@Yutaro-Yoshii]

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.

[@PolylogCS]

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...

[@tciddados]

Unless I'm missing something, shouldn't the number of sides each die needs never exceed n! ? As the whole issues is solving tiebreakers, you'd just have to take a typical 1-N! die (ex 1-6 for 3 players, equal to the N! # of potential player orders like seen at 2:45 ), multiply each side's value by N (3,6,9,12,15,18), and then for each side on the die, you would assign each side a potential player order, and on each player's die, subtract a correction # from it based on their order position (ex: for the 2 side that became 6, if we call it the "A

[@paulcooper8818]

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.

[@pokeface119]

There's a far far easier way of coming up with a 6 sided dice that's fair. For 5 people you're trying to cram 125 numbers into 5 different dice, when in reality it only matters how many numbers are higher than each other for each one.. meaning you need only between 1-30 instead of 1-125. x=players y=sides on dice x•y=number set to use. 5•6=30 and you write it out like below; Number set; 1 6 11 16 21 26 2 7 12 17 22 27 3 8 13 18 23 28 4 9 14 19 24 29 5 10 15 20 25 30 I then write out the numbers as letters from lowest number to highest number for each COLOMN. A A A A A A B B B B B B C C C C C C D D D D D D E E E E E E A's = 1 Point B's = 2 Point C's = 3 Point D's = 4 Point E's = 5 Point Then you make each ROW equal 18 points in value so its equal chances (Edit, if you're wondering where 18 came from.. You add up all the points and divide it by the amount of players. 90/5=18) And re-arranging the number set I have above gives; 4 8 15 17 22 27 2 7 11 19 25 29 1 10 12 16 24 30 5 6 13 20 21 28 3 9 14 18 23 26 Each ROW is the set of numbers on the dice the player gets. 5 Players, and 5 Rows. Please feel free to comment any questions or replies to my comment! I love discussions xD

[@user-wm1em1rg4p]

If you interpret "fair" player ordering a bit more broadly, you can use this method: For a player group of size M, obtain M dice of some side number M*N, where M and N are natural numbers. Create an "original" set of dice, where each player has a 100% chance of a given player order, by making each die a consecutive segment of the natural numbers M*N long. A six player case with d6s using your grid method: A: 1 2 3 4 5 6 B: 7 8 9 10 11 12 ... Permute these dice by selecting each group of M columns and shifting them in one direction vertically by the column group number minus 1. This means every player has an equal chance of rolling a number from any "original" set, and players who roll from the same set have fair odds of being at any point in the sequence relative to other individual players. With our example, as M=1: A': 1 32 27 22 17 12 B': 7 2 33 28 23 18 C': 13 8 3 34 29 24 D': 19 14 9 4 35 30 E': 25 20 15 10 5 36 F': 31 26 21 16 11 6

[@PolylogCS]

hm, so what is your claim for the dice A'...F'?

[@AndrewCrimefighter]

Better solution to the ordering problem would be to have a player shuffle a deck of N cards, where N is the number of players, then deal them out facedown. The other players take a card from the table and everyone flips to check the ordering. Shuffling cards randomly, especially a small deck, is harder to do fairly than rolling a die fairly, but if you do it this way all you need to do is have the dealer shuffle under the table or something so the other players can't track the cards, if that's a concern, then make the dealer pick last to ensure they can't rig the outcome even if they know the order of the cards

[@hofh]

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.)

[@aroundandround]

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.

[@Krebzonide]

What if you just add colors? For 2 players, if you have a tie then red beats blue on even and blue beats red on odd. You could easily scale this to 3 players and making the rule based on the value mod 3. It would stop working at 4 though since 6 isn't divisible by 4, but dnd players probably have some 4 sided dice. Even if they are the same color just use the player name instead. Bill beats Joe on evens.

[@nishchaymanwani36]

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

[@nishchaymanwani36]

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.

[@PolylogCS]

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! :)

[@Woah9394]

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

[@sinq2102]

TNice tutorials is one of the best intro soft softs I've ever seen. The entire basic worksoftow with no B.S.!

[@Bolpat]

Having watched only the first minute, this is what would work for 3 players: Everyone throws a normal 6-sided die. If everyone has a different value, sort by value. If all three have the same value, use a predetermined ordering, e.g., 1 maps to (1, 2, 3), 2 maps to (1, 3, 2), 3 maps to (2, 1, 3), 4 maps to (2 ,3, 1), 5 maps to (3,1,2), and 6 maps to (3, 2, 1); that there are 6 permutations of 3 players comes in quite handy, right? If there's exactly two people with the same value *v* (the other player higher or lower), also sort by value and for the two ones with the same value, if *v* is odd, sort them in clockwise order, if it's even, counterclockwise.

[@MultiUltimater]

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.

[@harriehausenman8623]

I love how one player "corrects" the played card in the last scene! 🤣 Definitely a candidate for some applied group theory 😊

[@movax20h]

It is a great problem, but practically for more 4 or more players, it is better to just use a phone app or a small electronic device that takes care of an order, or do make players take shuffled numbered cards. Still interesting to see it solved with dices,

[@pfeilspitze]

Honestly, I've never seen a game with dice that wouldn't be better (or at least as good) with cards. Catan being my go-to example, since sampling without replacement is so obviously better for it that one of the expansions gives you cards to use instead of the dice.

[@__8120]

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

[@codahighland]

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.

[@Fergguson]

Mathematicians spending weeks making dice instead of making the people who tied just roll again

[@PolylogCS]

You know, after the board game is played sufficiently many times, it starts being worth :D xkcd.com/1205/

[@josephcoon5809]

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.

[@tetronym4549]

4:05 In all 6 of those examples, they contain exactly 3 "sets" where the numbers are "ascending" (as you go from top to bottom, A B C A) and three where they are "descending". (If you loop around after reaching an edge.) Furthermore, any "upwards" arrow has a matching "downwards" arrow, its exact opposite. Well, I say "all 6", except... well, the 6th example has an error. The final column should be "A: 18, B:17, C: 16", but in the video, A has 17 and B has 18. (Note: I paused to make this comment, since I wanted to see if I my intuitions were correct, it's possible that I'm dumb and saw patterns that weren't there)

[@epiclink1012]

It feels like I'm missing something here because this is too obvious a solution for no one to have said it yet. Can't you essentially just look at this as needing to solve the ties? If that is the case, why can't you alternate which die(player) would win the tie, like 1,6,8,10,15,16 , 2,4,9,11,13,17 and 3,5,7,12,14,18 (I know this is almost exactly their solution for 3 players, but hold on) this means that on a tie the wins would go to player 3, then 1, then 2, 3, 1, 2. So each player wins the tie 2 times, meaning its a equal chance of winning the ties. If that works, why wouldn't this work: 1,10,14,18,22,26,35,39,43,47 2,6,15,19,23,27,31,40,44,48 3,7,11,20,24,28,32,36,45,49 4,8,12,16,25,29,33,37,41,50 5,9,13,17,21,30,34,38,42,46 the tie wins go 5,1,2,3,4,5,1,2,3,4 so each player wins 2 ties. What am I doing wrong here that makes this not work, because if it does then you should only need a d10 for 5 players, and a d20 for 10 players, not a d10^60.

[@tarnishedecho]

My first thought to fix the first 2 dice was to add 13 to player A's dice. This would add 6 outcomes where A > B and therefore make the dice fair.

[@Montewtf]

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

[@Jorvalt]

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.

[@Alasius]

Here's another way to solve the order with dice: For 3 players: All permutations of the order of the 3 players A,B,C can be written like this: ABC ACB BAC BCA CAB CBA This allows us to define a look-up table of the 6 orders. Thus we can just throw one d6 and use the result as our index in the lookup table! For 4 players: Our look-up table now has 24 elements! In other words, we can throw 1d6 and two coins ("two d2"), which then can be read together as the index within the look-up table. For example 4-1-2 could be understood as "the fourth order of the first half of the second half" (i.e. the order at position 4+(1-1)*6+(2-1)*12 = 16). We could also solve this with a single d24, or 1d2+1d12, or 1d4+1d6, whatever is to your liking. For 10 players: With 10 players we have 10! permutations. As we have seen before, our dice can be used like a numeral system (that is reading them like digits of a number). By splitting 10! into divisors of itself, we can rewrite it into such a mixed numeral system. 10! = (10*2) * (5*4) * (3*4) * (2*6) * (3*3) * (7) This means, we use 2d20+2d12+2d3+1d7 Ok, technically there can be no dice with 7*k sides in 3 dimensions, but I've seen websites provide any dice up to 23 that are (presumably) fair. Look quite weird. This means we still use less dice than there are players (even less than players-1). Another way to solve the d7 problem (rather than having weirdly shaped dice) is to split the players up into a sub-order. As the players are already ordered (A,B,C,D,E,F,G,H,I,J), we can run ordering like this: Take the first 3 players (A,B,C), let them roll 1d6 on the 3-player look-up table. Repeat with players D,E,F, and G,H,I (J's position will be determined later). Now take the first player of the first sub-order, and roll 1d4. The d4 determines the position relative to the second sub-order. Then throw a die to determine the relative position of the second player of the first sub-order relative to the second sub-order after the first player's relative position. This die is at most a d4. Do the same for the third player. (To explain, here's an example: let's say we get sub-orders A,C,B and F,E,D. Then for A we roll a d4, get 2 -> F,A,E,D. Now there are only 3 possible positions after A within this new sub-order, so we roll a d3, get 3 -> F,A,E,D,C. Thus we only have one reasonable position (1d1) for B -> F,A,E,D,C,B). We now can repeat the same for the third sub-order, starting with the first place of the second sub-order and determine the relative positions within the combined sub-order. The last step is to roll a d10 and this determines the position of the last player. This whole algorithm demands 3d6 to determine the first 3 sub-orders, then up to 9d4, and finally 1d10. In total it's 13 dice, but the die size average is quite low in comparison to the first method (and doesn't require a d7, therefor being realistic). You can even increase this to n players, only for the last one (or two) person(s) you'll need to change up the last step a bit, and the number of dice increases linearly with the number of players.

[@warmpianist]

I was thinking of the "sequential" tossing to determine the order. This might be the same as Jordan Weitz's solution (in pinned comment) that my solution also requires n-1 dice with 2,3,4,...,n sides. player 1 (p1) is fixed p2 tosses a dice of 2 sides: 1 means p1 -> p2 (p1 before p2), 2 means p2 -> p1 (since p2 only has 2 positions to place, either before or after p1) p3 tosses a dice of 3 sides: similarly p3 has 3 positions to place, before everyone, between p1 and p2, after everyone And we do this similarly to other players. In reality we can toss the dice at the same time, but just that you cannot directly say which player is before or after, just by looking at the 2 distinct dice. For example, p3 gets a 3 and p1000000 gets a 4: You can't directly say that p1000000 will be before or after p3 without looking at what p4, p5, ..., p999999 gets. In this case I still think that looking at the sequence of string is the most appropriate.

[@PolylogCS]

Very nice! I think it is the same as Jordan Weitz's solution in that you both simulate the process "put the player names in a hat and then choose from it the names one by one, randomly". The difference between the two solutions sounds to me a lot like the difference between the insertsort and selectsort. :)

[@Deeznuts-gd6lm]

🤓

[@jelleswaanen4089]

I feel like the solutions could be shortened by using super permutations somehow, but I haven’t yet found out how.

[@thegiftedspriter7427]

Cool proof, though it would have been nice if there were a constructor for the fair dice with the lowest number of sides for any given number of players.

[@stechuskaktus8318]

Well we do have an upper bound now. As well as a lower bound, as the number of possible combinations must be divisible by the factorial of the number of players. The optimal number must be somewhere between these.

[@austinconner2479]

Heres a general solution which doesn't produce as large of solutions (but still large). First, generalize to the case where the number of die faces for each player is not required to be the same (one can pass back to the equal number of faces case if desired by duplicating faces in runs, giving lcm(all faces) faces for each player). For example, in the 2 player case, fair dice have faces [1,3] and [2]. This can be duplicated to the lcm = 2 number of faces for all to get say [1,4] and [2,3]. Now, say we have a solution (in string form, per video) for n-1 players string S. Then there is a solution for n players, where the nth player is called X, of the form X^(d_1) S X^(d_2) S ... S X^(d_n), where d_1...d_n are numbers to be chosen. The property of all orderings being equally likely gives a linear system on the probabilities p_k = d_k / sum_i d_i, which can be solved to obtain a string. For instance, with 4 players, there are a set of dice with 6,12,18, and 8 faces giving a solution: [[3, 10, 18, 25, 33, 40], [2, 4, 9, 11, 17, 19, 24, 26, 32, 34, 39, 41], [1, 5, 6, 7, 8, 12, 16, 20, 21, 22, 23, 27, 31, 35, 36, 37, 38, 42], [0, 13, 14, 15, 28, 29, 30, 43]]. Duplicating faces to obtain equal size dice as above, these correspond to 72 sided dice. For 5 players, we can do this with dice with [24, 48, 72, 32, 90] faces (or all 1440 sides). For 6, dice sized [120, 240, 360, 160, 450, 288] or all 7200.

[@PolylogCS]

Perhaps you know it, but Erik and his collaborators constructed some small fair dice this way. I think this is an absolutely amazing construction, however, I don't know how to prove that it works for any n. The way I understand the construction leads to so-called Cotes numbers that are sometimes negative for something like n>=7. If you know how you can make it work for all n, totally let us know, I think this is a very interesting question. We focused on the theoretical existence question in our video because we find it cute (and because otherwise the video would be about what Erik and his collaborators did :) ).

[@nishchaymanwani36]

@@PolylogCS Yup this is an amazing construction. I noticed the negative cotesian numbers after n=7, but I am thinking whether we can have some other number of X repeats = R >= n (so new string looks like X^(d_1) S X^(d_2) S ... S X^(d_R)) such that we can have all non-negative values of d_i. I implemented gaussian elimination method to calculate for R=N case, but now I have to implement simplex for R>N cases 😔. I think there is a high chance that we might able to atleast one R where it works every time, but yea no formal proof

[@PolylogCS]

@@nishchaymanwani36 I was thinking a bit about the following approach: Let's say that a sequence of numbers is k-nice if you can carry out Erik's construction going from k-1 to k using this sequence. E.g., 1,4,1 is 3-nice. Is there some operation that you can do to a k-nice sequence such that it stays k-nice? (or combine two k-nice sequences to get another one etc.) If there were some operation like this, perhaps it could give us enough flexibility to construct a k-nice sequence with positive numbers. What could help is that I think the size of cotes numbers can be understood quite well asymptotically - I think that if you look at the numbers i and i+1 in the n-th row of the triangle of cotes numbers and divide them, you get asymptotically some very simple fraction like -(i+1)/i or something like that (not exactly this fraction but something similar)

[@austinconner2479]

​@@PolylogCS You are right I overlooked this. After a great deal of thought I found an argument showing that Nishchay's proposal will always work, making use of your (Erik's?) observation that we should be considering Cotes numbers adjacent things. First, my original claim is equivalent to the statement that the uniform distribution on n elements is in the cone spanned by (is a nonnegative combination of) the binomial distributions with probability p_i = i/(n-1), for i = 0..n-1. As you point out, this claim is false, e.g. when n=9. The modified claim of Nishchay (which I will prove) is that this is true when the second n is replaced by some R, and the combination can be chosen to be over the rationals (this was immediate before but no longer). It suffices to show that the uniform distribution lies in the interior of the convex cone over all binomial distributions (algebraically, the uniform distribution is a finite linear combination of n binomial distributions with positive coefficients): if the uniform distribution is in the interior of the simplex spanned by n binomial distributions, it will also be if we perturb those distributions a small amount. In particular, we may perturb the distributions to have rational probabilities. In this case, the positive weights attached to them (being a solution to a linear system with rational coefficients) will be rational. Taking common denominators of probabilities gives us R, and as before clearing denominators of the weights give us the d_i. Okay, why is the uniform distribution in the cone over the binomial distributions? Now we use the ideas of interpolation and integral approximation. Claim: We may choose probabilities p_i and weights w_i > 0, 1

[@austinconner2479]

By the way, for n=4, R can be chosen to be 3, and we get a smaller set of dice of sizes 4, 8, 12, and 6, which can be actually implemented with platonic solids :) [[4, 8, 14, 18], [3, 5, 7, 9, 13, 15, 17, 19], [2, 6, 6, 6, 6, 10, 12, 16, 16, 16, 16, 20], [1, 11, 11, 11, 11, 21]]

[@RationallyChallenged]

I believe the solution for 2 players is actually solved by a coin flip, not “heads vs tails” but rather a 2 sided “die” P1: 1,4 P2: 2,3 Sure, the outcome is determined by P1’s roll/flip, but cool to ponder the minimization of the die vs die roll

[@rccookie6202]

You can solve this problem recursively: 1 player - trivial. n+1-th player: gets a die with n+1 sides. N of these sides have a value smaller than the values on all other dice, and one side has a value greater than all. You can now scale the number of sides on all dice to the smallest common multiple of 1..(n+1) if each dice should have the same number of sides.

[@rccookie6202]

Should be noted, with this approach not all players have the same chance of being the n-th player. For example, the last player can only ever be first or last. But the average position is fair

[@deadall127]

The solution to the original problem is very easy for this 3 player case: 1) one player (which one doesn't matter) rolls a die, divide the result by 2 and round to the lowest value, you get the player order (1, 2 or 3) 2) a different player (again, the actual one doesn't matter) rolls another die, divide the result by 3 and round to the lowest value, you get the order within the remaining orders that have not been taken in step 1 3) last player takes the last remaining order And this technique can easily be generalized for 2 and 4 players, the idea is always to emulate a n-sided die (the highest n being the amount of player) using one (or many) 6-sided die tho it would be easier to just use the actual n-sided die, n is limited to the amount of players anyway it won't be very big.

[@pwnmeisterage]

Remember that there is another constraint on physical dice. They must have an isohedral geometry where every pair of opposite faces is parallel. So that you can read the "top" face while the "bottom" face rests flat. If they have some other shape then they won't rest flat and/or you won't know which face displays the roll result.

[@Kaepsele337]

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.

[@toasteduranium]

Given players a, b, and c, if you counted up starting from 1 and giving each number of the sequence to a new player, I think the following process may work: Give to A, then B, then C. C has the highest here. Give to B, then C, then A. A has the highest here. Give to C, then A, then B. B has the highest here. If you repeated this switching of the order of assignments, for any group of people with dice that have a number of sides equal to a multiple of the square of the number of players, would you always have a fair set of assignments? With three-sides dice, assigned numbers as previously described, they are “fair” in the sense the video uses. The same result would occur with 6-sided dice. Edit: I just realized that the first solution at 4:07 is exactly what I’ve just described. Edit: I just realized that 7:30 almost exactly described my solution