View Single Post
Old 2021-06-02, 16:38   #3
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2×353 Posts
Default

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.
Viliam Furik is offline   Reply With Quote