The mini-facebook puzzle

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

Why can't we be friends?

We'll show that it's impossible to exceed

4850 friendships.

Why can't we be (un)friends?

First of all, un-friending is useless for friendship maximization.

Indeed, consider a sequence of valid friend or un-friend requests that includes an un-friending of participants A and B. Consider a second sequence obtained by removing this un-friend request and the friend request that added this friendship. The second sequence obtains the same end result as the first sequence while using one fewer un-friend request, and it is valid because a missing friendship does not obstruct any new friend requests.

From now on, we only consider friend requests.

Why can't we be (inverted) friends?

Actually, that was a lie.

For convenience, let's invert the notion of friendship, so that everyone starts as friends and only makes un-friend requests. (We'll only consider un-friend requests from now on, promise!)

At the start, all 100 participants are friends with every other participant. A valid un-friend request takes a 4-cycle of friends A-B-C-D(-A) and un-friends one of its edges A-D. This is equivalent to the original formulation of the problem, where our new goal is to minimize the number of friendships.

Why can't we be (time-reversed) friends?

Ok, I lied again. To establish a useful result, let's reverse time, so that we start with a small number of friendships and only make friend requests. A valid friend request takes a 3-chain of friendships A-B-C-D and adds the friendship A-D.

A useful result

Consider the undirected graph where participants are vertices and friendships are edges. Our goal is to establish that the graph will always be disconnected or bipartite if we start with fewer than 100 friendships and make friend requests.

Suppose we start with fewer than 100 friendships among our 100 participants. We case on whether the corresponding friendship graph is connected.

Case 1: The graph is not connected. Observe that every new edge added is between two vertices that are already connected, so the graph will never be connected.

Case 2: The graph is connected. Because it has fewer edges than vertices, it must be a spanning tree. In particular, it is bipartite. Suppose we can add an edge A-D to a bipartite graph with a vertex partition into independent sets U and V. Then there exists a 3-chain A-B-C-D. If A is in U, then B is in V, C is in U, and D is in V. Conversely, if A is in V, then D is in U. Either way, the graph is still bipartite after adding the edge A-D. Therefore, our original graph will always be bipartite.

We have shown that the original graph is disconnected or bipartite, and that it will therefore always be disconnected or bipartite.

Un-reversing

Now we can un-reverse (re-reverse?) time to get back to our original (actually inverted) problem. We start with all 100 participants being friends with every other participant. The corresponding friendship graph is a 100-clique, which is clearly connected and not bipartite, so (the contrapositive of) our useful result shows that we can never obtain fewer than 100 friendships through un-friend requests.

Un-inverting

Finally, let's un-invert the problem. There are a total of 100 choose 2 = 4950 possible friendships among all 100 participants, so we can never exceed 4950 - 100 = 4850 friendships.