General Principles of the Approach
So I've started trying to tackle this myself and here are a few things I am observing and considering.
First thing is I can think of two possible strategies for trying to solve this problem. (not using spoilers since this is just speculation).
- At each step try to minimize the total number of possible solutions in the worst case scenario as posted in a prior blog looking at this problem.
- At each step try to minimize the entropy of the worst case scenario.
I see the rationale for minimizing the number of possible solutions as you are effectively narrowing your total search space. However, my gut says minimizing the entropy may be more effective as it seems more optimal to have slightly more possible solutions where most people have only one or two possible partners, than to have fewer possible solutions but more possible outcomes per person.
I also want to note, both of these approaches assume the success of a greedy strategy. I have no justification for this, but I cannot think of a computationally tractable way of approaching the problem otherwise. Additionally I will assume the worst case scenario outcome can also be found using a greedy strategy for the same reason.
During this post I will refer to the two members of each couple using capitol letters ("A", "B", "C", etc.) with each letter A-J referring to one man and the same letters A-J representing one woman. A couple pair will be indicated by a hyphenation of the two letters ("A-A", "A-B") where the position represents the gender of the person.
First observation is that at week one:
It does not matter what couple is chosen to test as they are all equivalent at this state nothing distinguishes any of the members.
For ease of communication we will designate the first couple to be tested as:
For both strategies the worst case scenario is:
A-A is not correct.
This gives the following matrix of possible options were the number in each box of the grid represents the number of possible scenarios where the person in each row is correctly paired with the person in each column.
Going into the couple matching test for week 1 we can observe that
All the couples that haven't been paired are still equivalent so there is only one choice to make; Do you keep the first tested (and failed) couple together for the ceremony or do you match them with new partners.
At this point came my first big surprise. I assumed that the optimal choices for the two strategies would be very similar for the most part but instead I discovered
The optimal choice for reducing the number of options was to give A-A new partners (1334961 options for stay, 1201464 for switch), but the optimal choice for reducing the entropy was to keep them together (entropy 0.99483 for stay, 0.99516 for switch)!
In both cases
The worst case scenario is for 1/10 couple to be a correct match.
Which produces the following matrix for strategy which minimized the number of possible options:
With black outlines representing the tested couples and white text representing best choices of couples to evaluate next week. For the entropy based strategy, the matrix is: