2
$\begingroup$

let's say we live in a "very strange" world of Facebook, in which everyone has $1000$ friends. In addition, every $n$ people will have exactly $\lceil{1000 * (\frac{1}{10})^{n-1}}\rceil$ friends in common if $n \leq 3$, not more than a friend if $n$ between (inclusive) $4$ and $1000$ and $0$ otherwise. How many people are there in this world? If there can be more than an answer, what is the lower and upper bound for this number?

PS: Friends and self are excluded from friends of friends.

PS2: I don't know the answer either :)

PS3: Assumed that there must be at least a person in this world

Edited:Just found a "bug" for this problem, say I'm A and my friends are A1, ..., A1000, friend in common of A, A1, A2, A3, A4 must be subset of friend in common of A1, A2, A3, A4, which is $A$.

I need to change the statement of the problem... :(

  • 0
    @mjqxxxx: very i$n$teresti$n$g idea! on the other hand, will we have one answer or the answer will be bounded?2011-12-06

1 Answers 1

3

Answer to the original problem: There are no people in this world. If there is one person, he has 1000 friends. Choose 4 and call them $a,b,c,d$ They have exactly one mutual friend, call him $e$. Then $a,b,c,d,e$ have a mutual friend, call him $f$. But then $f$ is another mutual friend for $a,b,c,d$.

For the new problem, if such a world exists (I suspect not) the population is $9991$. Choose one individual $a$ and consider how many people are at each distance from $a$. As $a$ has $1000$ friends, there are $1000$ at distance $1$. Each of them has $100$ friends among this batch to get $100$ mutual ones with $a$. So they each have $899$ friends at distance $2$ from $a$, giving $899,000$ edges between distance $1$ and distance $2$ people. Each person at distance $2$ has $100$ friends at distance $1$ so they have the proper mutual friends with $a$, so there are $8990$ at distance $2$. There are none farther away, as everybody has $100$ mutual friends with $a$. As I have not constructed the graph satisfying all the constraints, it may not exist. They look hard to me.

  • 0
    @zfm: you don't know that it isn't buggy unless you know an answer. There may be no solution as stated. You are right that you have excluded this answer.2011-12-07