8
$\begingroup$

The database of mini-facebook only has space for the data of 100 participants. These 100 participants want to establish as many mini-facebook friendships among them as possible. However, mini-facebook has introduced the following set of ground rules:

  1. Mini-facebook friendships are always symmetric.
  2. Mini-facebook only accepts one mini-facebook friendship or mini-facebook un-friend request per second. If two or more requests arrive simultaneously, they are all rejected.
  3. Any mini-facebook friendship request must consist of four distinct participants $A,B,C,D$ (ordered) so that none of the four pairs $AB$, $BC$, $CD$, $DA$ are currently mini-facebook friends. Mini-facebook will then establish the new friendship $AD$.
  4. Any mini-facebook un-friend request must consist of two distinct participants $A,B$ that are currently friends. Mini-facebook will then delete the new friendship $AB$.

Question: What is the maximum number of mini-facebook friendships that can exist simultaneoulsy at any moment in time?

$\endgroup$
  • $\begingroup$ Am I correct in assuming you deem the current answer still sub-optimal, given it's not accepted yet? $\endgroup$ – Tim Couwelier Oct 5 '15 at 6:47
  • $\begingroup$ @Tim Couwelier: the current answers just guess what an optimal solution might look like, but there are no arguments why the solution should indeed be optimal. $\endgroup$ – Gamow Oct 5 '15 at 7:43
  • $\begingroup$ alright, fair enough. It's not like you know there's a better number achievable though? $\endgroup$ – Tim Couwelier Oct 5 '15 at 7:54
  • $\begingroup$ @Tim Couwelier: I know the complete answer to this puzzle. $\endgroup$ – Gamow Nov 9 '15 at 18:30
  • $\begingroup$ Sadly however, i have no clue on how to prove it's optimal beyond what I've tried thus far. $\endgroup$ – Tim Couwelier Nov 10 '15 at 13:23
7
$\begingroup$

Building on Ivo Beckers' answer:

Out of the 4950 possible friendships (100 x 99 / 2), 197 of them cannot occur. Those 197 are B with 98 others, C with 98 others, and B-C.

So I wondered if there was improvement to be made, and I think there is:

Form groups like this:
B - random1 - C - random2.
Neither of the 4 exists already, so B is connected to random2 now.

Repeat so for any of the other 96 options (100-B-C-random1-random2) for random2.
This implies we've made another 97 matches, for a total of 4753 + 97 = 4850

Now can we take this further? Can we make combinations that create links for C?
They would have to look like this: C - random1 - random2 - random3
there are however no options left for 'random2' which isn't linked to any of the others.


To go beyond that: Can we link B and C? Combination would have to be like B - random1 - random2 - C. There are no 'random1' and 'random2' left from the pool that are unlinked, nor is there a B-random1 connection possible.

$\endgroup$
  • $\begingroup$ Nice find. I think you're right $\endgroup$ – Ivo Beckers Sep 23 '15 at 12:31
3
$\begingroup$

My guess is

$97 + 96 + 95 + ... + 1 = (97*98)/2 =4,753$

If you do it like this

set aside two people, call them B and C. Then interconnect everyone else using B en C as the middle two arguments of the friendship. The number of connections will be like this: the first person connects with the 97 other people that are not B or C, the second with everyone except the first, and so on.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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