Can you clarify if this is correct? You want a strategy for Alice such that, for every permutation of the boxes, $\Pr[$find a red$] \geq 1-1/n$.

For instance, a published book all about the sums of various series clearly would show that summation as an operation was interesting enough to be studied on its own. A reference to a particular series, say the triangle numbers, might not show that the author had any theory of summation in her/his toolbox as a general method.

@MonroeEskew, if I may attempt a tenuous analogy, the Greeks had the integers and the rules of summation and the fact that zero is an additive identity, but we would probably not attribute to them the study of group theory. The case of summation is way more murky of course, because it's hard to identify the line where it became a useful abstraction, so I don't insist on anything. But I'm playing devils advocate to try to show why I think the question might not be silly.

@MonroeEskew, I would disagree -- I think the modern notion of summation is more sophisticated: We have the idea of some well-defined set of numbers, and the notion that we want to calculate the sum over this entire set. We have the idea that this general approach is useful in many circumstances for solving different problems. The question is looking back in time for when this general idea arose as a useful abstraction, not looking for the earliest example of a particular instance of this idea.

Re: #3 and #4, it depends what you think of as "planning beforehand". We could ask "what is a strategy that succeeds if both players follow it?" We could consider this a sort of equilibrium strategy and it might be reasonable for both players to follow such a strategy even if they have never met or spoken. (Selection among all such strategies is a further problem...)

If they can write arbitrary messages this might be too easy for them: Each player continually writes her entire strategy on the ground. Once you cross another's path, you simply compute where they will be at all points in the future and pick a meeting point. (This should work because once you read their strategy, you also know when they will next cross your path or if they have already done so, and you know how they will react.)

I think the most fun question is when the strategies must be symmetric (otherwise it is like they agree beforehand to synchronize) and they must meet as quickly as possible, in expectation, subject to an upper bound on travel speed $v$. So, when both players follow the same strategy, what is the optimal strategy and how long will it take them to meet on the unit sphere?

Related: mathoverflow.net/questions/139804/… . I thought I had seen other discussions of this phenomenon on here as well....

Technically I think Nash's theorem is only for finite action sets. For infinitely many pure strategies, the existence theorem I know of is Glicksberg's, which wants the strategy space to be compact (which is true here) and the payoffs to be continuous in the pure strategy. I'm worried about this last condition, continuity, since I think a small change in some $x_i$ can cause a payoff jump. Some slides about that theorem: ocw.mit.edu/courses/electrical-engineering-and-computer-science/…

Does an equilibrium definitely exist?