Legitimate question : are you considered your own friend?

assumption: for each x, x is not befriend with x. for the sake of contradiction, assume every pairs of 30 chosen have odd number of mutual friends. for every pairs of person $i,j$, denote $f(i,j)$ their number of mutual friends of $i$ and $j$ (on assumption, $f$ is odd). then, summing $f$ over all choices of person, then clearly this sum is odd (because ${30 \choose 2}$ is odd. now, think of an edge whose endpoints are $u$ and $v$. note that this edge must have been counted in $\sum f$ as much as $\deg u + \deg v-2$. now, we have $\sum f(i,j) = \sum_{u,v \, connected} \deg(u)+\deg(v)-2$. Thus, $\deg(u)$ itself must be called as much as $\deg(u)$ times. this leaves us to $\sum f(i,j) = \sum \deg(u)^2 - 2(sth)\equiv \sum \deg(u) \pmod{2} = 2|E| \pmod{2} \equiv 0 \pmod{2}$. contradiction.

The above solution is flawed, since there are constructions for which $\sum{f}$ is odd. Consider, for example, the construction given by five disjoint copies of the following mini-graph: Begin with a vertex and label it $4$. Join it to four other vertices, two with label $1$ and two with label $3$. Join the two vertices labeled $3$, and connect both to a sixth and final vertex labeled $2$. Each vertex is now labeled with its degree, and $\sum{f}$ over this mini-graph is odd. Since no two MOPpers in different mini-graphs share any friends, the sum of $f$ over all pairs of MOPpers is five times an odd number, which is of course odd. Also, it does not matter at all whether we consider a person to be their own friend.

Here's a proof for all even $n$. Suppose, for the sake of contradiction, that all pairs of people have an odd number of common friends. Notice that this implies each person has an even number of friends - if some person had an odd number of friends, then consider the subgraph whose vertices are her friends and edges are the friendships among them. Since each of her friends has an odd number of common friends with her, each vertex of the graph has odd degree in the subgraph. But if each vertex has odd degree and there are an odd number of vertices, the degree sum of the graph is odd, which is absurd. Thus every person has an even number of friends. Consider the adjacency matrix $M$ of the graph; in linear algebra terms, we have that $M$ is an even-sized square matrix (total number of people is even), each column of $M$ has even sum (from the above), and $c_i \cdot c_j$ is odd for all $i \ne j$ (by hypothesis every pair of people have an odd number of common friends). In addition $c_i \cdot c_i$ is even from above, so over $\mathbb{F}_2$ we have \[M^TM = A - I\] where all the entries of $A$ are $1$. However plugging the $1$-vector into the LHS gives the $0$-vector (since $M$ has even column sum), while plugging the $1$-vector to the RHS gives the $1$-vector since $A$ has even dimension, contradiction. Thus for $n$ even, some pair of people must have an even number of common friends. It is fairly easy to provide a construction for odd $n$ where this fails. Join $k$ $C_3$s at a common vertex (this gives $2k + 1$ vertices); it is easy to check that any pair of people have an odd number of (exactly one, in fact) common friends. Hmm either I have overcomplicated this a good deal, or this problem is significantly more difficult than the others on the ELMO.

Let $V$ denote the given set of people, and let $n(P)$ denote the set of friends of $P$ that are in $V.$ Suppose that any two people in $V$ have an odd number of friends in common. Fix an arbitrary $P \in V$ and consider the quantity \[ \sum_{Q \in V, P \neq Q} |n(P) \cap n(Q)|.\]Since each term in the sum is odd (by hypothesis), the sum is congruent to $|V| - 1 \equiv 1 \pmod{2}.$ On the other hand, each friend $i$ of $P$ is counted $|n(i)| - 1$ times in the sum, once for each of his friends distinct from $P.$ Therefore, the sum is also equal to \[ \sum_{i \in n(P)} (|n(i)| - 1) \equiv \sum_{i \in n(P) \cup {P}} |n(i)| \pmod{2}. \ \ \ (*)\]With a more specific view, consider the quantity \[\sum_{Q \in n(P)} |n(P) \cap n(Q)|.\]Again, each term is odd, and the sum is congruent to $n(P) \pmod{2}.$ On the other hand, since friendship is mutual, we have that for any two $A, B \in n(P)$ that $A \in n(P) \cap n(B) \iff B \in n(P) \cap n(A)$, and we may pair up terms in this manner to obtain that the sum is also congruent to $0 \pmod{2}$, i.e. $n(P) \equiv 0 \pmod{2}$ for any $P \in V.$ But then the sum in $(*)$ is also congruent to $0 \pmod{2}$, a contradiction, for we had previously established that it was $1 \pmod{2}.$ Hence, such set $V$ does not exist and there must always be two people with an even number of friends in common.

hyperbolictangent wrote: Hmm either I have overcomplicated this a good deal, or this problem is significantly more difficult than the others on the ELMO. There's a "simpler way" but your method solves a more general problem anyway. For this particular problem, you can just do something along the lines of your first paragraph---fix a person $P$ and look at the subgraph induced by $P$'s non-friends.

proglote wrote: But then the sum in $(*)$ is also congruent to $0 \pmod{2}$ Why? I don't see the relation between the two sums.

Why not? Since $|n(P)| \equiv 0 \pmod{2}$ for any $P\in V$ , it follows all summands in (*) are $0\, \mod 2$... The solution given by proglote is OK.

Ah, that makes sense. Nice!

proglote wrote: On the other hand, since friendship is mutual, we have that for any two $A, B \in n(P)$ that $A \in n(P) \cap n(B) \iff B \in n(P) \cap n(A)$, and we may pair up terms in this manner to obtain that the sum is also congruent to $0 \pmod{2}$, i.e. $n(P) \equiv 0 \pmod{2}$ for any $P \in V.$ Then how would you deal the situation if $n(P)=1$? As you observed $A \in n(P) \cap n(B) \iff B \in n(P) \cap n(A)$ holds for any $A, B \in n(P)$, so you can make pairs $\lbrace n(P) \cap n(A), n(P) \cap n(B)\rbrace$ iff $2$ divides $|n(P)|$. But how do you know that? Of course $n(P)=1$ situation is possible: take 28 strangers, each of them knows nobody among 30 people, and a pair of friends. I look forward to a convincing and correct end of your proof.

Consider this as a graph. FTSOC, assume not. If a person $v$ has an odd degree, then one of $v$'s neighbors must have an even number of common friends (otherwise take the induced subgraph of $v$'s neighbors). Now, consider the adjacency matrix $A$ of the graph, and we work in $\mathbb{F}_2$. Since the degree of each person is even, the diagonal of $A^2$ is $0$. Furthermore, the rest of the elements in $A^2$ is $1$ due to two people having odd number of common friends. This will also mean that $A^4 = I$, or the identity matrix. Now, observe that $A\cdot (1,1,\ldots 1) = 0$. Therefore, the determinant of $A$ is $0$, so the determinant of $A^4 = I$ is $0$. Contradiction. Thus, two people have an even number of common friends.