# Pick a card from a set with the help of a dice

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.

-

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

-
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! – Pierfrancesco PierQR Aiello Jan 9 '13 at 7: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! – Pierfrancesco PierQR Aiello Jan 9 '13 at 7: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 9 '13 at 8:45
i'm thinking about it (i'm unsure), thanks again. – Pierfrancesco PierQR Aiello Jan 9 '13 at 8:49
@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 9 '13 at 8:52

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.

-
@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 8 '13 at 20:43
You don't need a coin. Throw dice twice and interpret the first throw as even/odd or $\leq 3$/$>3$. – dtldarek Jan 8 '13 at 21:05
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. – Pierfrancesco PierQR Aiello Jan 8 '13 at 20:37