, 2016

Denote the people in the order of ascending age by $A_1, A_2, \dots, A_n$. Using induction on $n$ we show that regardless of the seating arrangement there are exactly $n-3$ newbie pairs.

In the base case of $n=3$ every person is adjacent to every other person so there are no newbie pairs.

For the induction step assume that any seating arrangement of $n$ people contains exactly $n-3$ newbie pairs and consider an arbitrary arrangement of $n+1$ people. We wish to show that there are exactly $n-2$ newbie pairs in this arrangement.

Removing the oldest person $A_{n+1}$ from the table, the induction hypothesis tells us that there are exactly $n-3$ newbie pairs left. Now let $A_{n+1}$ sit back down. All $n-3$ newbie pairs will still remain such because person $A_{n+1}$ was the oldest and does not affect the other pairs. Also, $A_{n+1}$ will not form any new pairs with any of the other people. If $A_{n+1}$ and $A_i$ are not adjacent there is at least one person on each of the two arcs between them that is younger than $A_{n+1}$.

Finally, consider the remaining pairs which were not newbie pairs before. Out of these only the pair seated next to $A_{n+1}$ turns into a newbie pair. Indeed, there is now one person between them that is older than both of them, namely $A_{n+1}$.

Therefore, this arrangement of $n+1$ people contains exactly $n-2$ newbie pairs. This concludes the induction step.