Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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$.

share|improve this question

4 Answers 4

up vote 5 down vote accepted

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$.

share|improve this answer
    
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  
$+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$.

share|improve this answer

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$.

share|improve this answer

$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$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.