2
$\begingroup$

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

$\endgroup$

4 Answers 4

Reset to default
5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Quixotic
    Aug 29, 2011 at 12:40
  • 1
    $\begingroup$ $+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! $\endgroup$
    – Quixotic
    Aug 29, 2011 at 12:45
  • $\begingroup$ @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. $\endgroup$
    – Ross Millikan
    Aug 29, 2011 at 12:50
  • $\begingroup$ 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! ) $\endgroup$
    – Quixotic
    Aug 29, 2011 at 15:08
  • $\begingroup$ @FoolForMath: I was looking a step earlier. You are right. $\endgroup$
    – Ross Millikan
    Aug 29, 2011 at 19:22
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ For 4 people around a table we have 4c2 -4 = 2 i.e. 2 introductions. $\endgroup$
    – HOLYBIBLETHE
    Jul 11, 2012 at 12:58
  • $\begingroup$ An introduction involves 2 person. nC2 is the number of introductions among n people taken 2 at a time. $\endgroup$
    – HOLYBIBLETHE
    Jul 11, 2012 at 13:17
  • $\begingroup$ 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. $\endgroup$
    – HOLYBIBLETHE
    Jul 11, 2012 at 13:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .