Thread: Matching problem View Single Post
2021-06-02, 19:50   #4
Walter

"Walter S. Gisler"
Sep 2020
Switzerland

3×5 Posts

My approach would be to formulate the problem as a 0-1 linear program.

We will have variables $x_{ij} \in \{0,1\}$ which are 1 if letter $i$ matches with envelope $j$ and 0, otherwise.

Clearly, every assignment of letters to envelopes would fulfill the following constraints:

$\sum_{i\in I} x_{ij} = 1 \: \forall j \in J$
$\sum_{j\in J} x_{ij} = 1 \: \forall i \in I$

If we solve this problem we will get a unique assignment and we can receive the number of correct guesses, which we can denote as $c$. With that, we can add one new constraint every time this hint is given. Assuming our previous solution is given as a set of $ij$ pairs, denoted as $S$, this additional constraint can be expressed as follows:

$\sum_{ij \in S} x_{ij} == c$

This constraint essentially says that the correct solution includes $c$ of the matchings in $S$.

I believe this is the strategy that uses the given information the most efficient way possible and minimizes the number of attempts needed to uncover all of the correct pairs. Unlike using only the information from the last (or maybe last two "rounds") it combines all knowledge it retrieves in this process.

It is pretty hard to calculate the expected number of "rounds", but a simulation can help to quantify it. I have implemented this quickly in Python to get an idea. I have added a sample run to illustrate how this method choses the pairs in each round. It is clearly not what a human would do or in any way similar to the previous answer, but seems to be quite efficient.

I'm attaching a graph showing the frequencies (+cumulative frequencies) of the problem being "solved" after a given number of rounds. It can be seen that, if we have 10 letters and 10 envelopes, the expected number of iterations seems to be somewhere around 10. In my experiment (2000 random experiments), the highest number of tries I needed was 15 (just once), but the most common number seems to be 10 (473 times out of 2000 experiments).

I am also attaching the Python code (simulate.txt - seems like I can't upload .py files) in case anyone wants to experiment with it and adjust it to chose a different strategy.

Out of curiosity, I have also done a quick experiment and have adjusted the number of letter/ envelope pairs to 20. Obviously, there are a lot more possible assignments. Nevertheless, the expected numbers seems to be somewhere around 27, which is still quite decent.
Attached Thumbnails

Attached Files
 sample_output_n=10.txt (1.4 KB, 62 views) simulate.txt (3.3 KB, 62 views)