Will we find a closed form for the expected number of moves in eidetic single-player Memory?

464

Ṁ360

Ṁ141

resolved Mar 8

Resolved

ALL

Consider the single-player version of Memory, where you try to uncover matching pairs of cards by flipping over two at a time. If they match, remove them -- if not, put them back. And assume you have a perfect memory and play perfectly. Given p pairs of cards (n=2p cards total), how many turns does it take, in expectation, to find all the matches? We have a recursive function that can efficiently get the answer for any specific number of cards but have not found a closed form.

Will we find it?

Here's our ongoing progress: https://forum.beeminder.com/t/matching-game-perfect-play/10346

Get Ṁ200 play money

🏅 Top traders

#	Name	Total profit
1		Ṁ7
2		Ṁ3
3		Ṁ3
4		Ṁ1
5		Ṁ0

14 Comments

10 Holders

139 Trades

Sort by:

I'm fairly sure this is possible but we clearly didn't do it in time so I'm planning to resolve this to NO if there are no objections...

bought Ṁ2 of YES

have you tried generating functions yet

@agentydragon I have not! I'm not actually even sure where to start on doing so, for whatever that's worth in predicting our success at this endeavor.

predicted YES

@dreev there's a book, generatingfunctionology. Or start from a book on discrete math (probably), for problems like counting involutional, or finding the closed form formula for Catalan numbers

predicted YES

*involutions

bought Ṁ1 of YES

Do you have a precise definition of what qualifies as "closed form"? Presumably you mean "in terms of some set of pre-allowed functions". Are finite sums allowed? Infinite sums? What's the set of permitted functions, precisely?

@ScottLawrence Pretty much anything non-recursive should qualify!

bought Ṁ5 of YES

@dreev While I'm optimistic that you'll succeed---that is, that you'll say "we have succeeded"---I still think this is vaguely worded enough to be potentially problematic. For instance, I expect that you would *not* allow a solution of the following form: "I give you a straightforward expression for a function F_p(E), where E is a vector of dimension p^3 (representing various expectation values). F has a single global minimum. The value of a particular (specified) component of E, at that global minimum, is the desired expectation value." (I choose that example because one can encode the recursion relation in that form.) But it's not so clear where the dividing line is, and this is just one example of a problematic construct. I would hope that you would allow "here's a function of one variable; the largest root that lies in [0,1] is the expectation value you want", but many people would not allow that as "closed form".

predicted YES

(I realize that I'm being an unholy pain in the derriere, but IMHO posting to a prediction market is asking for pedantry.)

@ScottLawrence Ha, I love it. Does Wikipedia have something reasonably authoritative? https://en.wikipedia.org/wiki/Closed-form_expression Even if not, I meta-predict that the gray area here has small measure, so to speak, and that we'll either find something that obviously counts as closed-form or we'll fail to.

predicted YES

@dreev I view wiki's definition as being *way* too restrictive. I think you'd accept a 1-d integral. But it's very difficult to define a broader definition in a way that excludes some of the more extreme tricks...

predicted YES

(But I agree with your meta-prediction, I guess.)

predicted YES

Actually, to clarify: there are tricky forms for *every* expression. So I agree only if, when you invoke "the measure", you're refering to the measure induced by "humans use intuition to search", rather than some measure intrinsic to mathematics.

@ScottLawrence Affirmative. It's unlikely that we come up with some crazy technically non-recursive expression involving integrals or "the minimum of such-and-such function" or whatever. Much more likely we'll either find some closed form like the nth root of the golden ratio or something delightful like that or else we just won't find anything better than the recursive function we have currently. In other words, it's very unlikely that we'll find ourselves needing to debate definitions of "closed form" in order to properly resolve this.