Today's XKCD-comic (see below) featured a couple of joke open math problem, and one of them caught my interest (being the only one that's an actual mathematical question!):
If I walk randomly on a grid, never visiting any square twice, placing a marble every $N$ steps, on average how many marbles will be in the longest line after $N\times K$ steps?
Here is how I interpret it formally:
Let $N,K\in\Bbb N$, and consider a finite-length symmetric random walk $X=(X_0, X_1, \ldots, X_{NK-1})$ of length $NK$ on the plane grid. Let $Y_i = X_{iN}$ for $i\in\Bbb N_0$. $Y_i$ is the position of the $i$'th marble. What is the expected cardinality of the maximum set of collinear $Y_i$, given that $X_j\ne X_k$ for all $j\ne k$?
To my eyes this looks pretty complicated; I can't tell whether it is feasible or not. I would love to see any analysis on this, even if a complete answer is out of reach. Feel free to simplify the problem too, if it leads to something interesting. For example we could:
- Drop the condition that the random walk be non-repeating.
- Look at an infinte random walk instead (i.e. set $K=\infty$).
- Set $N=1$.
- Look at the expected number of collinear marbles in some sense, instead of looking at the maximal collinear set? (Perhaps taking expectation over lines that go through two marbles... idk).
- ...
To be clear, I am not asking all these things at the same time! I am just looking for any interesting discussion on the problem.
