## All Friends Inline

Suppose you go to a party. As the night goes the party gets more and more crowded so now the party host comes up with a cute idea to kick some people out: **try to line people up such that each person in the line knows the person standing right next to you on both sides**. The line starts with the party host (of course). She grabs Andy, who knows her for a long time. Andy is popular among the crowds and he knows many folks there. But he has to pick one, so he chooses Barbara, his sister, because he doesn’t want her to be kicked out of the party. And the line grows…

Let’s see what we can say about this kind of lines. Yes, lines. There are many possible lines. For example, if Barbara happened to know nobody besides Andy, then the line ends and everyone else other than the party owner, Andy and Barbara would need to head out. What if Andy didn’t choose Barbara, but chose one of his friends, say Beth, who also happened to have many acquaintances in the crowds, unlike Barbara who didn’t? So the line would go on. **So, many of this kind of lines possible, and it’s possible that someone won’t be able to get in line**.

One interesting thing you can say is that, **if you happen to be the last person in line, then your friends must have all been in line already**. So don’t worry about your friends being kicked out if you are the last person in line!

This is somehow not very intuitive to me. How can you be so sure? But think about it, if you had a friend who’s not yet in line, then she could have joined by your side and would hence have been the last one in the line. That’s not gonna happen because you are the last one.

Now that you know all your friends are already in the line, you can at least put forth a rough estimate that **the length of the line is at least equal to the number of your friend s**. That’s kind of intuitive, because if you have only one friend, and you are in the line, then your friend must be the second to the last, right next to you. But if you have say 20 friends at the party, then you could at least tell that the line ended by you is at least 20 people long, plus you.

(Propoition 1.3.1., GT)

## Reply