wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> 9 jars and 9 labels
        
(Message started by: Kozo Morimoto on Dec 4^th, 2002, 4:17am)

Title: 9 jars and 9 labels
Post by Kozo Morimoto on Dec 4^th, 2002, 4:17am

I have 9 opaque jars/tins of paint each with a different colour paint.

I also have 9 labels with the colour written on it.

Without opening the jars/tins, I place the labels on the jars/tins.

What's the expected number of labels that I would have correctly placed?

My guess is 1 from looking at n=3 and n=4, but I don't know how I need to go about finding a solution to this problem.

Title: Re: help needed: 9 jars and 9 labels
Post by towr on Dec 4^th, 2002, 9:14am

Simulation would be my easy answer.. just try it out by computer several thousand times.. (actually since it's just nine, you can try all possibilities once)

Probability theory would be a better way.. But I'd have to think about that first..

Title: Re: help needed: 9 jars and 9 labels
Post by towr on Dec 4^th, 2002, 9:51am

Your guess is right btw, it's 1..

Title: Re: help needed: 9 jars and 9 labels
Post by James Fingas on Dec 4^th, 2002, 12:34pm

Kozo,

Maybe a proof by induction would work here. I'm thinking along the lines of:

1) Assuming label 9 ends up on jar 9 (p = 1/9), then our expectation is one more than the expectation for 8 jars and 8 labels.

2) Assuming label 1 ends up on jar 9 (p = 1/9), then we get the expectation for 8 jars and 8 labels, but we subtract the probability that the 1^st label that was correct (which we get by symmetry of the labels 1 to 8).

3) The same logic applies to all labels from 2 to 8 ending up on jar 9.

I haven't worked through it, but I imagine that it will work nicely.

Title: Re: help needed: 9 jars and 9 labels
Post by TimMann on Dec 4^th, 2002, 7:27pm

What's the probability that exactly one label ends up on the wrong jar? ;)

Title: Re: help needed: 9 jars and 9 labels
Post by Kozo Morimoto on Dec 4^th, 2002, 11:33pm

What's the probability that exactly one label ends up on the wrong jar?
-----------------
That's a good one.

But working on the problem, 9! = 362,880

no. of 9 correct labels = 1
no. of 8 correct labels = 0
no. of 7 correct labels = COMBIN(9,7) = 36 ?
for each 7 correct labels, you can only have 1 combination of 2 wrong labels...

but how do I calc the next step with no. of 6 correct labels?
COMBIN(9,6) = 84 and FACT(3)=6, but some of the 6 wrongs include the situation where you may have 7 or 9 correct labels. So out of the 6, 1 would be when 9 labels are correct and 3 of then are when 7 labels are correct which only leaves us with 2?

So,

no. of 6 correct labels = 168 ?

Title: Re: help needed: 9 jars and 9 labels
Post by Nigel_Parsons on Apr 11^th, 2004, 8:45am

To continue this thought process, and it gets complex.
For 6 correct there are indeed 168 ways to select 6 correct from 9, including the fact that the 3 'wrong' labels can be selected 2 ways. i.e. if labels 4-9 are correct, to have 6 correct & only 6 then labels 1 2 & 3 must all be wrong. The 6 arrangements of labels for 1 2 & 3 give:
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 & 3 2 1
of which only 2 3 1 & 3 1 2 are totally incorrect.

The next level (5 correct) gets tougher. There are 126 arrangements of 5 correct. i.e. 9!/(5! * 4!)
However, these can appear with any arrangement of 4 incorrect labels, and there are 9 ways to get 4 wrong labels.
Thus there are 9*126 or 1134 ways to get 5 correct labels

Back to the drawing board for the next level (4 correct) I have a feeling the complexity will increase

Title: Re: help needed: 9 jars and 9 labels
Post by Barukh on Apr 11^th, 2004, 10:32am

Check the Umbrela makers' convention (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1078433909) thread - it discusses the same problem.

Title: Re: help needed: 9 jars and 9 labels
Post by grimbal on May 1^st, 2004, 5:17pm

Thinking of just trying all the combinations.

Imagine all the jars in a circle. For each possible arrangement of the labels, you can get 8 other arrangements by rotating all the labels. Over these 9 arrangements, each label is right exactly 1 time out of 9. That is an average of 1 correct label per arrangement. The set of all arangments is the sum of all such sets of 9. So the average is 1 overall.

Title: Re: 9 jars and 9 labels
Post by rmsgrey on May 2^nd, 2004, 6:22am

Very nice grimbal. Makes all our messing around with conditional probabilities and case counting look messy and inefficient! :)

Title: Re: 9 jars and 9 labels
Post by yadayada on May 3^rd, 2004, 5:36pm

Here is one way to look at it.

[hide]

Say there are n cans.

let X(i) be 1 if you label the ith jar correctly.
Let it be 0 othewise.

Now Expected value of X(i) is 1/n.

The number of correct labels is X = X(1) + X(2) + ...+ X(n)
By linearity of expectation,
Expected value of X = sum of Expected values of X(i)'s
= n * 1/n = 1

[/hide]