Yay!! Thank you, your honour. :D

Do you mean this moo event?

Or this one?

Well played, sir. Well played. :D

I'm posting here just to let you know, I am in whatever future Mafia games.

Yep, it's that time of year again.

I've been kind of AWOL from GOG mafia (and from forum mafia in general, for the most part), but does GOG want to send a champion?




What's that? You volunteer because you've already got experience on MU and know you can at least reasonably handle the pace?

EXCELLENT

Ha! Glad to see you haven't lost your sense of humor. :)

I've only seen two paces on MU: Warp 6 and Dead. Between that and the number of abrasive players I encountered in my few games there, I'm going to give it a pass.

Not me. The pace on MU is too high for me.

While we wait, Joe (or anyone else who's interested)

...

(This one is not mine; I do have the answer for this one though. And it is quite interesting)

A group of 50 people are to enter a hall with 50 seats. Each person is assigned one seat and every seat has a person assigned to it.

The people are told to enter one by one and are given the following instructions: Sit in the seat assigned to you. If that seat is occupied however, choose a random empty seat and sit in in instead.

The first person to enter however is drunk and he just sits in a random seat. Assuming everyone else who enters is sober and follows the instruction, what's the probability that the last person to enter will end up sitting in his own seat?

(Note: try not to go into all the branching probabilities, instead find a general solution for n people).

Ummm

1-[(n-1)/n]

Am I missing something?

No....

A brute force shows that for n=3 the answer is 1/2.

In fact your formula fails for any n>2

Your hint to solve for n was helpful. It made me think of a solution by induction.

So let's consider the case for n-1 persons and seats solved and try to work from there. For starters, n seats means that the drunk person has a 1/n chance of sitting in his own seat, in which case everyone sits in their own seats and therefore also the last person gets their seat. If the drunk person doesn't sit in their own seat, there are n-1 other seats in which they could sit. Randomly. So we add the probability that the last person gets their seat within that subset. Which is solved. The chance that the drunk person selects a wrong seat is (n-1)/n.

Written as probability-chain (sum over the products of the probability that the drunk person chooses a seat with the probability that that choice results in the last seat being the correct one):

P(n) = (1/n)*1 + ((n-1)/n)*P(n-1) = ((1+n-1)/n) * P(n-1) = (n/n) * P(n-1) = P(n-1)

So the probability doesn't change by adding another passenger and seat. Now we just need the probability for the easiest case of n=2. The drunk person chooses one seat randomly. So the second person has a 1/2 chance that the correct seat is free. I.e. P(2) = 0.5
And since P(n)=P(n-1) or in other words P(n+1)=P(n), the probability P(n) = 0.5 for all n>2.

Bravo!

When the problem was presented to me I brute-force solved for 3 and 4, saw it's always 1/2 then went for a solution by induction.

Told you it's interesting.

Yes, it's a good problem. I might use it on my students at some time. :-)

I highly doubt any of us would be so silly as to do that.

...

1/50 chance that original drunk guy (I'll refer to him as 'Vitek' from now on) sits in his own seat and everybody sits down in their own seat.

if not, each time someone sits down they're going to displace someone else... so I'm not sure it's possible for the last person to sit in their own seat. let me think about it.

if there are three chairs, Vitek sits in Joe's chair, Joe enters first he has to sit in Trentonlf's chair, Trentonlf enters he has to sit in Vitek's chair. [Pre-post edit - why can't Joe sit in Vitek's chair, leaving Trentonlf's chair free for Trentonlf? Alright yeah fine.]

If Trentonlf entered first, he'd get to sit in his own chair, but Joe would have to sit in Vitek's chair.

So it looks to me that, though some people would be able to sit in their own chairs, the last person is always going to have been displaced by at least one person. Damn you Vitek!!

[pre-post edit:]

So I read Lifthrasil's answer and think I understand. Thinking about it the initial chance that Vitek sits in his own chair and the puzzle is 100% solved is offset by the initial chance that Vitek sits in Quadralien's chair and the puzzle is instantly unsolvable.

I could try and do what Lifthrasil's done with Ps and (n-to-the-qt)s but I don't really know what it means.

So let me have a look at 4 seats worth. Assuming Vitek sat in neither his own seat, nor in Telika's seat, Joe enters, he has 1/3 chance of sitting in Telika's seat and making the puzzle unsolvable, which is offset by the 1/3 chance he'll sit in Vitek's seat and make the puzzle impossible not to solve. Aha! That's the thing!

So everybody who enters has as much chance of fixing Vitek's mess as they have of ruining everything.


However the true solution, of course, is to get flubbucket to kick Vitek out of the party.