2max(m. n) + min(m, n) - 1, by math induction.

http://www.kalva.demon.co.uk/apmo/asoln/asol035.html

Also can't open it.

The result is max{2m+n,2n+m} - 1 I don't use induction to prove this problem. The key of this problem is finding a " acquainted model" that k can't not be max{2m+n,2n+m} - 2.

please, Can someone post full solution(not only results)? thanks.

Let m be larger of m,n. construct a 2m+n-2 graph with 2m-1 of the vertexes forming a complete graph and no other edge is connected. Obviously this don't have either m acquainted pairs or n unacquainted pairs. Now to prove 2m+n-1 works, induction beginning with m-n and 1. This case will obviously yield result 2(m-n)+1-1=2(m-n). The induction step is by increasing number of vertexes by 3 and m,n by 1 respectively. Since except for extreme cases we can find 3 vertexes with both connected pair and unconnected pair between them, take these 3 away and use the hypothesis gives the result.

greentreeroad wrote: Let m be larger of m,n. construct a 2m+n-2 graph with 2m-1 of the vertexes forming a complete graph and no other edge is connected. Obviously this don't have either m acquainted pairs or n unacquainted pairs. Now to prove 2m+n-1 works, induction beginning with m-n and 1. This case will obviously yield result 2(m-n)+1-1=2(m-n). The induction step is by increasing number of vertexes by 3 and m,n by 1 respectively. Since except for extreme cases we can find 3 vertexes with both connected pair and unconnected pair between them, take these 3 away and use the hypothesis gives the result. Thanks for nice solution=) But i have one question. Can you clear the last step of induction, how we can be sure that when we will put 3 vertex again we will find complete subgraph which will contain one more vertex than in 2-nd step? thanks.

You can generally find 3 vertexes in any graph that there are connected or unconnected segments among them.(except for some very extreme case such as every pair of them is friend...). Now, take these three vertexes away and using induction hypothesis.

I do the double induction with (n,n) and(n+k,n)

The induction proof is relatively standard, but here is a beautiful proof which does not rely on induction. The answer is $2\max(m, n) + \min(m, n) - 1$. I claim that this is minimal. Consider a complete graph with $2m + n - 2$ vertices. We create a clique of $2m-1$ people who all know each other, and then $n-1$ people who don't know anyone else. We can easily see that the largest matchings have sizes $m-1$ and $n-1$ respectively. Let the answer for $m$ and $n$ be $f(m, n)$. Now, I claim that we can always get $2\max(m, n) + \min(m, n) - 1$. Assume that $m > n$, since clearly $f(m, n) = f(n, m)$. Call acquainted people red and not acquainted people blue. Assume that we had a counterexample to the hypothesis. Then we will procedurally recolor edges until the largest red matching has size exactly $m-1$. This works, because the largest blue matching will not increase in size, and the largest red matching will increase in size by at most one at every move. Let the vertices be $I_1$, $I_2$, thru $I_{n+1}$ and $J_{1}$, $J_2$, thru $J_{2m-2}$. Assume that there is a matching between $J_1$ and $J_2$, $J_3$ and $J_4$, and so on and this is maximal. We then go down the line, like this: Let the vertex $V$ be a variable vertex. Start it as $I_1$. Then observe that at the beginning, $VJ_1$ and $I_2J_2$ are not both red, for if they were both red, we would have a larger matching. (replacing $J_1J_2$ with $VJ_1$ and $I_2J_2$). One of these therefore is a blue edge. If $V$ is part of the blue edge, let $V = I_2$ now. Otherwise, keep $V$'s value. We do it again with $VJ_3$ and $I_3J_3$. After doing this $n$ times, we will have an $n$-blue matching, unless $m = n$. In that case, we can employ a rather devious trick. After applying this procedure $n-1 = m-1$ times, we will have two vertices left over. If the edge between them is red, we have an $m$-red matching: combine this edge with the current red matching. If the edge between them is blue, we have a $n$-blue matching: combine this edge with the other $n-1$ edges. Hence, we are done and the answer is $2\max(m, n) + \min(m, n) - 1$.

Attachments:

The answer is $m + n + \max(m, n) - 1$. Interpret the situation as a complete graph with vertices as people and color edges red or blue depending on whether two people are acquinated; we are searching for an $m$-red or $n$-blue matching. For convenience let $a_{m, n}$ denote the answer. First we show $a_{m, n} > m + 2n - 2$. Consider a $K_{2n - 1}$ with blue edges and introduce $m - 1$ new vertices; color all the new edges red. It is clear no desired matching exists. Hence $a_{m, n} > m + 2n - 2$. Similarly $a_{m, n} > 2m + n - 2$, so $a_{m, n} \ge m + n + \max(m, n) - 1$. Now we show $m + n + \max(m, n) - 1$ vertices is sufficient. Claim. $a_{m + 1, n + 1} \le a_{m, n} + 3$. Proof. Consider a graph with $a_{m, n} + 3$ vertices. If it is monochromatic the claim is trivial; otherwise, there exists a non-monochromatic triangle $\mathcal{T}$. The graph on the remaining $a_{m, n}$ edges contains an $m$-red or $n$-blue matching; appending a red or blue edge from $\mathcal{T}$ gives the desired matching. Suppose $m \le n$. Using the claim $a_{m, n} \le a_{1, n - m + 1} + 3(m - 1)$. Since $a_{1, n - m + 1} = 2(n - m + 1)$, we deduce \[a_{m, n} \le 2(n - m + 1) + 3(m - 1) = m + 2n - 1 = m + n + \max(m, n) - 1.\]Similarly $a_{m, n} = m + n + \max(m, n) - 1$ also if $m \ge n$, completing the solution.

I'm having trouble seeing how in va2010's proof (in the first paragraph) we can procedurally recolor edges until the largest red matching has size exactly $m-1$. Why can't it have size less than $m-1$? In other words, how can va2010's algorithm guarantee we can attain $m-1$ red matchings?

We claim that the answer is $m+n+\max\{m,n\}-1$. Let's rephrase the problem statement. New Problem Statement: $G$ is a complete graph with $k$ vertices and each edge is either red or blue. If there are $n$ red edges with distinct endpoints or $m$ blue edges with distinct endpoints for any $G$, then find the minimum value of $k$. First, let's give a construction for $2n+m-2$ vertices where $n\geq m$. Consider the complete blue graph with $m-1$ vertices called $H_b$ and complete red graph with $2n-1$ vertices called $H_r$. Colour each edge between $H_r$ and $H_b$ into blue. We cannot find $m$ blue edges or $n$ red edges. Thus, $k\geq 2n+m-1$. Now, let $G$ be a graph with $2n+m-1$ vertices and suppose that there are no discrete $n$ red edges or discrete $m$ blue edges. Consider the maximum number of matchings among red edges. Let there be at most $l$ red edges, call these red edges' endpoints as $u_i,v_i$ where $1\leq i\leq l$. Let $S=G-\{u_i,v_i\}_{i=1}^{l}$. We see that $S$ is a complete blue graph. Pick two vertices $A,B\in S$, if there are at most $1$ blue edge between $A,B$ and $u_i,v_i$, then we would get $l+1$ discrete red edges hence there are at least $2$ blue edges. Note that $S$ has $2n+m-1-2l$ vertices. If $A_1,\dots,A_{2n+m-1-2l}$ are all elements of $S$, thenk there is a red edge between $A_1,A_2$ and $u_1,v_1$. Match them (WLOG $A_1$ is matched). After that, there must be a red edge between $A_2,A_3$ and $u_2,v_2$. If $2n+m-1-2l\geq l$, then by continuing this process we get $(2n+m-1-2l)-1$ pairs. However, $2n+m-2l-2\geq m$ which contradicts with our initial assumption. Suppose that $2n+m-1-2l<l$. By applying the same process, we get $l$ blue pairs between $S$ and $G-S$. Also there are $(2n+m-1-2l)-l$ vertices in $G-S$ which are not in a pair and between any of them there exists a blue edge. Thus, we can get $l+\lfloor \frac{(2n+m-1-2l)-l}{2}\rfloor=\lfloor \frac{2n+m-l-1}{2}\rfloor\geq \lfloor \frac{n+m}{2}\rfloor\geq m$ which gives a contradiction again as desired.$\blacksquare$