Thread: Matching problem View Single Post
 2021-06-02, 14:32 #2 Viliam Furik     "Viliam FurÃ­k" Jul 2018 Martin, Slovakia 3×251 Posts If we assume the envelopes are coded 1 to n, and letters are also coded 1 to n, but the pairings of these numbers are unknown, the maximum number of tries you need should be n! because you can simply try all the possible arrangements of the letters while fixing the envelopes. That's for brute force. If you want something clever, I suggest something like the following:Start with a random arrangement of letters in your fixed envelopes. Ask your magical friend for the number of matches. Then you find your matches by switching two random letters (call them A and B) and comparing your number of matches.a) If the number increases by two, your letters were in each other's places, and are now in the correct places. b) If the number increases by one, one of your letters got to the correct place, and you can find out which one, by switching one of your letters (A, B) with a randomly chosen letter C. Say we switch B and C.I. If the number increases by two, B and C were in each other's places, and thus the correct one was A. A, B, and C are now in the correct places. II. If the number increases by one, A was the correct one, and one of B or C got to the correct place. You can find out which one by repeating step 2b for letters B and C. III. If the number stays the same, A was the correct one, and neither B nor C is in the correct place. Repeat step 2. IV. If the number lowers by one, B was the correct one, and you can return it and repeat step 2. V. If the number lowers by two, B was the correct one, C was also in the correct place, and you can return them, then repeat step 2. c) If the number stays the same, neither one of your letters got to the correct place. Repeat step 2. d) If the number lowers by one, one of your letters was already in the correct place. You can find out which one by switching them back and applying the same procedure as in step 2b. e) If the number decreases by two, your letters were already in the correct places. Switch them back, and repeat step 2. When you are certain that some letter is in its envelope, leave it there and never move it until you're done. That should do it. I am not sure if it's the best way to do it, but it should be a fairly good way to do it. As for the expected number of times you bother your friend, I don't know, and it's probable that someone else here will find a better algorithm or the number before I do either.