3
$\begingroup$

The Problem There's a bag with six distinct tokens in it (e.g. a six-sided die). Each token has an unknown value of some real number. A "trial" consists of drawing five tokens (five die rolls) and being told the sum (to clarify, you do know the identifier for each token, just not its value).

What's the expected number of trials to be able to determine the values of all six tokens?

Algebraic representation There are six unknowns $x_1, x_2, ..., x_6$. Each trial gives you an equation of the form $x_{d_1} + x_{d_2} + x_{d_3} + x_{d_4} + x_{d_5} = r$, where each of the $d_i$s are chosen randomly (independently, each with 1/6 probability) from $\{1,2,3,4,5,6\}$.

The logical way to solve it is to convert each trial into a linear equation of the form $$n_{1,i}x_1+n_{2,i}x_2+n_{3,i}x_3+n_{4,i}x_4+n_{5,i}x_5+n_{6,i}x_6=r_i$$ and then consider the resulting system of linear equations. In many (probably most) cases, six trials will suffice. But it's possible to get the same combination of dice more than once (either exactly or as a permutation), causing the six equations to not be linearly independent, which would necessitate another trial. And it's also possible for the latest trial to produce an equation that's a linear combination of some of the previous equations. (e.g. if $x_1+x_1+x_2+x_2+x_3=r_1$ and $x_3+x_4+x_4+x_5+x_5=r_2$ then $x_1+x_2+x_3+x_4+x_5=(r_1+r_2)/2$)

So the problem becomes, how many trials are necessary to get 6 linearly independent equations?

My attempts I thought I'd solve it by building it up one trial at a time, considering the probability that the next trial will produce a linearly independent equation. Then I can find the expected number of trials to get to 2, then expected number of trials to get to 3, etc. However I didn't know how to proceed. I thought I'd consider things casewise the cases where the first trial has no repeats / one pair / two pair / one triple / one four-of-a-kind / two pair / a pair and a triple, but that quickly becomes unfeasible.

$\endgroup$
  • $\begingroup$ It's sort of a variation of the coupon collector's problem, but instead of n coupons, there are not-quite-arbitrary vectors in an n-dimensional vector space. $\endgroup$ – Snowbody Jun 30 '14 at 14:27
0
$\begingroup$

There are 6^5=7776 different possible dice rolls.

  1. The first dice roll may have:
    • No multiples: 720 of 7776, 5!=120 permutations of each of 6
    • one pair: 3600 of 7776, 5!/2!=60 permutations of each of 60
    • one triple: 1200 of 7776, 5!/3!=20 permutations of each of 60
    • one four-of-a-kind: 150 of 7776, 5 permutations of each of 30
    • two pair: 1800 of 7776, 5!/2!/2! = 30 permutations of each of 60
    • one five-of-a-kind: 6 of 7776
    • a pair and a triple (full house): 300 of 7776, 5!/2!/3! = 10 permutations of each of 30
  2. On the second dice roll, the only way to get something linearly dependent is to have something exactly the same as last one, or a permutation of it.
    • No multiples: 720*120/6^10
    • one pair: 3600*60/6^10
    • one triple: 1200*20/6^10
    • one four-of-a-kind: 150*5/6^10
    • two pair: 1800*30/6^10
    • five-of-a-kind: 6 / 6^10
    • full house: 300*10/6^10

Total chance of the second roll being useless: 384156 / 6^10, around 0.635%.

However, after that the possibilities explode and this method is not really feasible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.