Update (January 17): The problem has now been solved by Daniel Ahlberg and Christopher Hoffman. (Thanks to Matt Kahle for informing us.)
Consider a square planar grid. (The vertices are pair of points in the plane with integer coordinates and two vertices are adjacent if they agree in one coordinate and differ by one in the other.)
Give every edge a length one with probability a half and length two with probability a half.
Consider a shortest path between the origin and the vertex $(n,0)$.
Show that with probability that tends to one as $n$ tends to infinity the shortest path will not contain the "middle edge" on the x-axis inbetween the orgin and $(n,0)$. (Namely, the edge between the vertices $(\lfloor\frac{n}{2}\rfloor,0)$ and $(\lfloor\frac{n}{2}\rfloor+1,0)$.)
This question is in the category of "a missing lemma". It is not really a full fledged open problem but rather a statement which looks correct that was needed in some paper and resisted proof. Of course, some such "lemmas" turn out to be very difficult, but sometimes maybe a simple argument was simply missed. The relevant paper is
- Itai Benjamini, Gil Kalai, and Oded Schramm, First Passage Percolation Has Sublinear Distance Variance, Ann. Probab. 31(4) (2003) pp 1970-1978, doi:10.1214/aop/1068646373, arXiv:math/0203262.
While MO have chosen to accept one answer, and there were some nice suggestions, the problem is still wide open.
Best Answer
It seems that this problem was recently solved by Ahlberg and Hoffman. https://arxiv.org/abs/1609.02447