OK, so a black toddler and a Chinese toddler stumble on an international drug-trafficking ring — no, actually, this is a game I just bought for CJ, a kid’s version of Nob Yoshigahara‘s classic game Rush Hour. The object here is to get the small white truck to the edge of the board (the top edge, in the image here.) The trucks in your way can’t move sideways or turn; they just go forward and back.
You play a captivating game like this and naturally you start abstracting out the underlying math problem. Play Set enough and you can’t avoid thinking about affine caps. Rush Hour has more to do with the geometry of configuration spaces; it reminds me of the “disk in a box” problems that people like Persi Diaconis and Matt Kahle work on.
So here’s a question — it doesn’t capture all the features of Rush Hour, but let’s start here. Let X be the unit square, and let c be a parameter between 0 and 1, and let N be a large integer. Let L be the set of line segments in X which are either horizontal of the form y = i/N or vertical of the form x = i/N. A traffic jam is a choice of a length-c interval in each of the 2N +2 line segments in L, where we require that these intervals be pairwise disjoint. The traffic jams naturally form a topological space, which we call T(N,c). We say an interval (x,i/n),(x+c,i/n) in a traffic jam t is trapped if no traffic jam in the connected component of t contains the interval (0,i/n),(c,i/n).
Questions: For which values of (N,c) is T(N,c) connected? In particular, is it connected almost always once it’s nonempty? If not, when does T(N,c) have a “giant component”? If there’s an interesting range of parameters where T(N,c) is not connected, what proportion of intervals do we expect to be trapped?
Quomodocumque 
It’s not clear to me how you are defining the “natural” topology on T(N,c).
T(N,c) maps to R^2N+2 where your coordinates are the starting points of the intervals and I have in mind the topology induced by the restriction.
OK, I think I see what you’re up to, but don’t you actually need to consider pathwise connectivity and path components? (Components of a subspace of R^2N+2 are not necessarily pathwise connected.) I see a puzzle “solution” as a path in T(N,c), which of course also opens the door to thinking about the geometry of the set of all solutions. Let me know if I’m way off base.
The expression “giant component” is not standard in point set topology as far as I know. Apparently this comes from graph theory.
Since I have not done enough topology to even keep up with the math, I have a question about two simple English words.
Is Rush Hour a game? Or is it a puzzle?
I tend to think of games as contests that waged by use of superior strategy and skill that end with all human participants expereincing a victory or a defeat. Puzzles are problems (like math problems) that may or may not have a solution, but that are inherently solvable. Though they may have mroe than one solution.
(A third category, I call activities are contests in which you need not be present to win such as: Candy Land, War, LCR, Lotto).
Now a solution and a victory may feel similar, but are they? Which of these are games and which are puzzles:
Chess
Clue
Mastermind
Tetris
Myst
Super Mario Brothers
Doom
Euchre
Ricochet Robots
Reiner Knizia’s Fits
Is this a meaningful disntiction? (I bring this up because you have written about what is a sport and what isn’t and this seems related).
Coincidentally, David just blogged about this!
http://malvasiabianca.org/archives/2010/05/another-world/
He says:
“Jesse Schell defines a puzzle as “a game with a dominant strategy”, with the implication that “puzzles are just games that aren’t fun to replay”. ”
Anyway, I do think Rush Hour Jr. is more of a puzzle under any reasonable account, yet I am inclined to call it a game. Why?
The awesome puzzle game Fish Fillets NG has a level called Filled Car Park which has this type of puzzle as the basis. The previous level is a tower of hanoi puzzle. The game’s free for download and hours of fun! Highly recommended.
I though about it for a bit. I think you are missing the point. It is in fact very easy in Rush Hour to get stuck. Keep alternating vertical and horizontal intervals from upper left corner to lower right corner, each next blocking the previous one. Place the remaining intervals whatever way – since the “diagonal” is stuck the intervals can’t get across. As for the “giant component” question, since you can’t efficiently sample from the set of allowable intervals, this also makes little sense to me.
However, having played RH as a kid (many years ago) I am pretty sure the “right way” of stating the problem is different. In your pic, the main elements are four big trucks on the sides (two yellow and two red ones). The question is whether you can get them across. In your notation, let c<1/2, and have half vertical intervals be stuck on top (so they form c x 1/2 rectangle like the red truck in the upper left corner), with the remaining vertical intervals be stuck on the bottom (yellow truck), and a similar pattern with horizontal intervals. You want to move all intervals all the way across the board (another legal position). I checked in my head, and for c<1/4 this is possible and in fact very easy. I suspect this is also possible all the way to c<1/2, but might take a long time, maybe a polynomial in (1/.5-c). It's hard for me to visualize this…