# How to derive a general formula for this problem? (pairs of people seated around a table)

$N$ people attend a dinner party and sit round a circular table.Each person knows only the people sitting immediately next to him and has to be introduced to everyone else.If the total number of pairs of people introduced to each other is $20$,then what is the value of $N$?

Is this a form of any well known problem?I could only of think of a brute-force solution,however I am inquisitive to know how to solve this for any number of pairs in an efficient manner.

ADDED:It seems like I have understood the pattern,for any $N$ the number of pairs of introduction is given by $(N-3)+(N-3)+(N-3)-1+(N-3)-2+\cdots+2+1$ by using this idea the solution of the above problem should be $N=8$.

-

Each person is introduced to $N-3$ others. As there are $N$ people, that would make $N(N-3)$ introductions, but each has been counted twice-once from each side. So we have 20=$\frac{N(N-3)}{2}$, which has roots $8, -5$.

-
I did the same in a bit different way:$20 = 1+2+3+\cdots+(N-3)+(N-3)\Rightarrow (N-8)(N+5)=0$... hence the answer. – Quixotic Aug 29 '11 at 12:40
$+1$ and accepted.Reading your answer makes me feel a bit silly:P,I generated answers for first few $N$'s and tried to identify the pattern but all I am supposed to do just to think reasonably! – Quixotic Aug 29 '11 at 12:45
@FoolForMath: I don't see how you take the sum to $(N-8)(N+5)$-the sum from $1$ to $N-3$ is $(N-2)(N-3)/2$ and adding the last $N+3$ takes us to $N(N-3)/2$. The idea of counting each intro works sometimes, but here it is a bit hard to convince yourself you have the endgame right. – Ross Millikan Aug 29 '11 at 12:50
Okay,so $$1+2+3+\cdots+(N-3)+(N-3)=20 \implies\frac{N(N-3)}{2}=20 \implies$$ $$N^2-3N-40=0 \implies(N-8)(N-5)=0$$ (Hoping I haven't committed any mistake in algebra! ) – Quixotic Aug 29 '11 at 15:08
@FoolForMath: I was looking a step earlier. You are right. – Ross Millikan Aug 29 '11 at 19:22

Let $x$ be the number of introductions.

Suppose that everyone must be introduced to everyone else. Do this as follows. (i) Everyone is introduced to her left neighbour ($N$ introductions); (ii) Every pair of non-neighbours is introduced ($x$ introductions).

It follows that $$\binom{N}{2}=N+x,\qquad\text{and therefore}\qquad x=\binom{N}{2}-N=\frac{N^2-3N}{2}.$$

Now we solve the equation $$\frac{N^2-3N}{2}=20.$$ The only admissible solution is $N=8$.

-

Total introductions needed(if nobody knows anyone)=$n\choose 2$; but since a person knows the person next to him, therefore introductions needed=${n\choose 2}-n$ which is given to be $20\implies \frac{n(n-1)}{2} - n=20\implies n^2-3n-40=0\implies n=8$.

-

$nC2 - n = 20$

$n(n - 1)/2 - n = 20$

$n(n - 1) - 2n = 40$

$n^2 - 3n - 40 = 0$ $n^2 - 8n + 5n - 40 = 0$ $n(n - 8) + 5(n - 8) = 0$

$(n - 8)(n + 5) = 0$

$n = 8$ or $n = -5$

now n is positive and greater than $3$ ($3$ people needs no introduction) , so we take $n = 8$

-
For 4 people around a table we have 4c2 -4 = 2 i.e. 2 introductions. – Rajesh K Singh Jul 11 '12 at 12:58
An introduction involves 2 person. nC2 is the number of introductions among n people taken 2 at a time. – Rajesh K Singh Jul 11 '12 at 13:17
An introduction involves 2 person. nC2 is the number of introductions among n people taken 2 at a time. Here (A introduced to B) and (B introduced to A) is the same introduction but counted twice in nC2. That is in all n introductions have been counted twice as every one needs an introduction if n > 3. To eliminate these n false introductions we subtract n from nC2. – Rajesh K Singh Jul 11 '12 at 13:29