2

Some days ago i was playing "Settlers of Catan", an homemade version. In this game there is an event where a players pick, randomly, a card from another player. So here is the problem: can we use the dice (six faces) to pick the card randomly?

Until the opposite player has less than seven cards, there are no problems. Even with an even number of cards there is no problem since we can split the set of cards in several rows (up to six 1) of same length. For example 16 cards will be split in four rows with four cards each, then we throw the dice once to pick a row, and then again to pick a card (of course if the dice shows five, we must throw again the dice). All of these cards have the same probability to be picked, but there are issues with an odd number of cards.

For example seven. We do two rows, one with three and the other with four cards. These cards don't have the same probability.

I thought about it for a while but i didn't see any solution (involving: the disposition of the cards, a dice of six faces and only simple maths [no calculators] such as modulo and so on), but i know that there are here people way more skilled than me.

Then, can someone tell me if the problem is solvable? Thanks a lot in advance.

PS: sorry for syntax mistakes, i know that i should improve my english. PPS: my "pratical" solution is - pick a dice with 20 faces to solve almost all real scenarios, but is not a mathematical solution.

1 assuming that the maximum number of cards in the hands of a player is 36.

edit: sorry for bouncing the "answer chosen" but i was unsure ^_^

edit2: i just acquired the "vote up" privilege, so i grant i vote and i can delete my "thanks/whoa" comments as the guide suggest.

Community
  • 1
Pier A
  • 45

3 Answers3

1

Do you have a coin? If so, flip the coin, along with the dice, and this takes care of up to 12 cards.

Even simpler, assign each card a number from 1 to $2^N$. (where $2^N$ is more than the number of cards you have). Flip the coin $N$ times and convert that into binary. If it doesn't correspond to a card, flip again.

As dtldarek suggests (even if we do not have a coin), we can just roll the dice and let $1, 2, 3$ correspond to a '1' in binary, and $4, 5, 6$ correspond to a '0' in binary. In fact, this allows us to reach any number of the form $2^a 3^b$, where $a, b$ are non-negative integers.

Calvin Lin
  • 68,864
  • @PierfrancescoPierQRAiello Of course you could use a dice and convert that into hexadecimal. Binary tends to allow you to have fewer unassigned numbers', though you will need more flips. – Calvin Lin Jan 08 '13 at 20:43
  • yes, i already think about it after your answer. Thanks! – Pier A Jan 08 '13 at 20:54
  • You don't need a coin. Throw dice twice and interpret the first throw as even/odd or $\leq 3$/$>3$. – dtldarek Jan 08 '13 at 21:05
  • @dtldarek maybe i didn't get your point sorry.

    if i understand you said: first throw choose if we consider only the odd or even cards [given seven cards]. Is it right?

    If yes, then is the same of splitting seven cards in two rows, one with three and the other with four cards.

     – Pier A Jan 08 '13 at 21:14
1

My comment was unclear, so here I am more verbose. Let $n$ be the number of cards to pick from.

If $n \leq 6$ throw one die and if the result is greater than $n$, throw again. The expected number of throws is $\frac{6}{n}$.

If $6 < n \leq 12$ take two dice. Let $(a,b)$ be the result of the throw, then set $r = 6\cdot(a \bmod 2) + b$. Then $r$ is uniformly distributed on ${1,\ldots,12}$. Rethrow if $r$ is greater than $n$ (the expected number of throws is again constant).

If $12 < n \leq 18$ take two dice and set $r = 6\cdot(a \bmod 3) + b$. Continue as before.

If $6k < n \leq 6(k+1)$ for $k \in {3,4,5}$. Throw first die until you will have $a \leq k$. Then throw second die. Repeat all if $r = 6(a \bmod k) + b$ is greater than $n$. (Here $r = 6(a-1) + b$ is also fine.)

If $6^k < n \leq 6^{k+1}$ take $(k+1)$ dice (in fact take $\lfloor \log_6(n-1)\rfloor$ dice) and follow in similar fashion ;-)

If anything is still unclear, just ask. Cheers!

EDIT:

I see that you are still unconvinced and even calculating the probability had not been enough (yet I hope that we agree that $P(r = i) = 1/12$). Maybe a small experiment would be better for you? Go to try ruby and type in the following code snippet (you can skip the comments, i.e. the text after $\#$s):

def roll(n)
  r = Random.rand(1..12)          # Throw the die for the first time
  while r > n                     # If the result is not right,
    r = Random.rand(1..12)        # repeat.
  end
  r                               # Return the result when done.
end

throws = Hash.new(0)
7000.times do throws[roll(7)] += 1 end   
print throws
dtldarek
  • 37,381
  • Ok after a night i must review my position. Even if your answer seems beautiful to me doesn't solve the problem.

    In fact your method it's equal to a particular arrangement of cards with the method exposed in the question. For example, with 7 cards (so in the case $ 6 < n \le 12 $), we have: one row with six cards and one with only one (instead of one row with three cards and the other with four).

    But in this manner it's true that all twelve position has the same probability, but these aren't all covered! So kicks in a truncated probability!

     – Pier A Jan 09 '13 at 07:45
  • In the example written above the positions from one to six have a probability of $ \frac{1}{6} \cdot \frac{1}{2} $ while the seventh position has $ 1 \cdot \frac{1}{2} $ , since we don't consider others positions. Then there isn't an equal probability for each card.

    If i'm wrong, please tell me where. Thanks in advance!

     – Pier A Jan 09 '13 at 07:49
  • @PierfrancescoPierQRAiello In case of $6 < n \leq 12$ cards, for all $i \in {1,\ldots,12}$ we have $P(r = i) = 1/12$. I have never said anything about splitting cards in rows and your interpretation "since we don't consider others positions" is against my intentions. You treat $r$ as you would have a 12-sided die and just "rethrow" (i.e. throw all considered dice and calculate new $r$) if $r > n$. The process stops when $r \leq n$, there is no "truncated probability" because the output of the process is never $r > n$ (because otherwise the process would not have stopped). – dtldarek Jan 09 '13 at 08:45
  • i'm thinking about it (i'm unsure), thanks again. – Pier A Jan 09 '13 at 08:49
  • 2
    @PierfrancescoPierQRAiello In case of $n = 7$, first (in fact any) card has probability $$P(r_1 = 1) + P(r_1 > 7)P(r_2 = 1) + P(r_1 > 7)P(r_2 > 7)P(r_3 = 1) + \ldots = $$ $$\frac{1}{12} + \frac{5}{12}\frac{1}{12} + \frac{5}{12}\frac{5}{12}\frac{1}{12} + \ldots = \frac{1}{12}\frac{1}{1-\frac{5}{12}} = \frac{1}{7}.$$ So you see, the rest of probability $7 < r \leq 12$ is redistributed again in the rethrow and if that doesn't succeed, then again and again (theoretically this process could last arbitrarily long, but you can imagine that probability of such event is very, very, very small). – dtldarek Jan 09 '13 at 08:52
  • @PierfrancescoPierQRAiello If you are still unsure, see the last edit. – dtldarek Jan 09 '13 at 09:23
  • Ok, your explanation is quite clear. So why am i stuck with the following thought (as above, i pick the example with 7 cards)? With your method the first roll choose the first six sides or the latter six sides of the 12-sided dice with probability of 1/2, right? If yes, then we roll again to choose one of the six sides previously chosen. Each side has, then, 1/12 of prob. , this is ok for me; but if i consider the condition of "usefull throw" i have: $ P(a \mod 2 = 0)P(b \in 1,...,6 | b \ \text{can be} \in 1,...,6 ) = 1/12 $ and $ P(a \mod 2 = 1)P(b = 7 | b \in {7} ) $ no ok it's 1/12 too. – Pier A Jan 09 '13 at 09:32
  • Right! I was stuck because if r>7 then i would reroll the dice only to choose again from 7 to 12 , and this doesn't work!

    This shrewdness will work even with the method exposed in the question (split cards in different rows).

     – Pier A Jan 09 '13 at 09:48
  • @PierfrancescoPierQRAiello Be aware that splitting cards into rows of different size (as in case of $n = 7$) is usually bad idea. If you want uniform distribution, treat your objects uniformly. Finally, if you are interested in that kind of stuff, there is a nice puzzle: how to produce one random bit (e.g. result of unbiased coin throw) with only a biased coin? – dtldarek Jan 09 '13 at 10:00
  • Why is splitting a bad idea? Using your concept of "repeat the whole process to model a bigger dice":
    given two rows, first with three and the second with four cards, then do a first roll to pick a row and then reroll to pick a card. If the second roll shows a number that is greater than the number of cards in the row, repeat the whole process. So each card has 1/12 of prob, while if i repeat only the second roll (to pick the card in the row) i'll loss the equal probability.     – Pier A Jan 09 '13 at 10:26
  • @PierfrancescoPierQRAiello Ok, I didn't understand what you wanted to do. You are right, it will work, the important thing is to repeat the whole process if if the current try "failed" (that is rethrow all the dice). – dtldarek Jan 09 '13 at 10:45
  • Yep, the "whole process" is the key that i missed in your earlier posts. Is a powerful shrewdness. About your biased coin problem, i'll think about it another time :) . – Pier A Jan 09 '13 at 10:51
0

You can select every 6 subset of cards, so if you have 7 cards, you have 6 possible subsets, then go through this six subsets and throw a dice, give a point to the card that the number or the dice tells you... at the end, the card with most points win. If you repeat the process, every card has the same possibilities.

MyUserIsThis
  • 3,702
  • 1
  • 24
  • 39
  • Nice! Anyway it seems to solve the problem with 7 cards, but with others odds numbers? 9,11,and so on?

    If i apply the same idea, that is: pick each 6-elements subset of 9 cards, there are $ \binom{9}{6} $ possible subsets (IIRC), that is quite a lot.

     – Pier A Jan 08 '13 at 20:37
  • Yes, it's a lot. It works for every number greater than 6, but it gets big really soon, as you've seen. – MyUserIsThis Jan 08 '13 at 20:47