Thread: Matching problem View Single Post 2021-06-02, 22:49   #13
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101110100012 Posts 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 (1-eps)*n guesses on average (for fixed eps>0 and for that large n).
Proof:
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.  