[unreality]

This is a problem I thought of while determining the identity of a 'Tiebreaker' character for Mafia VI. I have a 20-sided dice, which picks a number randomly between 1 and 20, but there are 21 players in Mafia VI. Say, for the purposes of this riddle, the only randomizing device we have is a 20-sided die.

My first thought was to role the dice for the values 1-20, then again for values 2-21 (ie, add 1 to the dice roll), then roll again, and if odd pick the first one and if even pick the second. However, on quick inspection, this is not a fair solution. It gives 1 in 40 chances to the players 1 & 21 but 1/20 to the 19 players in between.

Can you find a fair solution? Better yet, a fair solution that minimizes the number of rolls? For example, if my faulty solution had been fair, it takes 3 rolls at most, or 2 rolls if the first two numbers were the same regardless (ie, you rolled 8 and then rolled 7). The probability of it taking 2 rolls instead of 3 is (19/20)(1/20) = 19/400 (all numbers except 1 have a number one less, which that number as a 5% chance of occurring), but that doesn't matter. What matters is the maximum your method would take to get a fair solution (which is one person, you can't have multiple Tiebreakers). A fair solution is where each person has a 1/21 chances of getting picked. If my first solution had been fair, it's "roll-value" would be 3 since it would take 3 rolls at most to select someone fairly

An extreme, but working, solution, is to roll the dice 21 times, once for each player, and whoever has the highest number wins. For ties, take just the tying players and then roll once for each of them, etc. The roll value for this is infinity (since you can't be sure of ever not having a tie). Of course there must be a better solution than this.... is there?

That's your job- find a fair solution using the 20 sided die that has the smallest roll-value

[unreality]

yeah, 2 seems to be the desired. Oh and it was iBrendan not Brandonb ;D

yeah iB's solution is essentially the n=20 z=21 case of Solution One on post 20, which works only in special cases. I personally like Solution Two (the one I came up with) cuz it's more versatile and z doesn't have to be n+1.

For the case of n20 z21, I think s_One is the best solution method with 2 rolls and 1/400 chance of reroll, though there might be a better one (I doubt it)

Now I'm trying to think of n & z values where the reroll chance is the same for Solution One and Solution Two

[Guest]

ib's method could be done without multiplying by 20.. just add the two numbers, if greather than than 20 subtract 21, ( 0 is the first person , 1 second ...)

and if 20-1 is rolled reroll!

Edited August 15, 2008 by taliesin

[unreality]

nope, it can't. Adding the two numbers results in a weighted distribution. You need to multiply to clear the ranges for the next number to be added. It's like the first rolls determines 20, 40, etc, and the second roll adds to that, thus there is no weighted distribution.

[Guest]

iB's solution basically works by increasing the sample space you have to work with without weighting the distribution. Then, once you have the new space, you can divide it into any number of equal sections, with the remainder being a failed result.

For example, consider your die to be indexed from 0 (0 - 19). Then iB's solution looks just like picking two random numbers, and using them as the ones and twenties places in a base-20 counting system! Convert it to decimal if you like, and you have a totally random selection.

Error chance for n sided die, z choices: (n^2 mod z) / n^2

Another note: iB's solution can be improved upon in its worst-case scenario by rolling again and adding the new number multiplied by 400. Then you can repeat a similar process.

[unreality]

Error chance for n sided die, z choices: (n^2 mod z) / n^2

how did you get this? If you're talking about what I call "Solution One" (see post 20 of this topic), z is always n+1 and the chance of reroll is 1/(n^2). Your (n^2 mod z) / (n^2) would be 20/400 = 1/20 which is not correct, 1/400 is. Maybe you meant z mod n^2- which in this case for z = n+1 would always be 1, and thus it's just 1/(n*n) as I said in post 20

Edited August 15, 2008 by unreality

[Guest]

Wow lot's of discussion going on about this...

iB's solution basically works by increasing the sample space you have to work with without weighting the distribution. Then, once you have the new space, you can divide it into any number of equal sections, with the remainder being a failed result.

For example, consider your die to be indexed from 0 (0 - 19). Then iB's solution looks just like picking two random numbers, and using them as the ones and twenties places in a base-20 counting system! Convert it to decimal if you like, and you have a totally random selection.

Yep that was pretty much my thinking process... I actually first thought of the "try for a number from 1-14, then try for a number from 1-18" solution, but this that was already posted a couple times so I had to try to improve upon it.

Another note: iB's solution can be improved upon in its worst-case scenario by rolling again and adding the new number multiplied by 400. Then you can repeat a similar process.

If you plan from the beginning to use 3 rolls and multiply one of them by 400, then yes you end up with a space of 8000 possibilities instead of 400. That seems better but the remainder of 8000/21 is 20 so it may not really be an improvement? 20/8000 = 1/400

[Guest]

how did you get this? If you're talking about what I call "Solution One" (see post 20 of this topic), z is always n+1 and the chance of reroll is 1/(n^2). Your (n^2 mod z) / (n^2) would be 20/400 = 1/20 which is not correct, 1/400 is. Maybe you meant z mod n^2- which in this case for z = n+1 would always be 1, and thus it's just 1/(n*n) as I said in post 20

(400 mod 21) / 400

Wow lot's of discussion going on about this...

Yep that was pretty much my thinking process... I actually first thought of the "try for a number from 1-14, then try for a number from 1-18" solution, but this that was already posted a couple times so I had to try to improve upon it.

If you plan from the beginning to use 3 rolls and multiply one of them by 400, then yes you end up with a space of 8000 possibilities instead of 400. That seems better but the remainder of 8000/21 is 20 so it may not really be an improvement? 20/8000 = 1/400

Exactly, the point of adding the third one is only in the worst case, where it is unsolvable. When you do that roll, you have another chance to reach a solvable point. By the 4th total roll, you are back to 1/160000, which is the same as unreality's suggestion of redoing the whole thing, but you do have another 1/xx chance in between.

EDIT: Upon further thinking, this is not fair after all. In fact, it is exactly the same as rolling one die again. Scratch my response to iB, he is 100% correct.

Edited August 16, 2008 by itsclueless

[bonanova]

Not the best solution posted, but a different approach.

Two rolls with possibility of re-rolls needed: expected rolls = 2.54.

Roll twice - R1 and R2. Reroll if

• R1 = 19, 20 or
  
• R2 = 15, 16, 17, 18, 19, 20.
  

Multiply R1[mod 3] x R2 [mod 7].

[Guest]

Not the best solution posted, but a different approach.

Two rolls with possibility of re-rolls needed: expected rolls = 2.54.

Roll twice - R1 and R2. Reroll if

• R1 = 19, 20 or
  
• R2 = 15, 16, 17, 18, 19, 20.
  

Multiply R1[mod 3] x R2 [mod 7].

That doesn't give equally weighted answers, and how do you propose number 11 ever gets a win?

[unreality]

clueless: oops yeah I missed the n^2 part

bonanova: so the only way to get prime numbers are when you get 1 and the prime number? As Clueless pointed out, I'm not sure if this is a fair (1/21 each) solution

Also, about Solution One from my post #20, do you think there's any way to rework it so that z doesn't have to be always n+1?

[bonanova]

bn frantically searches for the DELETE POST button,

but after a moment's thought decides not to use it.

[Guest]

This is like random sampling, I will try to figure this out tomorrow because right now I am very sleepy.

[unreality]

bn: hehe Just the other day I was thinking of telling you to check this topic out, thought you might like it- guess not lol

SK: have fun ;D

[unreality]

my Solution Two method from post 20:

I came up with this one. It only works if z <= n*n. First, find M, the multiple of n that is as low as possible while still being higher than z and is also a factor of n multiplied by n. The maximum that M can be is n. Ie, if n is 6, your values of M can be 6 (1n), 12 (2n), 18 (3n) or 36 (6n). You want to pick the lowest one that's still higher than z. Call M/n = p. Ie, if you chose 18 when n=6, p would be 18/6 or 3. The formula is:

* split n into p groups of n/p each. Number the groups 0, 1, 2, ... p-1

* now roll n1 and find what group it falls under, then take that group's number, call that y

* roll n2 and add n*y, call this num

* if num is bigger than z, reroll n2

for example, if n is 6 and z is 10, the best bet is for M to be 12, thus p is 2, so split 6 into 2 groups (1-3 and 4-6). Number those groups 0 and 1. Roll- if you get the first group, roll again and add 0 (6*0). If you get the second group, roll again and add 6 (6*1). 11 and 12 are higher than 10 and thus reroll.

The chances of having to reroll are (1/p)((M-z)/n), and thus are best when p is smaller (which is why you want to choose the M that's lowest, but still has to be above z) and when M-z is closest to n.

For example, if n is 6 and you need to choose from 12 people (z=12), your chances of having to reroll are (1/2)(0/6) or 0, since z is a perfect multiple of n. It works even better when n=z lol.

Anyway, Solution Two is inefficient for the n=20,z=21 problem because the odds of rerolling would be (1/2)((40-21)/20) or (1/2)(19/20) or 19/40

If you don't reroll, this solution always uses up 2 rolls

***

I made a chart for values with a six-sided dice using the method:

n = 6

------

z = 6

reroll chance = 0

z = 7

reroll chance = 5/12

z = 8

reroll chance = 1/3

z = 9

reroll chance = 1/4

z = 10

reroll chance = 1/6

z = 11

reroll chance = 1/12

z = 12

reroll chance = 0

z = 13

reroll chance = 5/18

z = 14

reroll chance = 2/9

z = 15

reroll chance = 1/6

z = 16

reroll chance = 1/9

z = 17

reroll chance = 1/18

z = 18

reroll chance = 0

When the pattern of (1/p)((M-z)/n) emerges, with n staying constant, you really see how the second part of it, ((M-z)/n), repeats cyclically regardless of z since M matches z, it's the first part, (1/p), which makes this actually more efficient when z is high enough over n (multiples of n don't count of course)

anyway, earlier I was looking to connect Solution One with Solution Two, and for cases where z is always 1 plus a multiple of n, and thus M-n+1 (M-5 in case of a six-sided die), the chance of reroll is always (n-1)/M. Ie, 5/12 or 5/18 for six-sided die, 7/16 or 7/24 for 8s die, etc. Just a pattern that caught my eye

using a 20-sided die to select a random person from 399 people can be done with 2 rolls with a 1/400 chance of reroll, however the method is inefficient when z is closely above a multiple of n, but gets more and more efficient when z approaches a multiple of n (as in 399) or becomes a multiple of n (400). Depending on the factors of n, many multiples have a chance of 0 for reroll, though this isn't always the case. For there to be only one roll to determine the addition, you need a multiple which is n times one of its factors, so using the M of 40 for an n of 10 wouldn't work, you would need an M of 50 (and thus the odds for rerolling would drop as approaching the next usable M, or 50)