For all possible answers of $B,$ for how many cards will $A$ be able to know the number above for sure if $m=2, n=4?$

Question

We are given $n$ cards. Each card has a unique number written on it. Players $A$ and $B$ play a game. Each turn $A$ chooses $m$ different cards. Then $B$ sees all the chosen cards and say a number from one of the cards (no need to tell which card this number is from). $A$ can play as many turns as they want. For all possible answers of $B,$ for how many cards will $A$ be able to know the number above for sure if $m=2, n=4?$

(Notice that 'know for sure' means $A$ knows the number and which card this number is from. For example, if $n=2,m=2$, $A$ can know $0$ number above the cards.

I have no idea how to start at all. I have a feeling that this question seems incomplete in the sense that some information is missing. But I do not know what.

Any hint is appreciated.

Answer 1

Partial Answer (to be completed):

Here's an alternate construction of the problem that might help:

Let us define $_nC_m$ as the subset of the powerset of $[n]=\{1,...,n\}$ of elements with cardinality $m$. And, let $\sigma$ be some permutation of $[n]$.

$B$ picks some choice function $f:\:_nC_m\to[n]$, and you are given $\sigma\circ f$.

$B$'s chooses $f$ in an attempt to minimize your knowledge of $\sigma$. How much of $\sigma$ do you know?

Answer 2

(The first part is for the specific case of $n = 2, m = 4$ only.
The second part is for $n = 2$.
For the third part, I don't know how to deal with $n > 2$. I would love to hear your thoughts.)

Let the cards be $a, b, c, d$.

Claim: A can only guarantee that he knows at least 1 card.

Proof that 1 is the upper bound.
Consider the mapping: $\{a,b\} \rightarrow 1, \{ a,c\} \rightarrow 1, \{ a,d\} \rightarrow 1, \{b,c\} \rightarrow 2, \{c,d\} \rightarrow 3, \{ d,b\} \rightarrow 4$.
This is satisfied by $ (1, 2, 3, 4) $ and $(1, 4, 2, 3)$, so all that $A$ knows is $ a = 1$. $_\square$

Proof that $A$ will know at least 1 card.
Main idea: If $A$ hears a number at least twice, then the card that appears in the intersection of these pairs, must be equal to this number.

Since $A$ hears 6 numbers out of 4 possible distinct numbers, hence he must hear at least 1 number at least twice. So he can determine at least this card. $_\square$

Note: This argument tells us to look at cases where the frequency is $(3, 1, 1,1)$, and hope to show that we can only determine 1 card, which turns out to be the worst case scenario described above. Otherwise, we would be able to determine at least 2 cards, since every other frequency has at least 2 values that are $ \geq 2$.

---

For $n=2, m \geq 3$, we can determine at least $m - 3$ cards. This is the best that we can do.

$m= 3, n = 2$. There are 3 pairs mapping to 3 numbers. The frequency $(1,1,1)$ might allow us to determine 0 cards. This is possible: the $\{b, c, d \}$ rotation of the worst case scenario above.

$m = 5, n = 2$. There are 10 pairs mapping to 5 numbers. The frequency $(4, 3, 1, 1, 1)$ might allow us to determine at most 2 cards. This is possible:
1) If the pair has $a$, map to 1.
2) Else, if the pair has $b$, map to 2.
3) For the remaining pairs on 3 cards, do the $\{ b,c,d\}$ rotation above.

Proof that $m - 3$ is an upper bound.
For the general $m \geq 3$, there are $\frac{ m (m-1) } { 2}$ pairs mapping to $m$ numbers. The frequency $(m-1, m-2, m-3, \ldots, 4, 3, 1, 1, 1 )$ might allow us to determine at most $m - 3$ cards. This is indeed possible using a mapping generalized from $m = 4, 5$. $_\square$

Lemma: $k$ distinct numbers can be heard at most $k (m-1) - {k \choose 2}$ times.
Set up the standard bijection with the complete graph on $m$ vertices. Each edge corresponds to a pair, each vertex corresponds to a card. The $k$ distinct numbers correspond to $k$ of the $m$ vertices. A number can be heard only if the vertex lies on the edge.
Since the $k$ vertices lie on exactly $k (m-1) - {k \choose 2}$ edges (Each vertex has $m-1$ edges, and we double count by the complete graph on $k$ vertices), hence the lemma follows. $_\square$.

Proof that $A$ will know at least $m-3$ cards.
Suppose that there are at least 4 values that are heard at most once. Then, the other $m- 4$ values are heard at least ${m\choose 2 } - 4$ times.
Since $ {m\choose 2 } - 4 > (m-4)(m-1) - { m - 4 \choose 2 } $ (by expanding the inequality), this contradicts the previous lemma.
Thus, at most 3 values are heard at most once, so at least $m-3$ values are heard at least twice, so we can determine at least $m-3 $ values. $_\square$

---

Now for $n > 2 $ .... this seems messy. I'm not familiar enough with the higher dimensional analogy of the graph theory edge bijection that we have for $n = 2$.

It is not immediately obvious that the above could generalize. The main concerns I have are
1) What is the analogue of the $\{ b, c, d \}$ rotation?
2) For $n=3$, a number could be heard $m-2$ times and still not uniquely determine the card. Can we increase this further? What happens for $ n > 3$?
3) What is the analogue of the lemma?