Will we find a closed form for the expected number of moves in eidetic single-player Memory?
13
141Ṁ360resolved Mar 8
Resolved
NO1H
6H
1D
1W
1M
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
This question is managed and resolved by Manifold.
Get 
1,000 to start trading!
1,000🏅 Top traders
| # | Name | Total profit |
|---|---|---|
| 1 | Ṁ7 | |
| 2 | Ṁ3 | |
| 3 | Ṁ3 | |
| 4 | Ṁ1 | |
| 5 | Ṁ0 |
Sort by:
@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.
@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
@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".
@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.
@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...
@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.