The setup: Suppose we had a deck of $n$ cards numbered $1, 2, ..., n$. These cards are shuffled so that they are in random order. Our friend picks a card, looks at the number and then returns it back to the deck at a random position.
We then arrange the cards into a $p \times q$ matrix ($pq = n$).
$$ \begin{smallmatrix} a_1 & a_2 & \dots & a_p & \rightarrow r_1 & = & \sum(a_1, \dots, a_p) \\ a_{p+1} & a_{p+2} & \dots & a_{2p} & \rightarrow r_2 & = &\sum(a_{p+1}, \dots, a_{2p}) \\ \vdots & \vdots & \ddots & \vdots \\ a_{(q-1)p+1} & a_{(q-1)p+2} & \dots & a_{pq} & \rightarrow r_q & = &\sum(a_{(q-1)p+1}, \dots, a_{pq}) \\ \downarrow & \downarrow & & \downarrow & & & \\ c_1 = \sum(a_1 \dots a_{(q-1)p+1}) & c_2 = \sum(a_2 \dots a_{(q-1)p+2}) & \dots & c_p = \sum(a_p, \dots, a_{pq}) & \end{smallmatrix} $$
Information gathering rounds: We then have multiple rounds where information is provided. In each round, we are given only the row and column sums of the cards in the matrix (i.e., the sums $c_1,\dots, c_p$ and $r_1, \dots, r_q)$. The objective is to determine the position of the card chosen by our friend just using the row and column sums gathered from one or more information gathering rounds.
We may run as many information gathering rounds as we want to find the chosen card.
When a round is over, one row or column is selected at random by our friend and if it does not contain the chosen card, it is removed and set aside. We may collect the remaining cards back into a pile one row or column at a time (so those cards will remain in sequence in the reassembled deck). If we choose to collect the cards row-wise, we have to gather all cards row-wise (i.e., we cannot collect row 3 and then collect col 5) and similarly for column-wise. We may only decide which order the rows (or columns) will be collected (i.e., collect row 4, then row 2, then row 5 etc., is permitted). The process is repeated for the next round.
A simpler variant of the game: In this version the starting deck is in sequence order. When our friend returns the card, they insert it back in a random position. All the other rules are the same.
Questions:
Considering both variants of the game:
- Is it possible to determine the chosen card?
- If yes, what is a feasible strategy?
- Does an optimal strategy exist and if so, what is it?
Note: There is no source for this problem (that I know of). I came up with this problem formulation while studing sieves.