We have some cards that have the same look, but at the back of some of them is written $0$ and for the others $1$.(We can't see the back of a card so we can't know what's the number on it's back). we have a machine. we give it two cards and it gives us the product of the numbers on the back of the cards. if we have $m$ cards with $0$ on their back and $n$ cards with $1$ on their back, at least how many times we must use the machine to be sure that we get the number $1$? (15 points)
1. **Define the problem in terms of graph theory:**
   Let \( G(V, E) \) be a graph with \( m+n \) vertices, where each vertex represents a card. We do not know which vertices correspond to cards with 0 or 1 on their back. Placing two cards into the machine is equivalent to drawing an edge between two vertices and labeling that edge 0 or 1 depending on the machine output.

2. **Determine the worst-case scenario:**
   Suppose we add edges in \( G \) arbitrarily until we find an edge that gets labeled 1. At this point, we know that both vertices incident with that edge correspond to cards with 1 on their back. However, if \( G \) still contains an independent set of size \( n \), we could shuffle the cards around so that the cards with label 1 are on the vertices of the independent set. This implies that all edges in \( G \) would have label 0, meaning those moves won't suffice on this graph.

3. **Find the smallest number of edges in a graph \( G \) that contains no independent set of size \( n \):**
   This is equivalent to the complement graph \( \overline{G} \) having the maximum number of edges and no \( n \)-clique. According to Turán's theorem, the Turán graph \( T(n+m, n-1) \) is an \( (n-1) \)-partite graph with the size of the parts differing by at most 1.

4. **Calculate the number of edges in the complement of \( T(n+m, n-1) \):**
   The complement of \( T(n+m, n-1) \) is the disjoint union of \( n-1 \) cliques whose sizes differ by at most 1. If \( n+m = q(n-1) + s \), then this graph has:
   \[
   \binom{q+1}{2}s + \binom{q}{2}(n-s-1)
   \]
   edges. The strategy is to split the cards up into \( n-1 \) piles whose sizes differ by at most 1 and test all pairs of cards in each group.

5. **Determine the minimum number of tests required:**
   To ensure that we get at least one edge labeled 1, we need to test all pairs of cards in each group. The number of tests required is given by the number of edges in the complement of \( T(n+m, n-1) \).

The final answer is \( \boxed{ \binom{q+1}{2}s + \binom{q}{2}(n-s-1) } \).