For given positive integers $a>b$, find minimum value of positive integer $n$ , such that there exist real numbers $a_1,a_2,\ldots,a_n$, with
- $a_i>0$;
- There are nonempty Disjoint multisets $P_1,P_2,\ldots,P_a$ such that $S(P_i)=b$ $\forall 1\leq i \leq a$;
- There are nonempty Disjoint multisets $Q_1,Q_2,\ldots,Q_b$ such that $S(Q_i)=a$ $\forall 1\leq i \leq b$.
Comment: $P_i\subset\{a_1,\ldots,a_n\}$ and $Q_i\subset\{a_1,\ldots,a_n\}$, also $S(A)$ is sum of all elements in $A$.
My attempt:
lets $P_1,\ldots,P_a,Q_1,\ldots,Q_b$ be vertices of graph. Each vertices are connected if their corresponding sets have common element. Obviously graph is bipartite ($P_1,\ldots,P_a$ on a left side and $Q_1,\ldots,Q_b$ on a right side). Using Hall's Theorem we have matching that covers right side.
After this I tried several things but I got nothing.
Please don't hesitate and suggest your own ides. Thanks!
Answer is $a+b-d$ where $d=gcd(a,b)$.
In the solution $a=a'd$ and $b=b'd$
Lets consider bipartite graph, as it is described above. Now Consider connected component of this graph. Lets say that $ P_{i_1},P_{i_2}... P_{i_p}$ are on a left side and $ Q_{j_1},Q_{j_2}... Q_{j_q}$ are on a right side. Since component is connected than $ P_{i_1}\cup P_{i_2} \cup ... \cup P_{i_p} = Q_{j_1} \cup Q_{j_2} \cup ... \cup Q_{j_q}$ so $ S(P_{i_1})+S(P_{i_2})+... S(P_{i_p}) =S(Q_{j_1})+S(Q_{j_2})+...+ S(Q_{j_q})$ which gives us $pb'=qa'$. which means that $a'|p$ so the number of components is at most $\frac{a}{a'}=d$ (because number of vertices right side is divisible $a'$ in every component, since there is $a$ vertices in total there can't be more than $d$ components because $(d+1)a'>a$).
So number of edges in Graph $E\geq a+b-d$, which is our answer.