2

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

zfm
  • 300
  • Did you make this up? The rounding up does not help. – Henry Dec 06 '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 06 '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 06 '11 at 14:51
  • @Student73: no, it was ceiling, actually the ones important is only n=1,2,3, but if I am A and my friends are A1, ..., A1000, there must be friend of common for A1, A2, ..., A1000, which is A, myself :) – zfm Dec 06 '11 at 14:52
  • You are right! :) – Giovanni De Gaetano Dec 06 '11 at 14:55
  • Is there a reason to think this state of affairs is even possible? – mjqxxxx Dec 06 '11 at 14:58
  • 2
    @mjqxxxx: it's a riddle, everything can happen in a riddle :) – zfm Dec 06 '11 at 15:03
  • 2
    Quick question - is Kevin Bacon in this world? – The Chaz 2.0 Dec 06 '11 at 15:05
  • So, every 1000 people have exactly 1 friend in common. Every 1001 people have exactly 0 friends in common. – GeoffDS Dec 06 '11 at 15:07
  • @Graphth: that was the idea... – zfm Dec 06 '11 at 15:08
  • bug found (written in the question), if someone can restate the problem (that's still same with my idea), please comment – zfm Dec 06 '11 at 15:12
  • @TheChaz: I don't get your question... Is it some kind of joke? – zfm Dec 06 '11 at 15:14
  • Yes, it is a joke, but refers to (what could be) a related riddle about degrees of separation between circles of friends. – The Chaz 2.0 Dec 06 '11 at 15:17
  • And, this is why you don't make up random problems. But, what you said doesn't make sense. You haven't told us the friends of $A_1$, $A_2$, $A_3$, $A_4$, so we don't know who the common friends of those 4 are. It is true that the common friends of those and $A$ must be a subset of ${A_1, \ldots, A_{1000}}$. But, if $A$ is not included, the friends of $A$ have little to do with it. I'm sure there is some bug in this problem, but I don't want to figure it out. – GeoffDS Dec 06 '11 at 15:22
  • I think it's an interesting question - er - riddle. Reminds me of the research that tried to demonstrate that in a chain of friends there are 6 persons on average in the entire world. So if John Doe wants to pass a message to Obama, the message will on avg pass through 4 more people (if John Doe is not a personal acquaintance of Obama that is...) – Count Zero Dec 06 '11 at 15:29
  • You ought to close this problem, or add a comment to the top at least, so that people don't come here and read through your question only to find you've essentially un-asked it. – Thomas Andrews Dec 06 '11 at 15:35
  • @ThomasAndrews: done... – zfm Dec 06 '11 at 15:40
  • @zfm: How about this: each person has $1000$ friends; each pair of people has $100$ friends in common; each triplet of people has $10$ friends in common; and every $k$-tuple of people with $k>3$ has at most $1$ friend in common. – mjqxxxx Dec 06 '11 at 15:44
  • @mjqxxxx: very interesting idea! on the other hand, will we have one answer or the answer will be bounded? – zfm Dec 06 '11 at 15:49

1 Answers1

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.

Ross Millikan
  • 374,822