　$s_i,t_i$ を次のように定める．
$$s_0=t_0=0,　s_i=\sum_{k=1}^{i} x_k,　t_i=\sum_{k=1}^{i} y_k ~ (1 \leq i \leq N)$$
　このとき，$M$ の条件は次のように書き換えられる．
- 任意の実数の組 $(s_0,s_1,\dots,s_{N}, t_0, t_1, \dots, t_{N})$ が，$s_0=t_0=0$ かつ，$0 \leq i \lt j \leq N$ なる任意の整数の組 $(i,j)$ について，
$$|s_j-s_i|+|t_j-t_i| \geq 1$$
をみたすならば，任意の実数 $a,b$ について，ある $i ~ (0 \leq i \leq N)$ が存在し，
$$|s_i+a|+|t_i+b| \gt M$$
が成り立つ．

　さて，実数 $s,t$ に対し，$xy$ 平面における領域 $S(s,t)$ を
$$S(s,t):|x-s|+|y-t| \lt \frac{1}{2}$$
で定める．この領域は，点 $(s,t)$ を中心とする，一辺の長さが $1\/\sqrt{2}$ の正方形であり，各辺の傾きは $1$ または $-1$ である．さらに，実数 $(a,b)$ に対し，領域 $T_M(a,b)$ を
$$T_M(a,b):|x+a|+|y+b| \leq M+\frac{1}{2}$$
と定める．この領域は，点 $(-a,-b)$ を中心とする，一辺の長さが $(2M+1)\/\sqrt{2}$ の正方形であり，各辺の傾きは $1$ または $-1$ である．これらを用いると，$M$ の条件はさらに次のように書き換えられる．
- 任意の実数の組 $(s_0,s_1,\dots,s_{N}, t_0, t_1, \dots, t_{N})$ が，$s_0=t_0=0$ をみたし，さらに $0 \leq i \lt j \leq N$ なる任意の整数の組 $(i,j)$ について，$S(s_i,t_i)$ と $S(s_j,t_j)$ が共通部分をもたないならば，任意の実数 $a,b$ について，ある $i ~ (0 \leq i \leq N)$ が存在し，$S(s_i,t_i)$ は $T_M(a,b)$ に含まれない．

$M$ が整数であることに注意すると，$N+1\leq (2M+1)^2$ をみたすならば，正方形 $S(s_1,t_1),\dots,S(s_N,t_N)$ をうまく配置することで，ある正方形 $T_M(a,b)$ に含まれるようにすることができるから，条件はみたされない．一方で $(2M+1)^2\lt N+1$ をみたすならば，面積の総和を考えることにより，条件がみたされることが確認できる．よって，条件をみたす $M$ の最大値は
$$\bigg\lfloor \dfrac{\sqrt{N}-1}{2} \bigg\rfloor = \mathbf{15810}.$$
公式解説
https://onlinemathcontest.com/contests/omc166/editorial/7278
　$N=10^9$ とします．以下をみたす正の**整数** $M$ の最大値を求めて下さい．

- 実数 $a,b$ および $2N$ 個の実数の組 $(x_1,x_2,\ldots,x_{N},y_1,y_2,\ldots,y_N)$ が，$|a|+|b| \leq M$ および， $1 \leq i \leq j \leq N$ なる任意の整数の組 $(i,j)$ について
$$\bigg|\sum_{k=i}^{j} x_k \bigg| + \bigg|\sum_{k=i}^{j} y_k \bigg| \geq 1$$
をみたすならば，ある $i ~ (1 \leq i \leq N)$ が存在し，
$$\bigg|a + \sum_{k=1}^{i} x_k \bigg| + \bigg|b + \sum_{k=1}^{i} y_k \bigg| \gt M$$
が成り立つ．