Блог пользователя olenihc

Автор olenihc, история, 8 лет назад, По-английски

I've come across this probability problem and could not solve it. In order to learn, I searched for the solution on the internet and found out that people just printed 1/2. i.e., the answer, no matter the value of n, is always 50%.

Why is that so? I tried making some DP for testing values under ~20 and only when n = 2 the answer is indeed 1/2.

Can someone give me some help on this tough (for me) one?

Appreciate the help!

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

The last vacant seat must be either seat 1 or seat n, because otherwise the person that owns it would have occupied it.

But because the first n-1 passengers don't have tickets for either one of those seats, there's no difference between those two seats in our problem. Therefore the probability that the last vacant seat is 1 is the same as the probability that the last vacant seat is n, and they equal 1/2.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Well, ffao was faster than me. Anyway, you could also think that if some person i < n sits in a wrong place, then there exists some j > i that will sit in a wrong place too.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Nice one too!! Thank you!!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Actually, don't think about it because it's wrong :p. In the way I described doesn't imply that the nth person will sit in a wrong place.