Thread: Matching problem View Single Post
 2021-06-02, 16:38 #3 Viliam Furik     "Viliam FurÃ­k" Jul 2018 Martin, Slovakia 2·373 Posts I will demonstrate what I think is the worst-case scenario for n=5, using a bit of strategy in choosing the switches, such that I will try to not place the same letter twice to where I know it doesn't belong. ([x] denotes that letter is for sure in its correct envelope) Begin Step 1 -> 2, 4, 5, 1, 3 Friend -> 0 (call 1) Step 2 -> 2, 3, 5, 1, 4 (3-4 switch) Friend -> 0 (call 2) Step 2 -> 5, 3, 2, 1, 4 (2-5 switch) Friend -> 0 (call 3) Step 2 -> 5, 1, 2, 3, 4 (1-3 switch) Friend -> 0 (call 4) Step 2 -> 5, 1, 4, 3, 2 (2-4 switch) Friend -> 0 (call 5) Step 2 -> 3, 1, 4, 5, 2 (3-5 switch) Friend -> 0 (call 6) Step 2 -> 3, 1, 4, 2, 5 (2-5 switch) Friend -> 1 (call 7) Step 2 -> 3, 5, 4, 2, 1 (1-5 switch) Friend -> 0 (call 8) Step 2 -> 3, 1, 4, 2, [5] (rollback) Step 2 -> 3, 4, 1, 2, [5] (1-4 switch) Friend -> 1 (call 9) Step 2 -> 1, 4, 3, 2, [5] (1-3 switch) Friend -> 3 (call 10) Step 2 -> [1], 2, [3], 4, [5] (2-4 switch) At this point, you don't even need to call your friend, because you are certain you got it correct - If your correctness number is n-2, you know you just have to switch the two remaining letters you didn't yet mark as correct. That is 10 calls for n=5 in the worst case. If someone finds a mistake in my example, please, point it out.