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

Question

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.

Answer 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

Answer 2

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.

Answer 3

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.