# Puzzle: last one left over

October 19, 2007 am31 6:01 am

I found this on a list-serve (AMTNYS) (guy named Knox posted it):

`The digits from 0 - 9 are separated into 3 groups: A (0, 1, 2, 3); B (4, 5, 6); C (7, 8, 9). Digits are selected at random (no repeats) until the numbers from an entire group are chosen. What is the probability that group "A" will be selected?`

17 Comments
leave one →

A deceptively challenging problem, it plagued me last night as I was trying to fall asleep, but I still haven’t come up with the right way of looking at it!

Well, one simplification is to consider that there is a 2/5 chance that the first draw is from group A leaving exactly 3 numbers in all of the groups. After that it should be clear that there is an equal chance of drawing any one of the 3 groups first, so the chance of selecting A first and then getting all of the rest of the A numbers is (4/5)*(1/3).

Indeed, Brian, I think you hit the “right” way to look at it. Sadly, my much less clever and more convoluted method involving casework does not come up with the same answer (I got 23/105) and I haven’t been able to find my “bug” although I’m sure your answer is right (though I think you meant 2/5 at the end and not 4/5)

I think Brian has part of the answer(as he also clearly seems to indicate in his response). The rest of it also needs to be considered. We should get 2/5*1/3+3/5*x, where x is the probability of getting all of A provided we did not choose one from A first.

One way to go about it is to look at all possible arrangments of the numbers = 10!, and the arrangements with two numbers from B and C as the last two. This gives 9*8! arrangements. This is an undercount for the number of ways A can be selected first, but still gives a probability of 1/5 ( a lower bound, but better than Brian’s lower bound of 2/15).

With a simulation (an easy out for us engineers), I get a probability of about 0.26 for A, and 0.37 for B and C.

Clueless

I get mathmom’s 23/105 as the probability of succeeding if Brian’s trick doesn’t work. So the overall probability should be (3/5)*(23/105)+(2/5)(1/3)=139/525.

Of course, this assumes that I didn’t make an arithmetic error somewhere, which seems kind of likely. It seems like there should be some kind of elegant generating function solution, but I’m too rusty to come up with it: all the things I tried led to nasty PDEs.

brian’s only offered a partial solution

so there needn’t be a “bug” …

on the other hand, i got 9/35.

on the third hand, i don’t have

a whole *lot* of confidence in my result:

(1) it’s always so easy to overlook

essential details in combinatorics, and

(2) the whole approach suddenly

seems completely fishy (*after*

writing it almost all the way out here;

doggone if i’m not gonna take the credit

in case it’s actually right …).

anyhow, here goes.

there are 10!/(4!3!3!) = 4200 “strings”

consisting of 4 A’s, 3 B’s and 3 C’s.

we want to count the ones having

the fourth A before either the 3rd B or 3rd C.

break ’em down into cases:

AAAA****** (A “wins” on the 4th draw):

there are 6!/(3!3!) of these.

A wins in 5steps: 2* 4*5!/(3!2!) ways

(in AAAA, there are 4 positions

into which we can insert another letter

and still have an A in 5th place

[*AAAA, A*AAA, AA*AA, & AAA*A];

2 choices of letter; the rest is the

“distinguishable permutations” trick

i’ve already used twice).

A wins on the 6th draw:

we distinguish two subcases,

where the other two letters do or don’t match.

in the matching case, we get

2* [4c2+4] * 4!/(3!1!) = 80

(two choices of letter; 4c2 ways to pick

*different* slots to put ’em in, plus 4

ways to put ’em in the *same* slot;

the usual bit at the tail end).

in the unmatched case, there are

4*5*4!/(2!2!) = 120 possibilities

(4 slots for the B; 5 for the C

once the B has been added in).

seven steps: 2B’s & a C or 2C’s and a B. so

2*(4+ 4c2)*6 * 3!/(2!1!) = 360

(choice of doubled letter; choice of slots

*for* the doubled letter; 6 slots for the

singleton; the usual (which is now looking

sort of ridiculous since 3!/(2!1!) = 3 of course).

finally, 8 steps: 2 B’s & 2C’s.

(4 + 4c2)(6 + 6c2)* 2!(1!1!) = 420

–put the B’s somewhere in the 4 “slots” first,

then the C’s in the 6 slots (2 newly created

by the insertion of B’s); distinguishable perms.

add ’em up; divide by 4200; done.

this is the fishy part … haven’t i got the wrong

sample space here now that i think about it?

who says these “equally likely strings” have

anything to do with “outcomes of the game”?

i have to quit thinking about this for a while

since my girlfriend has come to get me.

i won’t be back at the computer till monday.

anybody care to check this for me?

Oh, yeah, Brian’s solution is only for when we pick an A first. But A can still “win” if we pick a B or C first. I was so taken by the simplicity of his solution, that I forgot about the other cases.

I’ll type up my full solution later tonight. But what I did was say that the game would end after at most 8 picks, so I only considered strings of 8 of the characters, then went on to consider a bunch of cases… more later. :)

And in starting to write up my solution, I did find one bug. So now I’m coming up with 9/35 or approx .257 which is happily close to Clueless’ empirical result.

The game ends after at most 8 moves

Consider the 10!/2! possible strings of the first 8 picks.

A “winning” string for A contains all of 0 1 2 3 before all of 4 5 6 or 7 8 9. Let’s consider the possible ways we can have winning strings.

Case 1) The string contains all of 0 1 2 3 and two each from sets B and C

There are 3 ways to chose the 2 items from B, 3 ways to choose the 2 items from C, and 8! ways to arrange the 8 items once we have them chosen. So that’s 3x3x8! = 9! such arrangements.

Case 2) The string contains all of 0 1 2 3 and all of 4 5 6 and only one from set C – some of these will be winning strings and some will be losing strings. Let’s look at the winning strings:

2a) all of 0 1 2 3 occur in (any 4 of) the first 6 slots (so as most two from group B occurred before the last of group A)

Then there are 6C4 ways to choose the 4 spots for the group A numbers, 4! ways to arrange the A numbers within those 4 spots, and 4! ways to arrange the other numbers within the other 4 spots, and 3 choices of which element from set C is included. So that’s 6C4 x 4! x 4! x 3 (The bug was forgetting the 3’s in this and the other case 2 and 3 subcases) = 15 x 24 x 24 x 3 = 25920

2b) 3 items from A occur in the first 6 slots, the 4th item from list A occurs in the 7th slot and one item from list B occurs in the 8th slot (so list B is still completed after list A)

Then there are:

4 choices of which A number goes in the 7th slot

3 choices of which B number goes in the 8th slot

6C3 ways of choosing spots for the other 3 A numbers

3! ways of arranging those 3 A numbers in their 3 slots

3! ways of arranging the other two B numbers and the C number in the other 3 of the first 6 slots

3 choices of which C number was included

4x3x20x6x6x3 = 25920 (ok, that surprised me!)

Case 3 is the analog of case 2, but with all of set C and only 1 item from set B. So that’s another 2 x 25920 good strings

Adding it all up, it comes to 466560 / 1814400 which reduces to 9/35

Have at it!

Vlorbik, I just realized that you and I now have the right answer. Since we got it in somewhat different ways, and it lines up with Clueless’ experimental results, I think we’re onto something.

You said:

who says these “equally likely strings” haveanything to do with “outcomes of the game”?

Well, I made the same assumption, so we could both have the same wrong answer due to the same wrong assumption, but I think it’s an ok assumption.

The strings represent a record of a game. They will be longer than they need to be, since the game will end before the 10th number is drawn, but it is a valid simplification to consider them all anyhow. If we looked at the cut-off strings, their probability would just the the sum of the probabilities of all the eventual 10-element strings that could have come out of them.

I thought that you were making a mistake by ignoring the permutations of the different elements between the two groups, but I realize now that that is a valid simplification as well, since all of the permutations of any string pattern will be equally “good” or “bad” strings, to the proportions are preserved.

I finally managed to get 9/35 also. So, by a simple majority of 3(Vlorbik, Mathmom and me), this answer wins :-)

My method (similar to Vlorbik’s, but treating the digits as distinct).

P= sum of probabiliy of winning in k steps, k=4 to 8. Note that these are mutually exclusive events, so we can add the probabilities.

P(4) = 4!/(10P4)

P(5) = 4.6C1 * 4!/(10P5): SInce you win in exactly five steps, the last one should be from the first set, which can be picked in 4 ways, the other one is one of the 6, and the first five can be arranged in 5! ways

P(6) = 4. 6C2*5!/(10P6): SImilar reasoning to the above

P(7) = 4. (6C3 -2) 6!/(10P7): Similar reasoning to the above, except if we choose 3 from any one of the other sets, we cannot win in exactly seven steps. There are two ways of doing this.

P(8) = 4. 9. 7!/(10P8). 9 is the number of ways of choosing the last two numbers, one each from B & C, and this should be equal to 6C4 – the number of ways in which all three elements of B or C are chosen.

Adding them up, we happily get 9/35.

There must be a more elegant way of doing this without explicit counting as above. Unfortunately (for me), it still eludes me.

Clueless.

Suppose that we select digits until all 10 digits have been selected. The last digit belongs to A, B, or C with probability 4/10, 3/10, and 3/10 respectively.

If the last digit belongs to A, then group A cannot be selected.

If the last digit belongs to B, then we must consider the digits belonging to A or C. If the last of those digits is in C,

then group A is selected; and if the last of those digits is in A, then group C is selected. But 3 of those 7 digits belong to C,

so the probability is 3/7 that group A is selected given that the last digit belongs to B.

By similar reasoning, the probability is 3/7 that group A is selected given that the last digit belongs to C.

Therefore the overall probability of selecting group A is (4/10)*0 + (3/10)*(3/7) + (3/10)*(3/7) = 9/35.

That is a pretty cool method, David!

Initially, I was confused as to how you could use just seven digits after conditioning on the last digit, but it became clear that you could ignore the two digits of the same kind as the last digit since they will have no bearing on the outcome.

Clueless.

Ah, very nice, David! I knew there had to be a better way!

I’m glad I finally managed to get the right answer with my convoluted way too, though. There’s something oddly satisfying about working through an ugly set of case logic once in a while, though not as satisfying as coming up with a nice clean solution. :)

Look at the last one’s chosen. Let P and Q stand for the two bad sets, Q designates the last chosen.

A ‘win’ is –PQ

or –PQQ

or -PQQQ

working right to left

+ +

=

=

=

It’s nice when several approaches end in the same place