View Single Post
Old 2021-06-02, 22:49   #13
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

5×13×23 Posts

Originally Posted by henryzz View Post
What is the expected number of times you need to pair the letters with envelopes to get all matching?
You need at least (1-eps)*n guesses on average (for fixed eps>0 and for that large n).
On the k-th 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=(1-eps)*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)>(1-eps2)*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.
R. Gerbicz is offline   Reply With Quote