Suppose there are $3000$ members in each of the clubs $X$, $Y$ and $Z$. Each member from each of these three clubs has at least $3001$ friends from the other two clubs altogether. Show that there are three members $A$, $B$ and $C$ from $X$, $Y$ and $Z$ respectively, that are pairwise friends.
This is a repost of a question that got deleted. I find it very interesting.
On
Considering the question from a strong induction standpoint, let $m=1, f=2$. Then there is one member of each club who is friends with both the members of the two other clubs. The statement is true in this condition. Considering when $m=2, f=3$, let $A_0,B_0$ be given members of $X,Y$ respectively such that $A$ is friends with $B$. Each of $A_0, B_0$ must be friends with at least one member of $Z$, but suppose that there isn't a common friend in this case. That means that $A_0$ is friends with all members of $Y$ and $B_0$ is friends with all members of $X$ and that $A_0$ is friends with $C_0$ and $B_0$ is friends with $C_1$. Then we have $A_1$ who is friends with $B_0$ and $B_1$ who is friends with $A_0$. If we suppose that $A_1$ is friends with $B_1$, then each of $C_0,C_1$ do not have $3$ friends, so we must instead have that both $A_1$ and $B_1$ are friends with each of $C_0,C_1$, and so we have $A_1,B_0,C_1$ and $A_0,B_1,C_0$ pairwise friendships.
Suppose the statement is true for all $n\gt2$, with $m=n, f=n+1$. So there are $m=n$ members of each club for a total of $3n$ club members, and each club member has $f=n+1$ friends not in their club, and there exist club members $A,B,C$ from $X,Y,Z$ respectively such that these members are pairwise friends.
Now consider the case $m=n+1, f=n+2$. There are $3n+3$ total club members, each having $n+2$ friendships outside their club. WLOG, choose members $A_0, A_1$ from club $X$. $A_0,A_1$ must each have at least one friend in each of $Y, Z$, suppose that all $n+2$ of these friends are either members of the same club or not friends with any other friends of $A_0, A_1$; choose $B_0, C_1$ from $Y,Z$ among these and assume that $A_0$ is friends with $B_0$ and $A_1$ is friends with $C_1$. Similarly, choose $B_1,C_0$ from $Y,Z$ such that $A_0$ is friends with $B_0, C_0$ and $A_1$ is friends with $B_1, C_1$ and $B_0$ is friends with $C_1$ and $B_1$ is friends with $C_0$.
If we remove these six from their respective clubs, we have a case where $m=n-1$. But we also have the possibility that there are remaining club members such that $f=n-2$ since from each club perspective, four members were removed from the other clubs. If there is any member remaining in any club such that their friendship counter has dropped by $4$ upon removing the above members, then that club member was part of a pairwise friendship and we are done. Supposing that there are remaining club members whose friendship counter dropped by $3$, note that any combination of three removed club members which are from only two of the clubs contains at least one friendship, and again there must be a pairwise friendship. This leaves the case of $f=n$, and in this case, we are down to one of the assumed scenarios from our induction, and it is already true.
Therefore, such a pairwise friendship must exist for all member counts $m$ with friendship counts in alternate clubs at $f=m+1$.
On
Here's my thought ( partly coming from the tags for the questions), lets make tables/arrays ( Note that the question, doesn't care about the number of friends in their own group):
$\begin {array}{c|c|c|c|} \hline clubs&X & Y & Z \\ \hline people &A & B & C \\ \hline \text {# friends in X}&0&1501&1500\\ \hline \text {# friends in Y}&1500&0&1501\\ \hline \text {# friends in Z}&1501&1500&0\\ \hline \end {array}$
As it wasn't specified, who these people were, they could be random people. Looking at the table though, we see that the total number of friends from the other two people not in that group total over 3000 there has to be some overlap. If one person has less in one group, than the other group, they need friends in the other there's even more overlap. For B and C, call this overlap person A. For B and A call this person C. Lastly, for C and A call this person B. were done as long as you make sure the sums of each column add to 3001 or higher it's inescapable. If friends in one group go down, the number in the other goes up. If of the people that overlaps goes down, in that overlap group, then the overlap in the other group goes up, to compensate. so there's an overlap with another person in in number of friends if they try to fix it with the person they aren't trying to avoid overlap with.
I think I got this after $3$ years, it seems to be extreme principle :)
Given a person $p$ let $f(p)$ be the minimum of the number of friends that $p$ has on eeach of the other two clubs.
Pick $p$ such that $f(p)$ is minimized and let $k=f(p)$.
So $p$ has $k$ friends on one club and at least $3001-k$ friends on the other club.
Pick a friend $q$ of $p$ on the side with $k$ friends. Notice that $q$ has at least $k$ friends on the third club (the one from which we have not selected a friend yet). Since $k+(3001-k)> 3000$ there must be a friend that is common to $p$ and $q$ in this club, so selecting such a person $r$ gives us the desired three people $p,q,r$.