Thread: Matching problem View Single Post
2021-06-02, 22:38   #11
Walter

"Walter S. Gisler"
Sep 2020
Switzerland

11112 Posts

Quote:
 Originally Posted by uau Trying something that could be the correct answer given all previous ones (which I believe is what Walter's code does) is not always the optimal answer, either for average or worst-case behavior (at least worst case for remaining tries in a particular situation, I don't show this to necessarily affect the global worst case): Suppose that n = 1000000. Your first random guess gets 999998 matches right (quite lucky). Now, if you keep trying guesses that could be the correct answer, they can only swap one pair from your initial guess. Since you can only change two places at once, you'd expect to need around 146000 tries to even try changing one of the incorrect positions (you'd try changing twice that number of places, and 50% chance that both the incorrect positions are outside that set). Some kind of bisection strategy should be able to do much better than that.
Interesting case! Would definitely be curious to see thoughts on how to handle this kind of situation better. I am not so sure. isn't 9999998 correct matches just as bad as only 2 correct matches in terms of information value?

I did a few additional tests. Unfortunately it isn't practical to try my method with such a high n because the matrix gets too big, but if I use n = 100 and force exactly this kind of situation, I am on average only using about 30 tries. My feeling is telling me that that's pretty decent compared to what you would expect as an average runtime.

So, with n = 1M, it is true that my approach would probably use over 100k tries in this worst case scenario (it needs to "touch" each wrong position at least once). However, what would the average case scenario look like? My gut feeling is telling me it would be somewhere in that range too. But might completely off on that estimate. It is pretty hard to imagine this game with such a lot of letters and envelopes...