Probability question: names in hats

[robvalue]

OK, interesting.

I have coded the problem.

I am getting the following results, over a series of 5000 games:

3 players: around 25%
4 players: around 14%
10 players: around 8%

This would tentatively place Aractus's solution as wrong, although I haven't looked through it properly yet.

The first two there line up with my calculations: 1/4 and 5/36 for 3 and 4 players respectively

Here is the code, in microsoft small basic:

---

done=0

While done=0


ok=0
While ok=0
 TextWindow.WriteLine("")
 TextWindow.WriteLine("Enter number of players (at least 3)")
 TextWindow.WriteLine("")
 players=TextWindow.ReadNumber()
 For i = 3 To 10
   If players = i Then
     ok=1
   EndIf
 EndFor
EndWhile

TextWindow.WriteLine("")
TextWindow.WriteLine("Enter index for number of times to run")
TextWindow.WriteLine("")
times=TextWindow.ReadNumber()

wins=0

For i = 1 To times
 left=players
 For j = 1 to players
   ticket[j] = j
 EndFor
 
 
 
 For j = 1 to players-1
   
   ok=0
   While ok=0
   
   b = left
   random()
   If ticket[a] <> j Then
     ok=1
   EndIf
   
   endwhile
   
   choice[j] = ticket[a]
   
   If a < left Then
     For k = a to left
     ticket[k] = ticket[k+1]
   EndFor
   
   EndIf
   
 left = left - 1
   
 EndFor
 
 choice[players]=ticket[1]
 
 If choice[players] = players then
 wins = wins + 1
endif

 
 EndFor
 
 
 TextWindow.Write("Wins ")
 TextWindow.WriteLine(wins)
 TextWindow.WriteLine("")
 TextWindow.Write("Win % ")
 TextWindow.WriteLine(Math.Round((100*wins / times)))
 TextWindow.WriteLine("")

endwhile


Sub random
 a = Math.GetRandomNumber(b)

EndSub

 
 

---

[ignoramus]

I'm in the lead so far with my 1 in 20 chances. (5%)

Where's my frozen chook or a kettle or something that I won?

(Doesn't say much for you bozos considering my IQ is Sagittarius)

[robvalue]

You win a hat with a load of bits of paper in it

I'm a bit surprised it's around 8%, I would have guessed lower I think. Of course my experiment isn't conclusive, but it was around that number for many iterations of 5000 / 10,000 games each.

[robvalue]

This can be solved through brute force, in theory at least, using a tree diagram. It's just that it is going to be monstrously big.

The first choice produces 8 distinct possibilities that keep the game going, each of which affect further probabilities in different ways. Each of those will lead to 7 or 8 more possibilities, then each of those leads to 6 or 7...

I think key to solving this is to try and find a formula for each combination, to see what the overlap is between different combinations, and then find a way of counting them all into useful groups.

The guy who told me this claimed he and his mates had solved it, but I don't know if they got it right or not. They didn't tell me the answer.

[Cyberman]

Can't we just say it's a miracle and then we wouldn't have to think about it anymore?

[robvalue]

That is the correct answer.

[Whateverist]

Oh do you suppose this is one of those supernatural thingies? Hmmm, I wonder if Craig has a proof of God based on it.

[robvalue]

Well, we don't have a full solution yet, so yeah.

That's what supernatural means, right?

It was fun doing a bit of coding. I haven't done any for a while.

[emjay]

I've had a couple of goes at this without much luck so far.

I'd go about it by saying that the probability should be 1 minus the sum of the probabilities of all branches where a previous player hits player 10's name. Is that correct?

As I understand it, all branches of the tree should add up to 1 but only if they are mutually exclusive... if there's no crossover between events. So the problem I'm finding is how to define the branches of a player choosing. In the simple case, player 1 has a 1/10 chance of hitting player 10's name. But I can't figure out how to phrase this additional choice he has if he hits his own name, or if it even makes any difference.

There's a 1/10 chance that he will hit his own name and a 9/10 chance that he will not. If he does not, he does not choose again, but it's implicit in that he did not that the name chosen is not his own. Conversely, if he gets to choose again it's only out of the other 9 names that are not his own, but in either case the net effect after the choice is that player 1's name stays in the pot and another name is removed. So I wonder if it even matters for this particular question - the probability of a player hitting player 10's name - about this second choice which appears to collapse down to the same thing.

So rob, how would you define the first choice... the probability of player 1 hitting player 10's name? Would you say a simple 1/10 or something like (1/10 * 1/9) + (9/10 * 1/9 or 1/10... I'm not sure what that's supposed to be given that I'm trying to add an implicit choice here that isn't really there just to make sure that the two branches do not overlap). It's very confusing but a fun puzzle 

[Aractus]

Here's the probability tree for 4 people:



So for Sn where n equals the probability that person n makes winning impossible for person 4, S1 + S2 + 2S3 = 1. S3 gives you both the probability of winning, and the probability that person 3 creates a loosing situation for person 4.

So:

S1 + S2 + 2S3 = 1
2S3 = 1 - S1 - S2

S3 = ½(1 - S1 - S2)

Okay, and here are the sums themselves.

S1 = ¼(1+1/3)
S2 = ¼(1/3)[3 + 3(1/3) + (1/3)½ + ½]
S3 = ¼(1/3)½[2 + 2(1/3) + (1/3)½ + ½]

Now do note that S1 only concerns itself with 4 being picked, whereas S2 requires that both 4 is not picked and 3 is not available to be picked next. So we could instead come up with a formula to compensates for this, we'll call it S2b that only cares if 4 is picked. It would look like this (I'll compensate for S3 while I'm at it):

S1 = ¼(1+1/3)
S2b = ¼(1/3)[2 + 2(1/3) + (1/3)½ + ½]
S3b = ¼(1/3)[2½ + 2(1/3)½ + (1/3)½2 + ½2 + (1/3)]