# Friends Problem (Basic Combinatorics)

Let $k$ and $n$ be fixed integers. In a group of $k$ people, any group of $n$ people all have a friend in common.

1. If $k=2 n + 1$ prove that there exists a person who is friends with everyone else.

2. If $k=2n+2$, give an example of a group of $k$ people satisfying the given condition, but with no person being friends with everyone else.

Thanks :)

-
Again... what did you try? – Did Feb 23 '13 at 20:17
I tired working out the number of groups of n people amongst 2n+1 people but I can't get it – mathsnoob Feb 23 '13 at 20:19
You mean you do not know the number of ways of choosing n people amongst 2n+1? (And why did you try to work this out?) – Did Feb 23 '13 at 20:22
Umm... I thought it would be a good start but... Argh! Any idea how to solve this question? It's for a maths assignment due in a few days and if I don't do it my teacher will be real BLEAK – mathsnoob Feb 23 '13 at 20:23

For the second part, divide the $k$ people into $k/2=n+1$ pairs and let the two people in each pair not be friends, while everybody is a friend with all those people they are not paired with. As any group of $n$ people involve at most $n$ of these pairs, the remaining pair are friends with everybody in the group. (Lesson: Taking complements, i.e., working with the graph of non-friends, can be useful sometimes.)

Thinking about how this example just barely works might give you some ideas for proving the first part.

-
I'm horribly sorry, I do not understand what you are saying :| Can you please explain it as you would to a complete and utter imbecile retard? I am only 15 and have barely any experience with this kind of maths... – mathsnoob Feb 23 '13 at 21:09
Sorry, that might require a drawing, and I have no further time to spend here today. Maybe someone else will step up to the plate. – Harald Hanche-Olsen Feb 23 '13 at 21:13
Ugh,... anyway thanks Harald Hanche-Olsen, I appreciate your answer :D I might be able to work stuff out from that – mathsnoob Feb 23 '13 at 21:14

Let's start with a small example for problem 2, $n=2, k=6$. Number the people $1$ through $6$. As Harald Hanche-Olsen says, let $1$ not be friends with $2$, $3$ not friends $4$, and $5$ not friends with $6$. Because of the symmetry, there are only two kinds of sets of $n$ to see if they have a mutual friend: $1$ and $2$, who have $3,4,5,6$ as mutual friends, and $1$ and $3$, who have $5$ and $6$ as mutual friends.

The general idea is that any set of $n$ people only have $n$ non-friends among them, leaving $2$ people who are friends with all of them.

For problem 1, the key insight is that at least one person has two non-friends. Again take $n=2, k=5$. $1$ is not friends with $2$, $3$ not friends with $4$, but $5$ has to be non-friends with somebody, say $1$. Now the $n=2$ people $1,3$ don't have any friends in common. You will have to work on generalizing this. The idea is that if you take a group of $n$ people, you have $n+1$ non-friends if one of the $n$ is the person with two non-friends. That is everybody ($n+(n+1)=k$) so the group has no mutual friend.

-
Hmm... I sort of see what you're saying... Thanks for your contribution! :) – mathsnoob Feb 23 '13 at 21:53
@mathsnoob: I added a sentence. See if that helps. – Ross Millikan Feb 23 '13 at 22:22
Yea, sorta... So you're saying that question 2 is impossible? – mathsnoob Feb 23 '13 at 22:25
@mathsnoob: no, question 2 is quite possible. I gave a specific solution for $n=2, k=6$ and Harald Hanche-Olsen the general one. For question 1 we were asked to prove that it was impossible unless somebody was friends with everyone and that is correct. – Ross Millikan Feb 23 '13 at 22:27
I apologize for my lack of any mathematical knowledge or understanding whatsoever. Thanks to your contributions, I think I'm beginning to understand a little. Sigh... – mathsnoob Feb 23 '13 at 22:30

The first part of this is just an expansion of Harald Hanche-Olsen’s answer.

For the second part number the $2n+2$ people $P_1,\dots,P_{n+1},Q_1,\dots,Q_{n+1}$. Divide them into pairs: $\{P_1,Q_1\},\{P_2,Q_2\},\dots,\{P_{n+1},Q_{n+1}\}$. The two people in each pair are not friends; i.e., $P_k$ is not friends with $Q_k$ for $k=1,\dots,n+1$. However, every other possible pair of people in the group are friends. In particular,

• $P_k$ is friends with $P_i$ whenever $1\le i,k\le n+1$ and $i\ne k$,
• $Q_k$ is friends with $Q_i$ whenever $1\le i,k\le n+1$ and $i\ne k$, and
• $P_k$ is friends with $Q_i$ whenever $1\le i,k\le n+1$ and $i\ne k$.

In short, two people in the group are friends if and only if they have different subscripts. Clearly no person in the group is friends with everyone else in the group. Suppose, though, that $\mathscr{A}$ is a group of $n$ of these people. The people in $\mathscr{A}$ have altogether at most $n$ different subscripts, so there is at least one subscript that isn’t used by anyone in $\mathscr{A}$; let $k$ be such a subscript. Then everyone in $\mathscr{A}$ has a different subscript from $P_k$ and is therefore friends with $P_k$ (and for that matter with $Q_k$).

I hope to get to the first part a bit later.

-
@mathsnoob: I’m glad that it helped. I shouldn’t feel too bad about being a little slow to see it: this is not a particularly easy problem. And I find that especially with combinatorics problems it’s often the case that the wording of a solution has a very large effect on how easily I can follow it. – Brian M. Scott Feb 24 '13 at 7:24
@mathsnoob: Unless I’m simply not seeing something, it’s harder. In particular, I don’t think that Ross’s idea works without a lot more argument. I’m still thinking about it. – Brian M. Scott Feb 24 '13 at 7:40
@mathsnoob: I’ve given it some thought, but so far a solution has eluded me. I can prove that everyone has at least $n$ friends, and I can prove that if there isn’t someone who is friends with everyone else, then there is someone who has at least two non-friends, but neither of those observations leads to a proof in any straightforward way that I’ve yet seen. I may, as the Germans say, just have a board in front of my face and be missing something simple $-$ that can easily happen with combinatorial problems. I need to take a break from it and come back to it, but I will post if I get it. – Brian M. Scott Feb 24 '13 at 17:03
@mathsnoob: The problem with that idea is that in part (2) were just finding one example, so we could set up whatever friendships we needed to make it work. In part (1) we have to come up with an argument that works for all sets of friendships satisfying the conditions of the problem. It may not always be possible, for instance, to find $n$ pairs of non-friends. – Brian M. Scott Feb 24 '13 at 17:36
@mathsnoob: To be honest, I can’t guarantee that I will solve it. It requires coming up with the right insight, and I may simply not manage it, at least in any reasonable amount of time. This is a non-trivial problem, definitely contest-worthy. (And I’m going to have to get some sleep fairly soon now!) I’d love to solve it $-$ it’s thoroughly engaged my interest $-$ and I’ve not given up, but I make no promises. – Brian M. Scott Feb 24 '13 at 17:48