pr.probability - The shortest path in first passage percolation

UPDATE: Fixed typing error in 2nd paragraph (greater than -> less than or equal to)

UPDATE2: Fixed typing errors pointed out by Gil Kalai

UPDATE3: I put off the detailed version from my webpage

UPDATE4: The solution is wrong, as pointed out to me by Nathanaël Berestycki. It is of course not enough to consider only the path that goes directly from the origin to (n,0). I didn't read the problem properly. Sorry.

I don't know whether this problem is still open, but I think I have found an elementary proof for the original question. It is almost too simple to be true, but I don't see any mistake. Here's the sketch:

All numbers here are natural numbers between $0$ and $n$, and $n$ is sufficiently large. Fix a (large) $K$. Let $x_l$ be the smallest $x < n/3$, such that for all $1le j le K$, the length of the path $(x,0)rightarrow (x,j) rightarrow (x+K,j)$ is less than or equal to the length of the path $(x,0)rightarrow (x+K,0)$. The arrow indicates that we take the direct path. For definiteness, set $x_l = lfloor n/3 rfloor + 1$ if such a number does not exist, but note that it exists with probability going to one as $nrightarrow infty$. Note further that since we took the smallest $x$ with the above property, conditioned on $x_l$, the lengths of the edges to the right of the vertical line $x=x_l+K$ are still independent, of the same law as before, and independent of the configuration to the left of this vertical line.

Now define $x_r$ by mirroring the above definition at the line $x=n/2$ (the largest $x>2n/3$, such that ....)

Then, the paths $(x_l+K,j)rightarrow(x_r-K,j)$ are independent for $0le jle K$, hence, with probability going to $K/(K+1)$, there exists $1le j le K$, such that the path $(x_l+K,j)rightarrow(x_r-K,j)$ is shorter than $(x_l+K,0)rightarrow(x_r-K,0)$.

Combining the above observations, with probability $K/(K+1) + o(1)$, there exist $x_l < n/3$, $x_r>2n/3$ and $1le j le K$ such that the path $(0,0) rightarrow (x_l,0)rightarrow (x_l,j)rightarrow (x_r,j) rightarrow (x_r,0) rightarrow (n,0)$ is shorter than the path $(0,0) rightarrow (n,0)$. Letting first $nrightarrow infty$, then $Krightarrowinfty$ finishes the proof.