Sunday, May 16, 2021

Eight people sitting around a table ...

 A friend recently asked me this question, 

Eight people including you and me are sitting around a table in random order. What is the chance that I am sitting next to you? 

so I tried solving it with a nine year old from first principles. Was amazed at how clearly kids think. Sketching out the solution we came up with together here.

  1. Imagine there are only two people in the group - this is just you and me. So we are sitting next to each other no matter which way you walk around the circular table. Not that interesting. 
  2. Imagine 3 people - you, me, and a third person sitting around the table. Then, you are next to me on one side, the other person is next to me on the other, and no matter how we sit at the table, you are always next to me. 
  3. With 4 people, things start getting really interesting. I take one seat. There are 3 seats remaining. If you take the seat to my left or right, you are next to me. If you take the seat across from me, that is the only case where you are not next to me. 
  4. With 5 people, again I take one seat, the seats next to my seat on the left and right are next to me, and the remaining (5-3=) 2 seats are the ones that are not next to me. 
  5. Making an inductive leap in reasoning, with N seats, there are N-1 seats after I take one seat, of these, 2 seats are next to me on my left and on my right respectively, and the remaining N-3 seats are not next to me. 
So, to summarize, with N seats, if you sit in N-3 of those N seats, you are not next to me, in 2 of those N seats you are next to me. Given I take one of the N seats, you are next to me when you take 2 of the N-1 seats, not next to me otherwise. Nice, elegant solution from first principles to an interesting combinatorics problem that is often asked in interviews.

No comments:

Post a Comment