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?

• Am I correct in assuming you deem the current answer still sub-optimal, given it's not accepted yet? – Tim Couwelier Oct 5 '15 at 6:47
• @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. – Gamow Oct 5 '15 at 7:43
• alright, fair enough. It's not like you know there's a better number achievable though? – Tim Couwelier Oct 5 '15 at 7:54
• @Tim Couwelier: I know the complete answer to this puzzle. – Gamow Nov 9 '15 at 18:30
• Sadly however, i have no clue on how to prove it's optimal beyond what I've tried thus far. – Tim Couwelier Nov 10 '15 at 13:23

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.

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

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.