Posted by: yanzhang | April 14, 2008

## Matryoshka Problems

True to the nature with their obsession with sets, combinatorialists like to collect stuff assorted by theme. Thus, we have Richard Stanley’s collection of Catalan-number-enumerated sets, Bridgit Tenner’s collection of permutation-avoidance occurrences, and of course… this. One day I’ll make a collection of these collections just for the sake of having a metacollection, but until then my main collectible hobby will be of Matryoshka problems, a term I just made up today.

Like its namesake, a “matryoshka problem” is not a single problem but a family (a “chain” really – although in practice the length is usually 2) of problems that increase strictly in difficulty. Then, as I am bewildered at discovering a smaller doll inside another, I realize I can push the boundaries of what I can prove.

Of course, this nested structure is not rare – in fact, it occurs very naturally in mathematics. Why? Because mathematics come from theory-building and generalization. Usually, some real-world (I use this term loosely) problem needs to be solved, so some smart person (the other mathematicians) goes ahead and generates just enough math to solve that. Then we want to generalize – say from $R^n$ to Hilbert spaces, and then from Hilbert Spaces to Banach spaces… and we naturally get a nested sequence of problems.

Usually, these families all have solutions which are at heart the same (just a little harder technically at each step) – like nested dolls who look exactly alike. For me, the fun comes when the techniques used to solve each level of the problem are completely different. It is great practice for think ing outside the box, because doing the “easier” versions of the problems tend to trap me into modes of thinking that makes it harder to do later problems.

To start this series, I’ll just do a pair of problems (again, most of my posts will probably end up being pairs, so I’ll call them “M-2 problems“). This one isn’t particularly nice, but I hope it demonstrates the spirit of what I’m trying to do (as a warning, since I give these in tuples, it is tempting to move through the “easy” ones quickly. But I think a lot of the fun and appreciation of these problems come from having thought about and being able to appreciate the “easy” versions of the roblems before going ahead, so keep this in mind).

-Y