Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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... :(

share|improve this question

closed as not a real question by Quixotic, Asaf Karagila, Bill Cook, Zhen Lin, t.b. Dec 8 '11 at 6:14

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

Did you make this up? The rounding up does not help. –  Henry Dec 6 '11 at 14:47
The square parenthesis mean the floor function? In that case it is not enough to restrict to $n\leq 4$? –  Giovanni De Gaetano Dec 6 '11 at 14:48
@Henry: yes I made this up... Well it might not be very helpful, but without it, we may have a non-integer number of friend in common... –  zfm Dec 6 '11 at 14:51
@mjqxxxx: it's a riddle, everything can happen in a riddle :) –  zfm Dec 6 '11 at 15:03
Quick question - is Kevin Bacon in this world? –  The Chaz 2.0 Dec 6 '11 at 15:05

1 Answer 1

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.

share|improve this answer
this is exactly why I wrote that this problem buggy –  zfm Dec 6 '11 at 19:36
it's no more buggy, I can say that this answer is no longer valid :) –  zfm Dec 7 '11 at 14:31
@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. –  Ross Millikan Dec 7 '11 at 14:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.