[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

[Guest]

I hate to say this, unreality, but not everything has to be a puzzel. you can always go online and get virtual x sided dice. There probably *is* a solution, the easiest but longest is if you just have a bunch of integers be a 'reroll' sequence.

[unreality]

I hate to say this, unreality, but not everything has to be a puzzel. you can always go online and get virtual x sided dice. There probably *is* a solution, the easiest but longest is if you just have a bunch of integers be a 'reroll' sequence.

"Say, for the purposes of this riddle, the only randomizing device we have is a 20-sided die."

Most riddles and puzzles on here obviously would not occur in real life. If you can't/don't/won't solve theoretical problems, there's no reason to post on here saying that you don't like it. Just giving you a heads up- you'll find 99% of the riddles on this site are theoretical problems that, in real life, may have easier methods of solving. Now if I hadn't said the sentence I put in quotes, using the internet or a program might be an acceptable solution, but say you are somewhere not near a computer and all you have is a 20-sided dice

I should also mention that I have a few vague solutions in mind (haven't gotten really cracking yet), but I don't know the best/only/ifitexists solution either, I guess this is like a group effort thing

Edited August 14, 2008 by unreality

[unreality]

right now I'm thinking...

That it's not possible, other than a max of infinity. One of my plans:

Roll until you get a value from 1-7. Then roll again. 1-6 = add 0. 7-12 = add 7. 8-18 = add 14. 19-20 = reroll.

The minimum is 2, however maximum would be infinity

I'm thinking that we should look at the MINIMUM instead of the MAXIMUM

edit: or chances of getting the minimum or whatever. To maximize that, for the first roll, values 1-7 are the value, 8-14 should subtract 7, and then 15-20 means reroll. Thus the chances for using only 2 rolls are (14/20)*(18/20) = 252/400

I know it can't be done with 1 roll, so can you get a minimum of 2 roll-value which has better chances than 252/400 for taking up 2 rolls?

Edited August 14, 2008 by unreality

[Guest]

Number the people 1-21. Roll the dice, and if it comes up 19 or 20 reroll. If it is 1-6, throw out players 8-21; if it is 7-12, throw out players 1-7 and 15-21; it is is 13-18, throw out players 1-14.

You're now left with 7 players. Roll again, reroll on 15-20. If it comes up 1 or 2, choose player 1; 3 or 4, choose player 2; etc.

This solution has no maximum number of rolls, but the expected number is reasonably low. Among other things, the probability of the "roll value" being 2 is 18/20*14/20=.63, which is pretty good I think.

I'm sure improvements could be made though.

[unreality]

wow you did the same exact thing I did... lol ;D

edit: looks like I copied you now lol since I edited 2 mins after you posted, but I never saw that you posted... we must've both came up with the same answer

Edited August 14, 2008 by unreality

[Guest]

One way that would work in two rolls 399 out of 400 times is as follows:

Roll twice. Then multiply the result of the first roll by 20 and add the result of the second roll. You end up with a number from 21-420. Then you can say

21-39 = player 1

40-58 = player 2

...

382-400 = player 20

401-419 = player 21

If it both land on 20 for a total of 420, you're out of luck and have to repeat.

[unreality]

One way that would work in two rolls 399 out of 400 times is as follows:

Roll twice. Then multiply the result of the first roll by 20 and add the result of the second roll. You end up with a number from 21-420. Then you can say

21-39 = player 1

40-58 = player 2

...

382-400 = player 20

401-419 = player 21

If it both land on 20 for a total of 420, you're out of luck and have to repeat.

wow... awesome! Two rolls 399/400 times!

Edited August 14, 2008 by unreality

[Guest]

Kill off one character and roll the d20. :-)

You have an odd number, so you can't be totally fair with an even number randomizer. Roll the die once to determine your starting point. Say you roll a 10, char number 10 is now your start and becomes number 1. Then roll the die again to land on your target character. Character 21 has a disadvantage as they can never be in a position to be "protected". But its fast and spreads the risk a bit.

[unreality]

Kill off one character and roll the d20. :-)

then it's 20 people of 1/20 and then someone with 0 ;D

You have an odd number, so you can't be totally fair with an even number randomizer. Roll the die once to determine your starting point. Say you roll a 10, char number 10 is now your start and becomes number 1. Then roll the die again to land on your target character. Character 21 has a disadvantage as they can never be in a position to be "protected". But its fast and spreads the risk a bit.

I didn't look into it, but something tells me the odds here are not fair and equal, and it would take a few roles to get the number- what if you roll over?

[Guest]

Roll the dice twice. If the same number comes up the same both times, chose #21, other wise go with the first rolled number. This creates a total of 21 possiblities with the two rolls: 1-20 on the first roll and and #21 on the second roll.

[phaze]

In a set 21 rolls (no possiblity of endless rolls) and fair

**WARNING psuedo code follows look away now if you dont want to be turned to stone ***

set the initail result to 0

For 21 times do the following (has to be 21 times as 20 does not have the factors 7 or 3)

Multiply result by 20

Roll the die

Add the value to the result

When finished take the modulas of the result with 21

[unreality]

Roll the dice twice. If the same number comes up the same both times, chose #21, other wise go with the first rolled number. This creates a total of 21 possiblities with the two rolls: 1-20 on the first roll and and #21 on the second roll.

the chances of getting 21 are 1/20 or 20/400. Each of the other 20 numbers are 19/400, or 1/400 less than 21. All of the numbers must have a 1/21 chance of being picked

[Guest]

Am I wrong, or do you have to worry about multi-die probabilities if you try to add (or multiply) the totals of your dice together (adding, 2 can only be rolled with a 1-1, 3 can be rolled with 1-2, or 2-1 etc.) I would think to be fair you have to take action on every roll (unless it's a re-roll). I like Chuck Rampart's solution.

[unreality]

Cracked Corn: yeah so far I thought the best bet was mine and Chuck Rampart's solution (both the same thing basically, we just worded em differently), until iBrendan came along

In a set 21 rolls (no possiblity of endless rolls) and fair

**WARNING psuedo code follows look away now if you dont want to be turned to stone ***

set the initail result to 0

For 21 times do the following (has to be 21 times as 20 does not have the factors 7 or 3)

Multiply result by 20

Roll the die

Add the value to the result

When finished take the modulas of the result with 21

can you demonstrate how this fair and gives each number a 1/21 chance? I'm not seeing the reasoning behind it, as Cracked Corn said 10 and 11 are weighted with most, then go outwards, etc, though that may not apply in your solution's case, I'm not sure

[phaze]

can you demonstrate how this fair and gives each number a 1/21 chance? I'm not seeing the reasoning behind it, as Cracked Corn said 10 and 11 are weighted with most, then go outwards, etc, though that may not apply in your solution's case, I'm not sure

I just relised it wont work. 20 to the power of 21 is not divisible by 21

I was not a case of 10 and 11 being weighted higher as there is no overlap

[phaze]

I am not sure if this is possible. The more rolls of the die however the fairer is is going to be

[unreality]

check out iBrendan's solution:

One way that would work in two rolls 399 out of 400 times is as follows:

Roll twice. Then multiply the result of the first roll by 20 and add the result of the second roll. You end up with a number from 21-420. Then you can say

21-39 = player 1

40-58 = player 2

...

382-400 = player 20

401-419 = player 21

If it both land on 20 for a total of 420, you're out of luck and have to repeat.

unfortunately I'm thinking that it may not be evenly distributed. I'll test out the combinations: (order of dice matter, first is multiplied by 20 and added to second)

21 = 1,1 = 1/400

22 = 1,2 = 1/400

39 = 1,19 = 1/400

40 = 1,20 = 1/400

41 = 2,1 (can't be 1,21) ... omg! This works perfectly! iBrendan is a genuis!!!

245 = 12,5 (nothing else)

wow! Nice work iBrendan- I was pretty sure yours was the best before, but now that we know it's fair- nice! ;D

edit for phaze: iBrendan's solution is fair (1/21 for each number) and works with only 2 rolls 399/400 of the time. In the 1/400 case, it would take 4 rolls... 1/160000 chance that it would take 6 rolls... etc. But it's highly likely to take only 2 rolls

Edited August 15, 2008 by unreality

[Guest]

Roll the 20 sided dice 21 times and sum up all the rolls.

Divide the total by 21 and take the remainder of the division. This will give you a value between 0 and 20 inclusive.

Add one to that to give you a value between 1 to 21 inclusive.

[unreality]

Shrawn: no, that value is weighted, distributed unevenly

btw, I was thinking about general cases, and found two general solutions, inversely efficient of each other depending on the dice you have

call the number of sides on your dice 'n', the number of people 'z', and the dice rolls n1, n2, nx, etc

Solution One:

in this form of it, it only works if n+1 = z (as in 20 and 21 like this problem) but I bet it could be molded to other scenarios (ie, n+2 or n+3 or n*2 is z) with some fiddling. iBrendan came up with this basically:

(n1 * n) + n2, which gives you a range of (n-1)*z + 1 numbers which can be clumped into groups of n-1, of which there are z (to pick a player evenly), with 1 "reroll number" left over. The chance of getting the reroll number is 1/(n*n), thus this solution becomes more efficient as n gets bigger

Solution Two:

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

[phaze]

Roll the 20 sided dice 21 times and sum up all the rolls.

Divide the total by 21 and take the remainder of the division. This will give you a value between 0 and 20 inclusive.

Add one to that to give you a value between 1 to 21 inclusive.

Although this was very similar to my answer. The dice will still have a "overlap"

The chance of getting 210 is high the chance of getting 420 or 21 are low.

When you do the modulas does it return an even distribution over the 21 numbers?

This might be possible if high percentage values are paired with low possiblity values

[Guest]

Although this was very similar to my answer. The dice will still have a "overlap"

The chance of getting 210 is high the chance of getting 420 or 21 are low.

When you do the modulas does it return an even distribution over the 21 numbers?

This might be possible if high percentage values are paired with low possiblity values

Make a 6x6 grid, and fill with player characters, and roll 2x6 sided dices. and look up the grid This works up to 36 people. If there is noone in the spot reroll!

Edited August 15, 2008 by taliesin

[unreality]

taliesin: good, except this has a 16/36 or 4/9 reroll chance though- almost one half reroll chance!

Check out my post #20 for an in-depth analysis lol

[Guest]

taliesin: good, except this has a 16/36 or 4/9 reroll chance though- almost one half reroll chance!

Check out my post #20 for an in-depth analysis lol

If you took your 20 sided dice and roll it, diving the rusult by 4 and round down to the nerest whole number. Doingthis twice you can get a even distrubution (using my grid idea) before and you have a 21/25 chance of not having to reroll ..

Edited August 15, 2008 by taliesin

[unreality]

do Solution One from my post #20 and you only have a 1/400 chance of rerolling ;D hehe

though your idea is cool- basically 0-4 and 0-4 on either side of a 5x5 grid as coordinates for one number within 25. 4 would be rerolls, yeah. Nice answer (and fair), but as of yet Solution One appears to be best for n=20 z=21 (again, see post 20) unless we can find a Solution Three that has reroll at even lower than 1/400

since Solution One and Two (from post 20) are both good and have (usually, with varying reroll chances) of only 2 rolls, I think 2 rolls can be our expected desired number of rolls, what it comes down to now is what is the best Solution to use under different n and z values. Solution One has a 1/(n*n) reroll value and Solution Two has a (1/p)((M-z)/n) chance or reroll, so it of course depends all on n and z. But if we can find more solutions that work better with other/more values, that would be cool

[phaze]

Looks like a lot of good thinking is going into this

At the moment it looks like BB has the best method

Is it possible to do the same thing with even less chance of re-roll?

Another advantage with BBs method it requires only two rolls