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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a quantitative aptitude type of problem,

Amrita hosted a birthday party and invited all her friends and asked them to invite their friends.There are $n$ people in the party.Only Satyam is not known to Amrita.Each pair that does not include Amrita or Satyam has exactly $2$ common friends.Also,Satyam knows everyone except Amrita.If only $2$ friends can dance at a time,how many dance numbers will be there at the party?

a)$3n − 7$$\qquad\qquad\qquad$b)$2n + 5$$\qquad\qquad\qquad$c)$4n − 3$$\qquad\qquad\qquad$d)none of these.

This kind of problems are generally solved by solving for small cases and then just plugging the values into the options to identify the correct one,but I don't think I can understand the problem correctly,could anybody help me to understand this (preferably with an example)

ADDED: The correct answer as suggested by the problem setters is $3n − 7$.

share|cite|improve this question
I'm not sure I understand the question. Is it asking in how many ways the $n$ people can be paired up under the constraint that Amrita and Satyam are not paired with each other? – Austin Mohr Aug 13 '11 at 17:37
up vote 5 down vote accepted

After a good deal of experimentation, I’m inclined to think that the problem is not just poorly stated, but hopelessly defective. I’ve written up refutations of all the possibilities that occurred to me, in hopes that someone might be able to come up with one that I missed.

It’s helpful to translate the setting into graph-theoretic terms.

Let $G = \langle V,E \rangle$, where $V$ is the set of people at the party, and a pair $\{x,y\}$ is in $E$ iff $x$ and $y$ are acquainted. Let vertices $a$ and $s$ be Amrita and Satyam, respectively. The assumptions are that $\deg a = \deg s = n-2$, that $\{a,s\} \notin E$, and that for any $x,y \in V \setminus \{a,s\}$ such that $x \ne y$, $|N(x) \cap N(y)| = 2$. (Here $N(x)$ is the set of vertices adjacent to $x$.) For every $x \in V \setminus \{a,s\}$, $a,s \in N(x)$, so this last condition says that for any $x,y \in V \setminus \{a,s\}$ such that $x \ne y$, $N(x) \cap N(y) = \{a,s\}$. This implies that the maximum degree of any vertex in the induced subgraph $G'$ on $V' = V \setminus \{a,s\}$ is $1$: the components of $G'$ are isolated vertices and copies of $P_2$, the path graph on two vertices.

The next problem is to interpret the condition ‘only 2 friends can dance at a time’. One possibility is that strangers do not dance with each other. (This isn’t actually a possible interpretation in standard English, but there are indications in the wording of the problem that a non-standard variety of English is being used.) In more standard English it could mean that there is room for only one couple at a time to dance and that only friends dance with each other. Alternatively, it could mean that there is no restriction on the number of couples dancing at once, but in any dance at most one of the couples on the floor may be a pair of friends. I see no way to resolve this save by taking into account the question: ‘how many dance numbers will there be at the party?’ (I’m assuming that are friends and knows are synonymous; if they’re not, the problem statement is hopelessly defective.)

Unfortunately, while the condition imposes a limit of some kind on who can be on the dance floor at one time, nothing in the problem clearly specifies what goal is to be achieved. I can think of only two plausible goals: either every pair of friends are to dance at least once, or everyone at the party is to dance at least once. In either case we would presumably be looking for the smallest number of dances guaranteed to meet the goal.

The goal of getting everyone a dance can clearly be met with $n-2$ dances: Amrita dances with everyone but Satyam and one other person, and Satyam dances with that person. This clearly doesn’t match the supposedly correct answer of $3n-7$, so let’s consider the goal of having every pair of friends dance. On this interpretation of the question it makes no difference which interpretation of the condition we use, and the problem is really about the number of pairs of friends at the party.

There are at least $2n-4$ pairs of friends, namely, those that have either Amrita or Satyam as a member. If the answer is $3n-7$, we need to find $n-3$ more pairs of friends. Unfortunately, the problem statement ensures that there are at most $\lfloor (n-2)/2 \rfloor = \lfloor n/2 \rfloor - 1$ other pairs of friends. The only simple way that I can see to get $n-3$ more pairs of friends is for $G'$ to be a star graph: one person (clearly different from both Amrita and Satyam $-$ call him Sunil) knows everyone else at the party. Sunil’s friendships would provide the missing $n-3$ couples, but his existence is incompatible with the requirement that ‘[e]ach pair that does not include Amrita or Satyam has exactly 2 common friends’ whenever $n>4$: any two guests different from Amrita, Satyam, and Sunil have all three of those people as common friends.

The second of these interpretations is already incompatible with the answer $3n-7$ when $n=3$, since there are $3$ allowable sets, $\{\{a,x\}\}$, $\{\{s,x\}\}$, and $\{\{a,s\}\}$. Assume, then, that a set of couples is allowable only if exactly one couple are friends. When $n=4$, the only way to get $5$ sets is to assume that the two guests other than Amrita and Satyam are friends and that we’re actually counting only maximal allowable sets; in that case the $5$ allowable sets are $\{\{a,x\}\}$, $\{\{a,y\}\}$, $\{\{s,x\}\}$, $\{\{s,y\}\}$, and $\{\{a,s\},\{x,y\}\}$. Without the maximality requirement, the set $\{\{x,y\}\}$ would also be allowable, and if $x$ and $y$ weren’t friends, only the first four sets would be allowable.

The assumption in the case $n=4$ that $x$ and $y$ are friends presumably should generalize to a requirement that the number of friendships amongst the guests other than Amrita and Satyam be maximal. For $n=5$ that means (without loss of generality) the friendships $\{a,x\}$, $\{a,y\}$, $\{a,z\}$, $\{s,x\}$, $\{s,y\}$, $\{s,z\}$, and $\{x,y\}$, and it’s not hard to check that there are only $7$ maximal allowable sets, not $8$: $\{\{a,x\},\{y,z\}\}$; $\{\{a,y\},\{x,z\}\}$; $\{\{a,z\}\}$; $\{\{s,x\},\{y,z\}\}$; $\{\{s,y\},\{x,z\}\}$; $\{\{s,z\}\}$; and $\{\{x,y\}\}$.

If ‘will there be’ is actually intended to mean ‘can there be’, the question could also conceivably be asking how many different sets (or perhaps maximal sets) of couples can be formed if each couple in the set must be a pair of friends, or if at most one of the couples may be friends, or if exactly one of them must be friends. The first of these possibilities is already incompatible (in both versions) with the answer $3n-7$ when $n=4$. In that case let the vertices be $a,s,x,y$. If $x$ and $y$ are not friends, there are $6$ sets of friendly couples, $2$ of which are maximal; if $x$ and $y$ are friends, the numbers are $7$ and $3$, respectively.

share|cite|improve this answer

Your Answer


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.