20210602, 22:44  #12 
If I May
"Chris Halsall"
Sep 2002
Barbados
9,767 Posts 

20210602, 22:49  #13  
"Robert Gerbicz"
Oct 2005
Hungary
2×743 Posts 
Quote:
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. 

20210602, 22:54  #14  
Jan 2017
3^{2}·11 Posts 
Quote:
The issue with trying only attempts that could be correct given previous ones is that while it may be optimal use of previous information to maximize the chance of solving the problem in one more try, it is not an optimal way to gain the maximal amount of new information from the try if it turns out to not be correct. 

20210602, 23:00  #15 
If I May
"Chris Halsall"
Sep 2002
Barbados
2627_{16} Posts 

20210602, 23:39  #16 
Feb 2017
Nowhere
123A_{16} Posts 
It's not clear to me what is allowed. Apparently you are allowed to switch pairs, and keep track of which pairs you've switched. Given n envelopes and n letters, a given pairingup of letters and envelopes corresponds to one of the n! permutations of n elements.
Assuming you eventually reach complete matching up (identity permutation) by switching one pair at a time, this would correspond to expressing the (inverse of) the original permutation as a product of transpositions. I suppose it is possible to determine, by repeated switching, which of the letters are in the correct envelopes. Perhaps it is possible to aim for a nested series of subgroups of S_{n}. Amusingly, if you suppose that each attempt is totally from scratch, and any of the n! permutations is equally likely, the "expected" number of tries before you match them all up (identity permutation) is n!. This is actually not hard to prove. Unfortunately, n! grows quite rapidly with n; 10! is already 3,628,800 so this approach is likely to take a while. In fact, the probability that the desired matching has not been found in n! steps is (1  1/n!)^n!, which for n >=10 is very close to 1/e = .367879+ The number of "derangements"  permutations with no fixed points  none of the letters is in the right envelope  is  sometimes denoted !n or n¡ or "subfactorial n". If n is at all large, this is very close to n!/e. 
20210602, 23:51  #17 
"Viliam Furík"
Jul 2018
Martin, Slovakia
1146_{8} Posts 
I was watching Netflix and returned back to this thread only now.
Walter: So your program is basically doing what you explained with the Excel pictures? If so, now I get it; even though still not quite educated in your code, I get the idea. To explain my 14 switch  I wanted it to be as many steps as possible whilst preserving the minimalism. In the situation before the 9th call, there were only four switches possible. 23 was absolutely bad because both 2 and 3 would get to already known bad positions. 31 and 24 were, as I realize now, the best choices. I went with 14 because 4 would get to a known bad position, but 1 would not. Thus I considered it acceptable as I was trying to get the worstcase scenario. I didn't realize that I should have kept my focus on making the worst best switches based on my information. (worst by randomness, best by strategy) 
20210603, 00:03  #18  
Jan 2017
99_{10} Posts 
Quote:
You can get at least one correct element overall by trying random permutations. I think the expected number of tries for just a simple strategy of "pick some half of remaining elements, randomly permute them" before you see a change in the number of matches would have a finite upper bound over all n. That'd allow you to bisect to the location of one correct element in O(log(n)). 

20210605, 18:42  #19 
Jan 2017
3^{2}×11 Posts 
It occurred to me that you can also get O(n*log(n)) by kind of the opposite strategy: instead of proving for one element at a time what its correct value must be, you can also collect permutations with zero matches that prove where every element can not be, and get enough of those in O(n*log(n)) to rule out any wrong value.
With each element having 1/n chance of being correct, all being wrong is about 1/e probability. So just trying random permutations will get you zeromatches ones which rule all values in that permutation. You can repeat this until you get mostly repeats of alreadyruledout values. With a constant multiple of n tries, you can rule out any particular percentage of possible values. So with O(n) tries, you can assume that for element in the permutation, about 90% of values have been ruled out, and n/10 possible values are left. To proceed further, you can specifically select some of the remaining possible values in a permutation. If each has one in n/10 chance of being correct, you can again place n/10 of them in the same permutation and still have a decent chance of there being zero matches overall. Select all other places with knownfalse values (should be pretty easy with 90% possibilities being known false). So you get one new knownwrong value for each of n/10 places, and need to do this 10 times to get one more for all n. So how many tries total? When there are k possible values remaining, you can try about k places in parallel, and need n/k to process all n. Total is sum of n/k for k from 2 to n (or n/10, if you get to 90% ruled out by totally random permutations as above), which is O(n*log(n)). 
20210606, 00:36  #20 
"Robert Gerbicz"
Oct 2005
Hungary
2·743 Posts 
An offline version of the puzzle, where you need to give all of your guesses in advance,
so you can profit nothing from the previous answers. For n=10 here it is a solution that is using "only" 23 guesses, which is quite good if you compare this to log2(10!)=21.79 ( proving nothing, so we could get even better than log2(n!) ). Hence there is no two different permutations of 1..10 where you give the same 23 answers. Code:
P=[[3,10,6,4,8,9,2,7,5,1],\ [3,10,1,7,9,6,5,2,4,8],\ [5,3,6,2,4,10,7,8,1,9],\ [2,6,5,8,7,1,9,4,3,10],\ [8,10,3,7,1,5,4,9,6,2],\ [6,5,10,8,4,2,3,1,7,9],\ [3,8,7,2,4,5,6,10,9,1],\ [4,1,7,5,2,3,10,9,8,6],\ [8,4,10,5,1,2,3,6,7,9],\ [10,9,8,2,5,3,6,1,4,7],\ [4,9,7,2,8,6,3,1,5,10],\ [4,5,1,9,3,10,8,7,6,2],\ [3,9,7,10,4,2,5,8,6,1],\ [1,4,2,6,10,8,5,7,3,9],\ [3,4,6,9,7,1,8,10,2,5],\ [2,10,9,4,6,1,5,8,7,3],\ [1,9,8,6,5,10,7,4,3,2],\ [1,10,3,2,9,8,4,7,5,6],\ [7,3,8,4,2,10,6,5,1,9],\ [1,5,10,8,9,6,7,3,4,2],\ [7,3,5,4,6,1,9,10,2,8],\ [9,6,2,1,4,3,7,5,8,10],\ [7,2,9,8,6,1,4,10,3,5]]; 
20210606, 05:55  #21 
Jun 2003
11000101110_{2} Posts 
In worst case scenario this can be solved in ~ N^2 tries.
The faster practical solution (not sure if this is allowed) is to create a hash table and assign each unique letter a number. Set the letter and envelopes set in ascending order based on the same hash table. Then this can then be solved in ~k*N trials. (depending on the definition of the problem the problem is slightly vague) Last fiddled with by Citrix on 20210606 at 05:58 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Matching BAD LL results?  PhilF  Data  35  20190520 02:36 
Largest number of LL tests before matching residues achieved?  sdbardwick  Lounge  1  20150203 15:03 
Can 1227133513 be the only composite number matching the conditions?  miket  Math  5  20140812 00:41 
Three matching tests not closing exponent?  Dubslow  PrimeNet  8  20120427 18:19 
Residue not matching due to masked bits  patrik  Data  1  20110924 23:44 