Quote:
Originally Posted by henryzz
What is the expected number of times you need to pair the letters with envelopes to get all matching?

You need at least (1eps)*n guesses on average (for fixed eps>0 and for that large n).
Proof:
On the kth level (after k guesses) there are at most (n+1)^k nodes, because each answer could be only 0..n. If we found the permutation, then that node is a leaf in the tree.
let L=argmax( h: 1+(n+1)+...+(n+1)^h<=n! )
ofcourse L=(1eps)*n.
Then for the average expected number of guesses: F(n)>=((L+1)*(n!sum(h=0,L,(n+1)^h))+sum(k=0,L,k*(n+1)^k))/n!
and from this F(n)>(1eps2)*n.
(it could be possible to improve this estimation a very little).
My wild guess is that you can get the permutation with only O(n*log(n)) guesses,
as your ideas, for this you only need to halve the search space, what is not very unlikely
because we have much more, (n+1) different answers on the guesses.
[ we know: log2(n!)=O(n*log(n)) ].
ps. even n=10 could be a very hard problem.