11.4. In a company, some pairs of people are friends (if $A$ is friends with $B$, then $B$ is also friends with $A$). It turned out that for any selection of 101 people from this company, the number of pairs of friends among them is odd. Find the largest possible number of people in such a company.

(E. Bakayev, I. Bogdanov)
Answer: 102.

Solution: In all solutions below, we consider the friendship graph, where vertices are people in the company, and two people are connected by an edge if they are friends.

Consider 102 vertices, and construct the following graph on them. Connect one vertex $x$ to three others $v_{1}, v_{2}, v_{3}$. Divide the remaining 98 vertices into pairs and connect the vertices in each pair. The resulting graph has $98 / 2 + 3 = 52$ edges. When any vertex is removed, an odd number of edges is removed, so an odd number of edges remains. Therefore, the company described in the problem can consist of 102 people.

It remains to show that there is no such company of 103 people (then a company of more than 103 people is also impossible). Below we provide several different ways to do this; in each way, we assume, to the contrary, that such a company has been found.

First solution. There are $n = C_{103}^{2} = 51 \cdot 103$ ways to discard two vertices from 103, leaving 101. Number these ways from 1 to $n$. Let $a_{i}$ be the number of edges on the remaining 101 vertices in the $i$-th way; by assumption, all numbers $a_{i}$ are odd, and thus their sum $S$ is also odd (since the number $n$ is odd).

On the other hand, consider any edge $uv$. This edge is counted in the number $a_{i}$ exactly when vertices $u$ and $v$ are not discarded in the $i$-th way, that is, when some pair of the remaining 101 vertices is discarded. This happens in $k = C_{101}^{2} = 50 \cdot 101$ ways. Thus, each edge is counted in $S$ an even number of times $k$, so $S$ must be even. Contradiction.

Second solution. Call a vertex even if its degree is even, and odd otherwise. Consider two cases.

Case 1. Suppose the total number of edges in the graph is odd. Then, by discarding any pair of vertices, we must discard an even number of edges (to leave an odd number). On the other hand, if we discard vertices with degrees $d_{1}$ and $d_{2}$, the number of discarded edges is $d_{1} + d_{2}$ if these vertices are not connected by an edge, and $d_{1} + d_{2} - 1$ if they are connected. It follows that vertices of the same parity are never connected by an edge, and vertices of different parity are always connected.

Thus, if the graph has $k$ even vertices, the total number of edges is $k(103 - k)$, which is even. But we assumed that this number is odd - contradiction.

Case 2. Suppose the total number of edges in the graph is even. Similarly, we get that vertices of the same parity are always connected by an edge, and vertices of different parity are never connected. Therefore, if the graph has $k$ even vertices, the number of missing edges is $k(103 - k)$, which is even. Therefore, the total number of edges is $C_{103}^{2} - k(103 - k) = 103 \cdot 51 - k(103 - k)$, which is odd. But we assumed that this number is even.

Remark 1. Of course, there are other examples of a company of 102 people that satisfy the condition.

Remark 2. There is also another variation of the second solution.

Consider any 102 vertices and the induced subgraph on these vertices, let it have $k$ edges. By discarding any vertex from them (say, of degree $d$), we get 101 vertices with an odd number of edges $k - d$. Thus, the degree of any vertex in our subgraph has a parity different from the parity of $k$, that is, the degrees of all 102 vertices have the same parity.

Now consider the entire graph on 103 vertices. Call a vertex even if after its removal, the remaining graph has all vertex degrees even, and odd otherwise. Then two vertices of the same parity are connected to the same set of the remaining vertices, and two vertices of different parity are connected to sets of vertices that complement each other to the entire set of 101 remaining vertices. From this, it is not difficult to determine, as in the second solution, that the graph is either a complete bipartite graph or the union of two complete graphs. Further, one can proceed as in this solution.

Comment. The statement that in any graph, the number of vertices of odd degree is even, is accepted without proof.

Only the answer - 0 points.

Only an example of a company of 102 people satisfying the condition is provided - 1 point.

Noted only that to complete the solution, it is sufficient to show that a company cannot have exactly 103 people - no points are added. If this observation is missed in the solution - no points are deducted.

Proved only that a company cannot have 103 people - 6 points.

Below are some advances in proving this fact. Points for different advances do not add up; 1 point can be added for a correct example of a company of 102 people.

Proved only that in any company of 102 people satisfying the condition, all vertex degrees have the same parity - 2 points.

Proved that the graph is either a complete bipartite graph or the union of two complete graphs (as shown in the second solution) - 4 points.

If one of the above cases is missed (without sufficient reason) - 3 points instead of 4.

Only one of the two cases from the second solution is fully resolved - 4 points.