# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Message body

 Emoticons View more Emoticons
 [quote="Lepton*"][spoiler]50% - either he does or he doesn't[/spoiler] :-)[/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
 Topic review
Author Message
ralphmerridew
Posted: Wed Apr 07, 2010 1:02 pm    Post subject: 1

Everybody from person 1 through person k-1 treats seats 1, k, k+1, ... N identically, so the chance that each is occupied before person k's turn must be equal.
lostdummy
Posted: Wed Apr 07, 2010 9:44 am    Post subject: 0

Nice - it has same result as my simulation (95.8%) , so it looks like good solution.

That (N+1-k)/(N+2-k) part is quite simple and elegant and it solve also original #100 problem. Only thing that could be questionable is if chance of free seat at 1,k,k+1...N is really same for every seat. But result number suggest that is is ;p
ralphmerridew
Posted: Tue Apr 06, 2010 6:21 pm    Post subject: -1

Also, prob. that a randomly chosen not-1 person will sit in his correct seat:

If my previous answer is correct, prob. is:
P = sum (k = 2 to N : Prob (he is #k) * Prob (#k gets own seat)
= (1/(N-1)) * sum (k = 2 to N : Prob #k gets own seat)
= (1/(N-1)) * sum (k = 2 to N : (N+1-k)/(N+2-k))
= (1/(N-1)) * (sum (k = 2 to N : 1 - 1/(N+2-k)))
= (1/(N-1)) * (N-1 - sum (k = 2 to N : 1/(N+2-k)))
= (1/(N-1)) * (N-1 - (1/N + 1/(N-1) + 1/(N-2) + ... + 1/2))
= (1/(N-1)) * (N - (1/N + 1/(N-1) + ... + 1/2 + 1))
= (1/(N-1)) * (N - H_n)
= (N - H_N) / (N - 1)
~= (N - ln N + y) / (N - 1)
where y is Euler's constant (~= .57).
ralphmerridew
Posted: Tue Apr 06, 2010 6:11 pm    Post subject: -2

I think that, with N people, the chance that person #k (k>1) sits in his own seat is (N+1-k)/(N+2-k).

Intuitive explanation:
Consider the seats 1, k, k+1, ... N. (Total of N+2-k.) Of those, exactly one will be occupied when person #k is about to sit. If that seat is #k (prob. 1/(N+2-k)), then person #k won't get his seat; otherwise (prob. (N+1-k)/(N+2-k)), he will.

Anybody care to make that rigorous?
lostdummy
Posted: Tue Apr 06, 2010 4:00 pm    Post subject: -3

Well, my initial remark still stays - problem does not explicitly state order of entrance, and thus it does not require person #100 to enter last.

And if person #100 have random position in entrance order, solution is not same. I have result value from simulation, and it is noticeably different (around 95% chance to sit in his chair). Would be interesting to see math solution on that one ;p
groza528
Posted: Tue Apr 06, 2010 2:33 pm    Post subject: -4

lostdummy wrote:
Well, the (same) result only require that person #100 be the last person, but it seems like some of above solutions assumed ordered entrance of other people - for example, statement that "Person X may not select a lower-numbered seat other than #1 " may require ordered entrance.

No, ralphmerridew is right-- the same results would apply but they would have to be reworded. The seats can be completely arbitrary. For that one it would be "Person X cannot sit in any seat assigned to someone who entered before him, other than the seat assigned to the first person to enter."
lostdummy
Posted: Tue Apr 06, 2010 12:36 pm    Post subject: -5

Well, the (same) result only require that person #100 be the last person, but it seems like some of above solutions assumed ordered entrance of other people - for example, statement that "Person X may not select a lower-numbered seat other than #1 " may require ordered entrance.

Anyway, it would be interesting to see what would be solution for case where person #100 can randomly enter (ie only #1 is fixed as first to enter).

Alternative question without changing how they enter would be:
what is chance for n-th person ( n = 2..100) to sit in his seat ?
ralphmerridew
Posted: Tue Apr 06, 2010 12:00 pm    Post subject: -6

The solution only requires that person #100 be the last person to enter. (Just number the people by the order in which they enter; their seats can be scattered all around the auditorium.)
lostdummy
Posted: Tue Apr 06, 2010 11:25 am    Post subject: -7

Actually, above solution presume that people try to seat in exact order, from 1 to 100. While it can be assumed from posted problem, it is not explicitly stated - only thing that is explicitly stated is that person #1 will enter first to choose seat.

I guess it would make slightly harder problem to solve if we ask for probability of person #100 to sit in his seat if entrance order is also random (except from person #1).
Zag
Posted: Mon Apr 05, 2010 8:05 pm    Post subject: -8

Ummm. right. I wrote that while I was in a meeting, and I wasn't thinking correctly. I agree that person 100 can only end up in his own seat or seat #1. (It's a scientific fact that being in a meeting will make you stupider.)
lexprod
Posted: Mon Apr 05, 2010 7:57 pm    Post subject: -9

Zag wrote:

Person 1 chooses a chair at random, let's say #23.
2 through 22 get their own seats.
23 chooses at random. He might choose #1.
24 through 99 get their own seats.
100 ends up in #23.

I was gonna chime in with the same thing, but reading your guys' explanations of how this can't happen I understand the folly. Good thing I didn't speak up and look st-.......crap.
Nsof
Posted: Mon Apr 05, 2010 7:18 pm    Post subject: -10

Quailman wrote:
So person 1 and person 100 are sharing seat 23?
Depending on what's presenting this might be appropriate

groza528 wrote:
In fact, I think the proof that person 100 is in either #1 or #100 is fairly simple.
I think so too but only after reading your proof
Quailman
Posted: Mon Apr 05, 2010 7:03 pm    Post subject: -11

Zag wrote:
Nsof wrote:
The explanation for why the Sets are the same size comes from the following claim: If person 100 is not in chair 100 then he must be in chair 1.

I pretty completely didn't understand what you said. But I did understand this line, and I know it to be false.

Person 1 chooses a chair at random, let's say #23.
2 through 22 get their own seats.
23 chooses at random. He might choose #1.
24 through 99 get their own seats.
100 ends up in #23.

So person 1 and person 100 are sharing seat 23?
groza528
Posted: Mon Apr 05, 2010 6:08 pm    Post subject: -12

2 can sit in #1. I said they cannot choose a lower-numbered seat *except* #1. If 2 is in #1 then 100 will be in #100.
Antrax
Posted: Mon Apr 05, 2010 5:58 pm    Post subject: -13

I'm confused. Why can't #2 sit in seat #1, for instance? In the rules it says that if your seat is occupied, you choose randomly from what's available. So if #1 sits in seat #2, person #2 has a 1/99 chance of sitting in seat #1. No?
groza528
Posted: Mon Apr 05, 2010 5:05 pm    Post subject: -14

Zag wrote:
Nsof wrote:
The explanation for why the Sets are the same size comes from the following claim: If person 100 is not in chair 100 then he must be in chair 1.

I pretty completely didn't understand what you said. But I did understand this line, and I know it to be false.

Person 1 chooses a chair at random, let's say #23.
2 through 22 get their own seats.
23 chooses at random. He might choose #1.
24 through 99 get their own seats.
100 ends up in #23.

...No?

In fact, I think the proof that person 100 is in either #1 or #100 is fairly simple.

Assume person X arrives to find his or her seat occupied.
Person X may not select a lower-numbered seat other than #1 because all lower-numbered seats will fulfill one of the following requirements:
- is #1
- was occupied by its rightful owner when he or she arrived
- was already occupied when the rightful owner arrived

So for X = 100, X cannot possibly sit in seats #2-99.

The other corollaries aren't too tough either...
When person X arrives, X-1 seats are occupied. If his own seat is occupied, then we know for certain that at least one lower-numbered seat must be available. We have already proven that this could only be seat #1.
Zag
Posted: Mon Apr 05, 2010 3:54 pm    Post subject: -15

Nsof wrote:
The explanation for why the Sets are the same size comes from the following claim: If person 100 is not in chair 100 then he must be in chair 1.

I pretty completely didn't understand what you said. But I did understand this line, and I know it to be false.

Person 1 chooses a chair at random, let's say #23.
2 through 22 get their own seats.
23 chooses at random. He might choose #1.
24 through 99 get their own seats.
100 ends up in #23.
Nsof
Posted: Mon Apr 05, 2010 1:36 pm    Post subject: -16

I found the same solution Zag found. My friend had another solution:

1) He split the sample space (all the legal seatings of the people) into two sets:
Set 1 contains all sample cases where person 100 does not sit in chair 100.
Set 2 contains all sample cases where person 100 sits in chair 100. (This set represents the event 'person 100 sat in chair 100'. We are interested in finding the probability of this event.)

I would expect that the order of Set 1 should be much larger than that of Set 2 because if we look at all possible permutations of 1,…,100 there are 99 times more permutation where 100 is not at the end (of which Set 1 is composed) compared to where 100 is in the end (of which Set 2 is composed).

While not all permutations are legal i expected the ratio to remain. But
2) He then showed a bijection between the two sets such that the bijection pairs cases that have the same probability.
This meant that the two sets have the same probability of occurring and so the answer is 0.5.

The explanation for why the Sets are the same size comes from the following claim: If person 100 is not in chair 100 then he must be in chair 1.

To see that, the following must be shown (all require more rigorous proof)
Lemma: if its person N's turn to sit and her/his chair is taken then all people 1,...,N-1 are sitting in chairs 2,...,N
Corollary 1: if its person N's turn to sit and her/his chair is taken then chair 1 is available
Corollary 2: if its person N's turn to sit and s/he chooses to sit in chair 1 then everyone after person N will be sitting in their place.
Corollary 3: If someone other than person 100 is in chair 1 then person 100 must be sitting in chair 100.
Corollary 4: If person 100 is not in chair 100 then he must be in chair 1.

The Bijection
Let's look at a sample case s from Set 1 (where person 100 does not sit in chair 100).
By corollary 4, person 100 sits in chair 1, so s looks something like
s = (100, s2, s3,…,s99, s100)
We'll define f(s)=r=(s100, s2, s3,…,s99, 100)
f switches between person 100 and the person sitting in chair 100

Claim 1: f is a bijection
Claim 2: Prob(s) = Prob(r)
Again both need to be explained further.

obviously not as elegant as Leptons
Lepton*
Posted: Sun Apr 04, 2010 3:19 pm    Post subject: -17

50% - either he does or he doesn't
MatthewV
Posted: Sun Apr 04, 2010 12:17 am    Post subject: -18

See--- I hate trying to figure out math in terms of math. And it took took long to type apparently!
MatthewV
Posted: Sun Apr 04, 2010 12:14 am    Post subject: -19

[50% of the time

I thought about an easier problem-- a theater with just 5 seats and the same setup and then expanded the process.
So if Dude1 sits in seat number...

5, then there is a 0 chance D5 will be in 5.

4, then seats 2,3,4 are full. D4 will sit randomly in 1 or 5 (0.5 chance of D5 in 5)

3, then seats 2,3 are full. D3 will sit randomly in 1,4,5. If 1, D5 will be in 5. If 4, then D4 will sit randomly in 1 or 5. if 5, D5 will not sit in 5. So... what 1/3 of the time, D5 will be in 5, 1/3 we get a 0.5 from D4 next, and 1/3 we get D5 not in 5. But this all sums to a 0.5 chance D5 ends up in 5.

2, then seat 2 if full. And D2 will make us go 1/4 of the time to seat 1 (D5 will sit in 5), seat 3 (see above, 0.5 success), seat 4 (see above, 0.5 success), seat 5 (no success). This still goes to 0.5

1, then everyone will sit in their seat, D5 will be in 5.
]

From my understanding, this could expand to 100 seats. My friends always hate the way I deal with situations of probability; I am posting partly because I would like to see if/where my logic is flawed.
Zag
Posted: Sat Apr 03, 2010 11:58 pm    Post subject: -20

I have to admit that I've seen a puzzle like this before, but I figured it out when I first saw it, so I feel justified in claiming this one.

The answer is exactly 50%.

Explanation:

Ignore the 100, let's just say that there are N seats, where N > 1

Person 1 chooses his seat randomly. He might choose
Seat 1: 1/N
Seat 100: 1/N
Some other seat (N-2)/N

The chances of the first two are equal, and, if either is chosen, completely determine the final answer. That is, if the random person accidentally chooses his own seat, Mr. 100 will end up with his own seat. And if random person chooses seat #100, then Mr. 100 obviously will not get it. So, so far, we have equal chance of success or failure.

If Mr. Random chooses some other seat, then nothing matters until we get to the person whose seat he chose, because everyone up until that point will be taking his assigned seat. At this point, we are back to the original problem -- there are N 1 seats left, and a person is choosing randomly from amongst the available seats. He might choose
Seat 1: 1/N 1
Seat 100: 1/N 1
Some other seat (N 1 -2)/N 1

Etc.
Nsof
Posted: Sat Apr 03, 2010 11:10 pm    Post subject: -21

From a friend

100 people, numbered 1 to 100, are waiting in line to sit in the theater. The theater has 100 seats also numbered 1 to 100.
The people sit one after the other according to the following rules:
1) Person number 1 randomly chooses one of the seats with equal probability and sits there.
2) Each person after that sits in the chair that equals his/her number unless it is already taken. If that happens s/he randomly choose one of the available seats with equal probability and sits there.

What is the probability that person 100 sits in seat 100?
--edit: fixed some spelling errors