## Bags I go nth

Posted by Chris on February 26, 2011 – 5:33 pm

You are in a lucky dip style competition. There is a bag with tickets in it. They are numbered 1 to 100. One of them wins tonight’s star prize, the others win nothing. It is equally likely that any one of the tickets is the winner. Only the host knows the lucky number. 100 people form a queue and in the order of their position in the queue, randomly take one of the tickets and show it to the host. If the number on the ticket is divisible by 3, it is put back into the bag, but you still get the prize. The winner isn’t announced until all of the contestants have selected a ticket (in fact, that’s irrelevant).

What is the optimum position to be standing in the queue to maximise your chance of winning the star prize?

February 26th, 2011 at 5:44 pm

As long as the members of the queue do not know the winning number and the host does not give away the winning number by some reaction to being shown a particular number,I would say that no position has an advantage over any other position.

February 26th, 2011 at 5:48 pm

Sorry. I missed the line about divisible by 3.

February 26th, 2011 at 5:51 pm

Hi JB. I have revised the question several times. You posted while I was still editing it.

February 26th, 2011 at 5:56 pm

Hopefully, the third time’s the charm. I completely misread the question the first time. I would think that the first position would be the optimal position. The further into the queue you go the higher the percentage of numbers divisible by three there are going to be and the less likely you are to end up with any ticket at all. The last person in line probably faces a significant disadvantage. All those still holding on to a ticket at the end will be equally likely to win.

February 26th, 2011 at 6:01 pm

Hi JB. You hadn’t misread the question. The question had changed. But I’m doubly surprised by your last answer.

February 26th, 2011 at 7:18 pm

What if the winning ticket is divisible by 3? Does that mean nobody wins? Multiple people win? The first person to draw it wins?

Also it says the winner isn’t announced until everyone has selected a ticket. Does this mean those who got a divisible by 3 ticket won’t have a ticket at all?

Very confused by this one.

February 26th, 2011 at 7:26 pm

You still get the prize, you just don’t retain the ticket. So the prize could be won by everyone (if the lucky ticket was divisible by 3).

February 26th, 2011 at 7:40 pm

Again I misunderstood the question. I was thinking that you had to be holding the winning ticket to win. That would also have meant that no number divisible by 3 would be the winning number.

February 26th, 2011 at 8:48 pm

Hi JB. Not so, tht would have meant that if the winning number had been divisible by 3 no one would have won.

February 26th, 2011 at 9:13 pm

I’m confused. Let’s say someone goes and takes ticket number 9, then puts it back. Does that mean that if someone else takes ticket number 9 too, both of them will get the prize if the lucky number is 9?

February 26th, 2011 at 9:21 pm

Hi MS. That’s right. e.g. Let the winning ticket be 9. Then there is one chance in 10,000 that everyone picks 9. That’s 100 winners. [Later: Ooops, I should have said 100^100, not 10^4].

I’ve amended the problem to make that clearer. Unfortunately I went live with the problem, then embellished it afterwards. I’m apologise for the confusion that’s caused.

February 27th, 2011 at 12:52 am

If the winning ticket is div-3 (33/100):

Person 1: 1/100 winning & returning; 32/100 losing & returning; 67/100 losing & keeping.

Person 2: 33/100 that there are still 100 tickets left for winning odds 1/100. 67/100 that a loser was removed for winning odds 1/99. (33/100 * 1/100) + (67/100 * 1/99)

If the winning ticket is not div-3 (67/100):

Person 1: 1/100 winning & keeping; 33/100 losing & returning; 66/100 losing & keeping.

Person 2: 33/100 that there are still 100 tickets left for winning odds 1/100. 67/100 that there are 99 tickets left: 1/100 that the winner was already removed for odds 0/99; 66/100 that a loser was removed for odds 1/99. (33/100 * 1/100) + (1/100 * 0/99) + (66/100 * 1/99)

If you combine all that together for Person 2, you get: (33/100 * ((33/100 * 1/100) + (67/100 * 1/99))) + (67/100 * ((33/100 * 1/100) + (1/100 * 0/99) + (66/100 * 1/99)))

= 1/100

Person 1 & 2 both have odds of winning of 1/100. So, I’ll assume this holds for 3 through 100 also, and say it doesn’t matter where you are in line.

February 27th, 2011 at 6:07 am

Hi SP. Correct Each person has a 1/100 probabilty of winning. Thank you for demonstrating that is the case. The tickets being returned, simply means that there can be more tha one winner.

I’m still not sure why JB backed away from his original answer. I can only guess that I ended up confusing him; I was still editing the question when he was answering it. Obviously, I credit JB with getting it right.

February 27th, 2011 at 7:20 am

It doesn’t matter what rule is used for returning or keeping the tickets.

A much simpler case, which I had started writing as a comment on the “Stacked deck” problem, was a bag with one black and one white ball. If the ball is returned, then obviously each person has 1/2 probability of picking the black ball. But if the ball isn’t returned, the half the time the first person picks the black ball and then the other person must pick the white, or vice versa. So each was equally likely to pick the black (or the white), regardless of retaining or returning the ball. I decided that it deserved a whole post of it’s own. That idea grew and I kept on tweaking it, until voila! the posted problem.

February 27th, 2011 at 9:14 am

Thanks for the credit, Chris. But I’m not sure I earned it. When you changed the rules of the game I wasn’t sure what the rules became. I had to leave and did not get back to the problem till now.

February 27th, 2011 at 9:24 am

Hi JB. I have no doubt that you would have reverted to your original answer. Next time I do live editing, I’ll put a “work in progress” sign up.

February 27th, 2011 at 10:39 am

Hi Chris

I think your post #11 is incorrect…….

surely the chance of all 100 contestants picking the number 9 would be 100 x 100 x 100….etc. or 10^199

regards Curtis

February 27th, 2011 at 11:11 am

Hi Curtis. You’re right, my bad. Thanks. That should save the host some extremely serious money. You goofed too; that should have been 100^100 = 10^200 = googol². We got there on the third iteration

February 28th, 2011 at 3:53 am

every one has equal chance

March 2nd, 2011 at 9:52 am

This post should be on the “Stacked Deck” page: http://trickofmind.com/?p=808. I’ve put it here so I can fix any faults. It’s only 98% off topic ^^

[October 2011. Unfortunately there was a serious error here. So I have deleted much of what I had written. Go to http://trickofmind.com/?p=808#comment-7637 for a correct analysis.

Consider dealing 7 cards to 2 players. First let's find the total number of possible combinations of hands that can be dealt to them. The first player can be dealt in 52*51*50*49*48*47*46 different ways. That count includes all the permutations of a particular set of cards, e.g. A1234567 and 32A7564 are counted as two different hands. So we divide by 7! to compensate for that. Altogether that gives 52*51*50*49*48*47*46/7! = 52!/(45! 7!) = C(52,7) = n!/((52-7)! 7!) possible unique hands that can be dealt (where the order they were dealt in doesn't matter).

The second player can get 45*44*43*42*41*39*38/7! = C(45,7) = C(52-7,7) hands. So the total number of ways of dealing to two players is

C(52,7)*C(45,7). You would get the same result if you were to consider dealling the cards alternately to each player e.g.

(52*50*48*46*44*42*40)/7!*(51*49*47*45*43*41*39)/7! = C(52,7,7)

NB When doing these calculations, it is very useful to realise that you can deal 7 cards to one player, then 7 to the next etc., it doesn't make any difference to the probabilities that you'll calculate, but it does make it easier to write the equations. That should be no surprise, because the deck is in a random sequence - you can't make it more random through the dealing process.

But C(52,7)*C(45,7) = 52!/(45! 7!) * 45!/(38! 7!) = 52!/(38! 7! 7!)

= 6071092494667200 ≈ 6.07 * 10^15 (as if you care). These large numbers mean that trying to simulate card games with a PC is impractical.

Noticing that 38 = 52-7-7, suggests defining C(n,a,b) = n!/((n-a-b)! a! b!)

Also note that C(n,b,a) = C(n,a,b) = C(n,a)*C(n-a,b)

If we're dealing to 4 players, we get C(52,7)*C(45,7)*C(38,7)*C(31,7) hands, and we can write that as C(52,7,7,7,7) ≈ 2.01*10^29, where C(n,a,b,c,d) =

n!/((n-a-b-c-d)! a! b! c! d!). If you could simulate dealing 1,000,000,000 hands per second (which is very unlikely), that'd take about 464 times the current age of the universe to do.

NB C(52-a-b,7-a,7-b,7,7)/C(52,7,7,7,7) = C(52-a-b,7-a,7-b)/C(52,7,7)

That has the immediate interpretation that the probability that you will be dealt a particular hand is independent of the number of players (and that's why this article is only 98% off topic). i.e. with one deck, 7 cards per hand, the probability that you wll be dealt 4 aces is 1/7735 for 1 to 7 players (you cannot have 8 players as that would need 56 cards in the deck). I will use that equivalence from now without mentioning that I've done so.

Consider dealing to four players. Let the first player actually have been dealt with a particular run (e.g. four of a kind), I'll call this a prun e.g. 4 aces, and I'll assume that the length of the prun is 4 for definiteness. Then there are

48*47*46 / 3! = 48!/(45! 3!)= C(48,3) ways of choosing his last three cards. Hence, the probability that the (first in this case) player is dealt the prun is

C(48,3,7,7,7)/C(52,7,7,7,7) = C(48,3)/C(52,7). It is also easy to see that if the second player has been dealt a prun (4 deuces say) that the probability that two players get those pruns is C(44,3,3)/C(52,7,7). It is quite sensible to say the the probability of the second player being dealt his prun, given that the first player has been dealt his prun, is C(44,3)/C(52,7). Similarly for 3 pruns we get C(40,3,3,3)/C(52,7,7,7) and for four pruns we get C(36,3,3,3,3)/C(52,7,7,7,7). The probability that seven players each get a prun is C(28,3,3,3,3,3,3,3)/C(52,7,7,7,7,7,7,7). We can’t quite make it to eight players because C(52,7,7,7,7,7,7,7,7) isn’t properly defined - it would involve (52-56)! = (-4)!) (I suppose that could be interpeted as a sort of +/- infinity and so its reciprocal is 0), but C(24,3,3,3,3,3,3,3,3) is defined (just), but only because 0! = 1. That all seems fairly sensible. ie. for 8 players, we could interpret the probability as 0.

Clearly (LOL), those probabilities are for the precisely specified situation of dealing a particular hand (4 aces say) to particular player (player 1 say) etc. From the dealers point of view, he would be just as likely to deal the first hand to any one of the, p, players, and the second to one of the remaining p-1 players and so forth. So for p players and a set of n pruns, there are p!/(p-n)! possible ways he could have dealt them. So the probability of a given hand being dealt to the table is a function of the number of players.

The C(...)/C(52,7,...) expressions aren't very convenient to use. But if you expand and inspect those expressions you'll end up with (now dealing with probabilities for the table): P(n pruns) = p!/(p-n)! * (52-nr)!/52! * (c!/(c-r)!)^n, where n is the number of pruns, r the number of cards in each prun, p the number of players and c is the number of cards dealt to each player. For this formula to work we need r > c/2 and cp ≤ 52. NB If r ≤ c/2, that’s a whole new ball game as you might be aiming for a pair of deuces, but get 3 or 4 deuces - so that'd be a bit silly.

[I've deleted the rest of this comment as it was incorrect - Chris]