9
$\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$
5
  • $\begingroup$ Am I correct in assuming you deem the current answer still sub-optimal, given it's not accepted yet? $\endgroup$ Oct 5, 2015 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, 2015 at 7:43
  • $\begingroup$ alright, fair enough. It's not like you know there's a better number achievable though? $\endgroup$ Oct 5, 2015 at 7:54
  • 1
    $\begingroup$ @Tim Couwelier: I know the complete answer to this puzzle. $\endgroup$
    – Gamow
    Nov 9, 2015 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$ Nov 10, 2015 at 13:23

3 Answers 3

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$
1
  • $\begingroup$ Nice find. I think you're right $\endgroup$
    – Ivo
    Sep 23, 2015 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$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Whoa, a nice solution! And a nice presentation style as well. $\endgroup$
    – justhalf
    Feb 20, 2022 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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