This was a relatively difficult puzzle, but I was surprised to see the number of people who attempted the answer. The best and the correct answer came from Alok Kuchlous and also from Challapalli. The one from Alok is very easy to understand, and hence reproducing it here:
Here is a solution with 10 nodes and that is the best possible.
Divide into two groups of 7 (G1, 1-7) and 3 (G2, A-C).
Make a 7 clique with G1. Remove one edge between ‘6’ and ‘7’. Now you have 5 nodes with degree 6 and 2 nodes with degree 5.
So they need 9 edges to make all of them degree 7.
Make a triangle with G2. All nodes in G2 have degree 2. Each of them needs 3 more edges to reach 5, totaling 9 edges.
Make the following edges
B4, B5, B6
C2, C3, C7
A1, A6, A7
Now ‘1-7’ have degree 7 and A-C have degree 5.
Proof that this is best possible.
– Cannot be done with 1 degree 5 node because all 7 degree nodes need at least 1 more neighbor.
– Cannot be done with 2 degree 5 nodes, because number of odd-degree nodes has to be even.
Also reproducing the answer from Anirudh who had contributed this puzzle!
For convenience, let’s call call the seven people at the party who each know seven others the Pontipee brothers. Since each Pontipee only has six brothers, each of them must know at least one person other than another Pontipee. This fact forces an eighth person to be at the party. This person knows at most five of the Pontipees, but all seven need to know at least one other party-goer, so we must have a ninth person as well. And we can’t stop here, since this would entail 7(7) + 2(5) = 59 instances where one person knows another, when the total must be even since knowing is mutual, bringing the minimum up to ten.
In fact it is possible to arrange such a party with ten people: call the Pontipees P1 through P7 , and let each of them know all the others except for P6 and P7 , who know the rst ve but don’t know each other. Call the remaining three people at the party the Querklin sisters Q1 , Q2 and Q3 , who all know each other. Finally, let Q1 know P1 , P2 and P3 ; let Q2 know P4 , P6 and P7 ; and let Q3 know P5 , P6 and P7 . This satises all the conditions, so 10 is the answer.
Challapalli send a solution for proving why 10 is the minimum answer. To be honest, I could not understand it, but reproducing it for others:
Say there ‘x’ other people who knew 5 others each.
Now, consider a Graph(G) with (7+x) vertices each vertex representing a person and an edge between two vertices (A, B) represents A knows B.
Total vertices = (7*7 + x*5)/2
Which implies x must be odd.
To find minimum x. Lets consider a complete graph with 7+x vertices.
Total vertices = (7+x)(6+x)/2
Number of vertices to be taken out from the current to get G = (x^2 + 8x – 7)/2.
When x = 1, this number will be 1, which is not possible.
So any x > 1 and which is odd satisfies the condition. So minimum x is 3.
Minimum number of persons is 10.
Several others sent answers which were more than 10.
Hope you enjoyed the puzzle!
Alok Goyal's Puzzles Page 