Are You a Fan of Dancing?
In a dancing night, there are 120 people including men and women participating (A person can dance to many). A group of three is called a " perfect three " if they dance to each other. After the night, it is said that for each 4 people there exists at least 1 "perfect three". How many pairs are there that have danced (at least)?
Note: The image is from the Visual Novel ' Rewrite '.
The answer is 7021.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Lemma: There can't be 2 separate pairs, for example (A;B) and (C;D), that haven't danced. Prove: Suppose there exists. If we choose any 3 among these 4, at least 2 of them are in a same pair, means that they haven't danced. So there's no "perfect three" among these 4, contradiction.
If all 120 people have danced to each other, the number of pairs is 2 1 2 0 × 1 1 9 = 7 1 4 0 . Suppose there exists 1 pair, for example A and B, that haven't danced. By lemma, all 118 other people have to dance to each other. Now, let A have danced to all these 118, and B haven't danced to any. We will prove that there can't be fewer pairs. Because we are sure that these 118 have danced, let A haven't danced to one of them, for example C. Then A haven't danced to C, B haven't danced to a D different from C (D is also in the 118). This is a contradiction, because of the lemma.
So there can't be fewer pairs. The number of pairs (at least) is 2 1 1 8 × 1 1 7 + 1 1 8 = 7 0 2 1 .