How many parties do I have to throw to detect potential couples? Given $n$ groups of people $P_1,\dots,P_n$. For simplicity assume that each group of people contains $k$ persons ($|P_i| = k$) and no person is in more than one group ($P_i \cap P_j = \emptyset$). Therefore we have $kn$ different persons.
We would like to determine for each two persons from different groups whether they like each other. To do so we can throw a party and invite $n$ persons. Whenever two persons are at the same party we get to know whether they like each other. To make parties more interesting we decide that we always invite one person from each group. Since we have $n$ groups this means there will never be two persons from the same group at the same party. What is the minimal number $z$ of parties we have to throw in terms of $k$ and $n$ in order to answer this question? 
For example, if $n=k=2$ then $z=4$. Observe that there can be at most $k^n$ different parties (two parties are different if their guest lists are not identical) and therefore $z \leq k^n$. Also, we want to know $k^2 \cdot \binom{n}{2}$ bits of information and one party reveals at most $\binom{n}{2}$ bits. This means $k^2$ is a lower bound and therefore $k^2 \leq z \leq k^n$. 
 A: This is a partial answer that significantly improves the upper bound.
At first note that $z = 0 < k^2$ for $n \le 1$. $\ddot\smile$
For $n = 2$ it is possible to reach the lower bound of $k^2$ parties that is equal to the trivial upper bound.
In graph theory terms I would say we need to cover all edges of complete $n$-partite graph $G(n, k)$ (with parts of equal size $k$) with cliques of size $n$. Let's show that $(n - 2) k^2$ cliques would be enough for $n \ge 3$, so this is a new upper bound.
Let $n = 3$. Then we have $2k$-regular $3$-partite graph $G(3, k) = K_{k, k, k}$. Let's show that graph $K_{k, k}$ has $1$-factorization.
By Hall's marriage theorem it has perfect matching. Removing all edges of perfect matching we again get regular bipartite graph and so on. Therefore we have $k$ perfect matchings that contain all edges between two parts of our $K_{k, k, k}$. Now for each vertex $v$ of the third part we take one perfect matching $M$ of these $k$ and for each edge $\{\,u, w\,\} \in M$ of this matching we take clique $\{\,v, u, w\,\}$. Then we have $k^2$ cliques that cover all edges of $K_{k, k, k}$. This is the base of induction.
Suppose that for $n = m$ all edges of $G(m, k)$ can be covered by at most $(m - 2)k^2$ cliques. Then for $n = m + 1$ we can add any vertex from the last part to the same $(m - 2)k^2$ cliques and add $k^2$ cliques as follows. For each vertex from the last part take the first vertex from each other part, then take the second vertex from each other part and so on for $k^2$ cliques in total. (I. e. each of $k$ vertices of the last part has $k$ edges to each other part.)
Thus $k^2 \le z \le (n - 2)k^2$ for $n \ge 3$. Both lower and upper bounds are not sharp still if $n > 3$. For example for $n = 4$ and $k = 2$ it is possible to take only $6$ cliques that is between $k^2 = 4$ and $(n - 2)k^2 = 8$.
A: Here's another partial answer. It's possible to achieve the lower bound of $k^2$ when $k$ is prime and $n \le k$. In general, if $p$ is prime and $p \ge \max\{n,k\}$, then $p^2$ parties suffice, but I'll prove the other claim first.
Assume $k$ is prime and $n \le k$. Number people within each group from $0$ to $k-1$. Then we choose the parties as follows:


*

*Choose any $a$ and $b$ between $0$ and $k-1$. 

*From group $P_i$, invite person number $a+bi \bmod k$.


Then person $x \in P_i$ and $y \in P_j$ will see each other at the party for which
$$
\begin{cases}
  a + bi \equiv x \pmod k\\
  a + bj \equiv y \pmod k
\end{cases} \implies
\begin{cases}
  a \equiv (yi-xj)(i-j)^{-1} \pmod k\\
  b \equiv (x-y)(i-j)^{-1} \pmod k
\end{cases}
$$
As long as $i \ne j \pmod k$, which is true if $1 \le i,j \le k$ and $i \ne j$, we will have a solution, so the two people will be together at some party.
When $k$ is not prime, this will still work as long as $n$ is less than the size of the largest possible subset $S \subset \{1,2,\dots,k\}$ where $\gcd(i-j,k) = 1$ for all $i,j \in S$. In that case, we can just renumber the groups to have indices from the set $S$. I don't have great intuition for how big $S$ can be.
Also, in general, if we take any prime $p$ such that $p \ge \max\{k,n\}$, then we can use this method to "detect all couples" in $p^2$ steps. Just add $p-n$ fictional groups and $p-k$ fictional people to each existing group, and then run the algorithm above. 
Whenever it tells us to invite someone from a fictional group, ignore that; whenever it tells us to invite a fictional person from a non-fictional group, invite a real person from the same group. The algorithm tests all pairs of people, real and fictional, in $p^2$ steps; we've replaced some fictional people by real people, but this doesn't change that all real pairs of people will be tested.
