Question:
Three Englishmen and three Frenchmen each know one unique secret. Only one Englishman knows French, no Frenchman knows English. They exchange secrets via person-to-person calls so all know all secrets. What is minimum number of calls?
Three Englishmen and three Frenchmen each know one unique secret. Only one Englishman knows French, no Frenchman knows English. They exchange secrets via person-to-person calls so all know all secrets. What is minimum number of calls?
Show Hint
Model the problem as two cliques with a single bridge vertex.
Updated On: Jul 31, 2025
- 5
- 10
- 9
- 15
Hide Solution
Verified By Collegedunia
The Correct Option is C
Solution and Explanation
Calls within each language group share secrets internally: 2 calls within English group, 2 within French group. The bilingual acts as bridge: 1 call to transfer all secrets from one group to another, then additional calls to propagate new info within groups. Counting carefully gives 9 minimum.
\[
\boxed{9}
\]
Was this answer helpful?
0
0
Top Questions on Graph Theory
- A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, \( n \) is _______.
- Dijkstra's algorithm fails for graphs with _______.
- Assume G is a simple undirected graph and some vertices of G are of odd degree. Add a node \( v \) to G and make it adjacent to each odd degree vertex of G, then the resultant graph is sure to be _______.
- A subgraph H of a graph G is called a clique if _______.
- For a given graph G having \( v \) vertices and \( e \) edges which is connected and has no cycles, which of the following statements is true?
View More Questions
Questions Asked in CAT exam
- ABCD is a rectangle with sides AB = 56 cm and BC = 45 cm, and E is the midpoint of side CD. Then, the length, in cm, of radius of incircle of \(\triangle ADE\) is
- CAT - 2024
- Mensuration
- Two places A and B are 45 kms apart and connected by a straight road. Anil goes from A to B while Sunil goes from B to A. Starting at the same time, they cross each other in exactly 1 hour 30 minutes. If Anil reaches B exactly 1 hour 15 minutes after Sunil reaches A, the speed of Anil, in km per hour, is
- CAT - 2024
- Time, Speed and Distance
- The selling price of a product is fixed to ensure 40% profit. If the product had cost 40% less and had been sold for 5 rupees less, then the resulting profit would have been 50%. The original selling price, in rupees, of the product is
- CAT - 2024
- Profit and Loss
- Suppose $x_1, x_2, x_3, \dots, x_{100}$ are in arithmetic progression such that $x_5 = -4$ and $2x_6 + 2x_9 = x_{11} + x_{13}$. Then, $x_{100}$ equals ?
- CAT - 2024
- Arithmetic Progression
- A circular plot of land is divided into two regions by a chord of length $10\sqrt{3}$ meters such that the chord subtends an angle of $120^\circ$ at the center. Then, the area, in square meters, of the smaller region is
- CAT - 2024
- Mensuration
View More Questions