Least number of rounds to find all hidden pairs

Question

In my country there's a TV reality show in which $n+1$ men and $n$ women live in a house and, over the course of the show, they have to, as a group, find out who their 'match' is. $($In the actual TV show, $n=10)$. Each man is assigned to a single woman such that every woman save for one has a single man assigned to her; this exceptional woman therefore has two men assigned to her.

At the start of the game, no assignment is known to any player. Each round lasts a week, and on each round the players assemble into pairs (hence, one man is left out). Then, each pair that is a match is revealed to be a correct pair.

The players win when $n$ correct pairs are assembled in a round. What is the least number $r(n)$ of rounds that guarantees a win?

---

More generally, what kind of theory/bibliography is available to deal with questions like this? Information theory? Combinatorial group theory? I confess I'm at a loss here, and devising a winning strategy here by 'trial and error' seems like an approach whose feasibility decreases very fast as $n$ increases.

Answer 1

$n+1$ rounds are the smallest number to guarantee a win. To see that $n+1$ rounds are sufficient, place $n$ of the men in a circle, each facing one woman in a concentric circle. The $n+1$st plays no part yet. Pair the couples who are facing one another. It any of them are matched, remove them from the circle. Then rotate one of the circles one position counterclockwise, and repeat. After $n-1$ rounds, each woman left in the circle has been pair with $n-1$ different men, each of who is not her match, so there is only one man left in the circle who can be her match, and she will face him in the $n$th round. Any woman not matched in round $n$ must be matched with the $n+1$st man, so $n+1$ rounds suffice.

EDIT

I now believe that the necessity part of this proof is incorrect. I'm going to leave in my attempt at it, in hopes that someone can fix it.

To see that $n+1$ rounds are necessary, imagine that the producers of the show take an adversary approach. That is, they don't decide on the matches in advance, but make them up as the game goes along, in order to prolong the game as long as possible. Of course, at the end of the game, they must be prepared to announce all the matches, and they cannot contradict prior statements: once they say a couple isn't matched, it must stay unmatched.

In my original post, I described an adversarial strategy rather loosely, and the OP has rightly objected that I haven't demonstrated that no contradiction can arise. Here is a more sophisticated procedure, and a proof of correctness. The producers will use a flow network whose vertices are the men and women. At the start, there will be an edge of capacity $1$ from the source to each woman, an edge of capacity $1$ from each woman to each man, and an edge of capacity $1$ from each man to the sink. Clearly, the maximum flow in the graph is $n$. It is well-know that since all the capacities are integral, there is a maximum flow with integral flows, in this case, $0$ or $1$. As usual, we consider a man and woman as matched if the edge joining them has a flow of $1$. As the game progresses, the producers will modify the network to prevent any contradictions from arising.

I will prove that in each round the maximum flow in the network is equal to the number of unmatched women remaining, so that a complete matching is always possible. We will deal with the question of the "exceptional woman" later.

At each round, the producers examine the edges joining the current couple in turn. (If the couple has been paired previously, there is no such edge, as we shall see). For each such edge $e$, the producers run the max-flow algorithm to test whether the removal of edge $e$ from the graph will reduce the maximum flow. If not, $e$ is erased. If so, then the removal of $e$ can only reduce the flow by $1$, and a maximum flow must include a flow in $e$. The man and woman joined by $e$ are matched and removed from the graph. We now have a graph with one less woman, and a maximum flow of $1$ less, so the invariant is preserved.

Now the problem is to show that the players can't force this procedure to terminate prior to round $n+1$. I haven't been able to prove this, or anything close to it. Furthermore, I can show by example that it isn't true for $n=2$.

Suppose $n=2$ and let the women be A and B, and the men be a,b, and c. In the first round the players form the couples Aa, Bb. If the producers match both of these, the game is over, and if they match one, then the remaining woman pairs with c in round $2$ and the game ends. So, the producers make no match. In the second round, the players form the couples Ab, Ba. Now if the producers match both, the game is over, and if they match neither, then both a and b are unmatched, so the producers match Ab, say, then a is unmatched. Therefore, the producers cannot extend the game to three rounds. I think this may just be an anomaly and that my claim is true for $n>2$.

I find it hard to believe that this procedure doesn't last for at least $n$ rounds in general, but I haven't been able to prove it. I need to show that after $k$ rounds, there are at least $n-k$ unmatched women, or something like it, but I haven't been able to.

Answer 2

A very slight improvement on the circle idea of @saulspatz makes $n$ rounds sufficient for a win, as follows.

Terminology: There is one woman matched with 2 men. We'll call her the "special" woman, and her 2 men, the "special" men.

Algorithm: randomly set one man aside. This leaves $n$ men and $n$ women. Sit them in 2 concentric circles. In each round pair off each man and woman facing each other. Between each round the women move clockwise 1 space. (This happens even if a match is found.) After $n-1$ rounds, each man (except the one set aside) has met $n-1$ different women, and therefore he knows which woman he is matched with, because he has either met her, or, she is the only one he hasn't met.

• If the set-aside man is one of the "special" men, then the $n$ men in the circle match with different women. Just pair them up.

• If both "special" men are among the $n$ (i.e. not set aside), then they both know who the "special" woman is. Pair her up with one of them (doesn't matter which). For the other $n-2$ men in the circle, pair each up with his match. This leaves one woman whom none of the $n$ men are matched with. Pair her up with the set-aside man.

I'm not sure this is the best solution though...

Answer 3

This post is on the necessity (not sufficiency) side, and so I decided to start a new answer. Hope this is acceptable etiquette.

Claim: The game cannot be won in $\lfloor (n+1)/2 \rfloor$ rounds. In fact, stronger claim: For the first $\lfloor (n+1)/2 \rfloor$ rounds, no matter what pairings the players tried, the producer can say every such tried pair is a non-match (and still have a valid answer).

Obviously, this bound is extremely loose. It is offered here only as a sharing of ideas. In particular I hope the stronger claim above may be the basis for a much better lower bound.

---

The proof is an application of Hall's marriage theorem: https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem

The $n$ women and $n+1$ men form a bipartite graph, with an edge between every woman and every man. Let $E = $ the set of edges. If a pair $(w,m)$ is tried and revealed to be a non-match, then the edge $(w,m)$ is removed from $E$.

In $k$ rounds, each woman could have tried at most $k$ pairings, and have at most $k$ edges removed (out of the $n+1$ edges she started with). Similarly, a man could have tried at most $k$ pairings, and have at most $k$ edges removed (out of the $n$ edges he started with).

Now consider a subset $W$ of women, and consider the subset of men $M(W)$ that at least some woman $w \in W$ is still connected to, i.e. $M(W) = \{m: \exists w \in W, (w,m) \in E\}$. Hall's marriage theorem states that a matching exists (using the edges still in $E$) iff $\forall W, |W| \le |M(W)|$.

To exclude a man $m$ from $M(W)$, i.e. $m \notin M(W)$, the $|W|$ edges from $m$ to all $w \in W$ must be removed. This has 2 consequences:

• In $k$ rounds, the women in $W$ have removed at most $k|W|$ edges. It takes $|W|$ removed edges to exclude a man, so the number of excluded men $\le k|W| / |W| = k$, or equivalently, $|M(W)| \ge n+1 - k$.

• Meanwhile, it takes at least $|W|$ rounds to remove $|W|$ edges. So: $|W| > k \Rightarrow$ no man can be excluded $\Rightarrow |M(W)| = n+1 \ge |W|$.

So only the "small" subsets where $|W| \le k$ remains to be checked. For such subsets:

$$k \le (n+1)/2 \Rightarrow n+1 - k \ge k \Rightarrow |W| \le k \le n+1-k \le |M(W)|$$

I.e., when $k \le (n+1)/2$, Hall's theorem applies and a matching $F$ can be found in the remaining $E$ (even if every tried pair is a non-match and the corresponding edge has been removed). In this matching $F$, one of the men is not involved. However, he (like every man) has $n$ edges to start with, and at most $k < n$ have been removed, so he still has an edge $e$ left, and $F \cup \{e\}$ represents a valid answer to the original problem setting.

---

Further thoughts: the $(n+1)/2$ bound is tight for the stronger claim. In $k$ rounds, a subset of $k$ women could have exhaustively tried all pairings with $k$ men (e.g. the concentric circles idea). If all $k^2$ pairs are non-matches, these $k$ women must match with the remaining $n+1-k$ men, which is impossible if $k > n+1 - k,$ i.e. $k > (n+1)/2$. In other words, if the players try the maximum number of pairings each round, the producer must reveal some match(es) within the first $\lfloor (n+1)/2 \rfloor +1$ rounds.