A problem by F. Nazarov, from the November/December 1994 issue of Quantum:
A person with fewer than 10 acquaintances is unsociable. If all your acquaintances are unsociable, you’re a weirdo. If all acquaintanceships are reciprocal (that is, if you know me then I know you), prove that unsociable people outnumber weirdos.
|
SelectClick for Answer> |
Consider three groups of people: N contains unsociable weirdos, W contains all the other weirdos, and U contains all the non-weird unsociable people. Let n, w, and u be the number of people in each of these groups, correspondingly, and let a be the number of pairs of acquaintances, each containing one person from W and another from U. We need to prove that w + n u + n, or w u.
Well, no one in N can have an acquaintance in W, since weirdos don’t associate with sociable people. Since acquaintanceship is reciprocal, this means that each of the people in W is finding all their numerous (10+) friends in U. So a is at least 10w.
A person in U can find friends anywhere but must have fewer than 10 of them. So a is less than 10u.
Combining these inferences, if 10w ≤ a and a u, then 10w u and w u.
|
