Induct on $n$ for any set $M$, base case $n=1$ easy to verify. Notice that the first step in a path must be to $(1,0)$ or to $(0,1)$, since all steps must be right or up due the path length being $n$. There exists at least one mine-avoiding path, so there are 2 distinguishable cases: Case 1: There exists a mine-avoiding path starting at (1,0) and there exists a different one starting at (0,1). Then in each of the two paths, there are at least $2^{(n-1)-|M|}$ ways to finish by induction, for a total of at least $2\cdot 2^{(n-1)-|M|} = 2^{n-|M|}$. Case 2: There does not exist a mine-avoiding path starting at (1,0). (The case replaced with (0,1) is symmetrical.) Then in particular, $(0,0)\to (1,0)\to (2,0)\to \cdots \to (n,0)$ is not a mine-avoiding path. So at least one of $\{(1,0),(2,0),\ldots,(n,0)\}$ is a mine, say $(k,0)$. The mine-avoiding path that exists starts at $(0,1)$, and will never hit $(k,0)$ since all steps are up and right. So we cut out this mine, and the number of mine-avoiding paths starting at $(0,1)$ is in fact at least $2^{(n-1)-(|M|-1)} = 2^{n-|M|}$. This completes the induction for all cases, and we are done.

basically induct on n, while doing cases on whether there are points on the x/y-axes

induct on $n$. will write out full sol later

Induct on $n$; base case is obvious. [asy][asy] size(5cm); dot((0,0)); for(int i=1; i<8; ++i) { dot((0,i),red); dot((i,0),green); for(int j=1; j<8-i; ++j) { dot((i,j),blue); } } [/asy][/asy] Separate the points into three regions as shown above. Let the number of mines in the red, blue, and green regions be $a,b,c$ respectively. If $a=c=0$ then our first move can be either up or right. After either of these moves we have at least $2^{n-1-|M|}$ ways to finish due to induction (there certainly exists at least one way to finish), hence at least $2^{n-|M|}$ paths total. If $a=0$ and $c>0$ then consider moving to $(0,1)$. There certainly exists at least one way to finish, hence by induction we have at least $2^{n-1-b} \ge 2^{n-|M|}$ ways to finish. The case $a>0$ and $c=0$ is identical to the above. If $a>0$ and $c>0$, then we're given there's at least one valid path -- WLOG its first move is to $(0,1)$. Then by induction there are at least $2^{n-1-a-b} \ge 2^{n-|M|}$ ways to finish.

idek if my sol is correct I called a point "bad point" iff the points right above them and directly to their right were mines/bad points and showed using induction that there were at most #mines "levels" containing bad points/mines if each level is the diagonal line of x+y=i for some i suffices to show that bc u cant walk on any mine/bad point so for each of these "bad levels" containing bad points/mines the #ways to get to that level from the previous level is at most 1, but for the "good levels" its always 2 so u get >=(1^m)(2^{n-m})

Me and mira74’s problem. Thanks for playing

Claim: $x,y\ge 0$. Proof: Suppose not. Then we can't have a path of length $n$ from $(0,0)$ to $(x,y)$ as $|x|+|y|>n$. $\blacksquare$. Thus, all our steps must be right or up. So $P_1=(0,1)$ or $P_1=(1,0)$. We induct on $n$. Base case $n=1$ is obvious. Suppose the problem statement is true for everything less than $n$. We will show it's also true for $n$. Case 1: For all mine-avoiding paths, $P_1=(1,0)$. Claim: For some integer $k$ so that $0< k\le n$, $(0,k)\in M$. Proof: Suppose not. Then the path $(0,0), (0,1), (0,2), \ldots, (0,n)$ is mine-avoiding, a contradiction as $P_1\ne (1,0)$ in this path. $\blacksquare$ Now we have a mine-avoiding path starting from $(1,0)$ with length $n-1$. There must be at least $2^{n-1-|M|}$ such mine-avoiding paths. Note that the mine on $(0,k)$ has no effect on the number of mine-avoiding paths as all steps are up or right, so we can take away this mine. Thus, there must be at least $2^{n-1-(|M|-1)}=2^{n-|M|}$ mine-avoiding paths, as desired. Case 2: For all mine-avoiding paths, $P_1=(0,1)$. This is analogous to the previous case. Case 3: Some mine-avoiding paths have $P_1=(1,0)$ and others have $P_1=(0,1)$. Note that for the paths where $P_1=(1,0)$, we have mine-avoiding paths starting from $(1,0)$ with length $n-1$. There are at least $2^{n-1-|M|}$ of these. Note that for the paths where $P_1=(0,1)$, we have mine-avoiding paths starting from $(0,1)$ with length $n-1$. There are at least $2^{n-1-|M|}$ of these. Thus, there are at least $2\cdot 2^{n-1-|M|}=2^{n-|M|}$ total mine-avoiding paths. We have exhausted all cases, so we are done.

Here's a different approach. We proceed by induction on \(n\), with base case \(n=0\) easy. Assume the hypothesis for length \(n-1\) paths, Let there be \(k\) mines along the line \(x+y=n\). Say \((x,y)\) with \(x+y=n-1\) is an induced mine if both \((x+1,y)\) and \((x,y+1)\) are mines. Evidently there are at most \(k-1\) induced mines. Firstly if \(k=0\), then by the inductive hypothesis there are at least \(2^{n-1-|M|}\) mine-avoiding paths of length \(n-1\). For each such path of length \(n-1\), consider progressing either north or east after the final move to produce two paths of length \(n\). Both of these paths are valid since there are no mines along \(x+y=n\), so there are at least \(2\cdot2^{n-1-|M|}=2^{n-|M|}\) mine-avoiding paths of length \(n\). Henceforth \(k\ge1\). Consider the set \(M'\), where, starting from \(M\), we remove the \(k\) mines along \(x+y=n\) and add (if they are not in \(M\) already) the \(k-1\) induced mines. Therefore \(|M'|\le|M|-1\). By the inductive hypothesis, there are at least \(2^{(n-1)-|M'|}\ge2^{n-|M|}\) paths that avoid \(M'\). From each such path, consider progressing either north or east after the final move to produce two paths of length \(n\). At least one of these paths avoids \(M\), since if the two paths both encounter mines, then the original path must contain an induced mine, contradiction. Hence there are at least \(2^{n-|M|}\) paths that avoid \(M\).

The_Turtle wrote: Me and mira74’s problem. Here's another solution, which can be thought of as "backwards induction on $|M|$." Shorten "mine-avoiding" to "safe". Claim: If there is exactly one safe path, then there are at least $n$ mines. Proof: Given a safe path, generate $n$ other potential paths by following the safe path for exactly $0 \leq k < n$ segments, then going on a straight line to $x+y=n$. Each of these $n$ new paths must contain a mine, giving $\geq n$ mines. $\blacksquare$

Now, we return to the original problem. Suppose $|M|<n$, so there are at least two safe paths. Suppose you're trying to walk on a safe path to $x+y=n$. There is some first point $(p,q)$ such that your next move isn't "forced" - that is, both $(p+1,q)$ and $(p,q+1)$ are part of at least one safe path. Consider placing a mine at whichever option is part of more safe paths, breaking ties arbitrarily. This increases the number of mines by $1$, and eliminates at least half (but not all) of the safe paths Repeat this until there is exactly one safe path. If we repeated $k$ times, there are $|M|+k$ mines at the end, so $k \geq n-|M|$ by our claim. By the halving property, we started with at least $2^k \geq 2^{n-|M|}$ safe paths, as desired.

From now on, we will use squares instead of lattice points. Let the base row and column be the row and column of the origin. We proceed with induction on $n$. For our base, the $n=2$ case is trivial. Now, assume it works for $n-1$. To show it works for $n$, we have two cases... Case 1: There is at least one mine on the base row or column. Wlog let's say the base row has a mine. If we cannot move up on the first move then that means there is at least one mine on the base column. Setting the base column to the base row lets us move up with at least one mine in the row. Now, the set of squares we can move to resembles the $n-1$ case. If we let $M'$ be the set of mines in the new set then $|M|-|M'| \geq 1$ since we have eliminated the base row which had at least one mine. Thus, we have at least $2^{n-1-|M'|} \geq 2^{n-|M|}$ mine avoiding paths. Case 2: The base row and column are both empty. Consider all paths where we move up first. Our set of squares now resembles the $n-1$ case. Notice that our set of possible mines is still $M$ since there are no mines in the base row. Thus, we have at least $2^{n-1-|M|}$ mine avoiding paths. By symmetry, we have at least $2^{n-1-|M|}$ mine avoiding paths starting with a right move. Giving at least $2^{n-|M|}$ mine avoiding paths in total.

Hmm, does this work? First, we clearly only need to consider when $|M| < n$. For any mine-avoiding path $P_0P_1\dots P_n$, define the $\emph{view}$ of a point $P_i$ with $i < n$ to be the set of lattice points on the segment from $P_i$ to the line $x + y = n$ perpendicular to $P_iP_{i+1}$. Clearly the views of $P_0$ through $P_{n-1}$ are disjoint. Hence, there exist at least $n - |M|$ indices $0\le i\le n-1$ such that there are no mines in the view of $P_i$. Consider the following operation: Either replace $P_{j}, P_{j+1}, \dots, P_n$ with the view of $P_j$ or do nothing. Suppose exactly $k$ of $P_1$ through $P_j$ had mine-free views before the operation. Since the operation fixes $P_1$ through $P_j$, the number of $P_{j+1}$ through $P_{n-1}$ with mine-free views after the operation must still be at least $n - |M| - k$. Hence, we can preform $n - |M|$ operations with increasing values of $j$ that keep the path mine-avoiding. Clearly the $2^{n-|M|}$ mine-avoiding paths produced by each sequence of $n - |M|$ operations are distinct, so we are done.

Cute. Clearly all steps must be right or up in a mine-avoiding path, so the first step must be to $(1,0)$ or $(0,1)$. We now induct on $n$ for a given set $M$; note that $n=1$ is trivial. If there are paths that start through $(1,0)$ and paths that start through $(0,1)$ (clearly a path cannot pass through both), then by inductive hypothesis we have $2^{n-1-|M|}$ paths for each start, giving a total of at least $2^{n-|M|}$ paths. If there are only paths that start through $(1,0)$ and none that start through $(0,1)$, then the path $(0,0) \to (0,1) \to \cdots \to (0,n)$ is not valid, so $(0,k) \in M$ for some $1 \leq k \leq n$. Then since we cannot go down in a path, any path that starts through $(1,0)$ will not pass through $(0,k)$. As such, letting $M'=M \setminus \{(0,k)\}$, by inductive hypothesis there are at least $2^{(n-1)-|M'|}=2^{n-|M|}$ valid paths starting through $(1,0)$. The case where there are only paths that start through $(0,1)$ is the same, covering all cases for the induction, as desired. $\blacksquare$

It is clear that $(0,0)$ is not in $M$. The proof is by induction on $n$. At $n=1$, the result is clear: for $|M|=0$ there are at least $2$ mine-avoiding paths and otherwise there are at least $1$. Observe that at least one of $(0,1)$ and $(1,0)$ is not in $M$, as otherwise there exists no mine-avoiding path. WLOG $(0,1)$ is not in $M$. There are two cases: $(1,0)$ is in $M$ and $(1,0)$ is not in $M$. In the former case, the result is clear because we can shift $(0,1)$ to $(0,0)$, the line $x+y=n$ to $x+y=n-1$, and note that because there are at most $|M|-1$ mines that could be stopping a path of length $n-1$ from $(0,0)$ to $x+y=n-1$ and there is one such path, we have at least $2^{n-|M|}$ mine-avoiding paths. In the latter case, note that there is a mine-avoiding path through at least one of $(0,1)$ and $(1,0)$. WLOG it is through $(0,1)$. Let $M_1$ denote the set of elements of $M$ in the triangle with vertices $(0,1),(n-1,1),(0,n)$. If $|M'| < |M|$, we are done for the same reason as before. So then we may assume $|M'| = |M|$. That is, every $(t,0)$ for integral $0\le t\le n$ is not in $M$. In particular, there is a mine-avoiding path through $(1,0)$. So by the same argument as before, we are done if $|M_2| < |M|$ where $M_2$ is the set of elements of $M$ in the triangle with vertices $(1,0),(n,0),(1,n-1)$. Thus we may assume $M_1=M_2=M$, meaning that there are at least $2^{n-1-|M|}+2^{n-1-|M|} = 2^{n-|M|}$ mine-avoiding paths through one of $(0,1)$ and $(1,0)$ by the induction step. We are done.

We use induction; the base case $n=1$ is easy. Let $X$ be the set of mines excluding those with $y$-value equal to $0$ and let $Y$ be the set of mines excluding those with $x$-value equal to $0$. Suppose that a path does not exist if we move upwards on the first move. Then we find that by the inductive hypothesis there are at least $2^{n-(|Y|+1)}$ paths but since there is at least one mine not in $Y$ we find that this case works. Now suppose that a path exists either way. We find by the inductive hypothesis that we need to show $$2^{n-(|X|+1)}+2^{n-(|Y|+1)}\ge 2^{n-|M|}\iff \frac{1}{2^{|X|+1}}+\frac{1}{2^{|Y|+1}}\ge \frac{1}{2^{|M|}}.$$But since $|M|\ge |X|,|Y|$ we find that if this does not hold we have $|M|=|X|=|Y|$ in which case the inequality is true anyway. We are done. $\blacksquare$ oops holden's solution is cleaner for the finish heh

For simplicity let a mine-avoiding path be a 'good' path, and let a point be 'reachable' if there is a good path to that point. Let a point be 'pseudo-reachable' if it is reachable or after removing the mine on the point, it is reachable. Let a '$k$-path' be a path where each move is $+1$ in the $x$ or $y$ direction and $0$ in the other. Claim 1: Suppose there exists a good path to $x + y = n$. Then at least $n + 1 - |M|$ points on $x + y = n$ are reachable. Proof: Induction on $n$. Base case: $n = 1$. If no mines on $(0, 1), (1, 0)$ then both are reachable, else a mine on exactly one of them and the other is reachable. Inductive step: Suppose there are $k$ mines on $x + y = n$ and there is a good path to $x + y = n$. Then there is a good path to $x + y = n-1$ so by inductive hypothesis, at least $n - (|M| - k)$ points on $x + y = n-1$ are reachable. The right neighbour of each of these lies on $x + y = n$, as well as the top neighbour of the highest reachable point on $x + y = n-1$. This gives at least $n - |M| + k + 1$ unique pseudo-reachable points on $x + y = n$. At most $k$ contain a mine, so at least $n + 1 - |M|$ points are reachable. $\square$ Suppose there are $m$ mines with $a$ of them lying within $x + y < m$, $b$ of them on $x + y = m$, and $c$ of them within $x + y > m$. Pick a $(n-m)$-path $P$. By Claim 1, there exist at least $(m + 1 - (a + b)) + b = m + 1 - a$ pseudo-reachable points on $x + y = m$. Now consider the copies of $P$ from these points to $x + y = n$. They are necessarily disjoint since each is a translation of $(d, -d)$ from the another yet paths are always non-decreasing in both coordinates. There are $b + c = m - a$ mines in $x + y \ge m$, but at least $m + 1 - a$ copies of $P$. Hence, there exists a good copy of $P$ from a pseudo-reachable point on $x + y = m$ to $x + y = n$ without a mine. Clearly no mine lies on this starting pseudo-reachable point, so it's actually reachable. Thus, we obtain a good path to $x + y = n$ ending with $P$. Repeat for all $2^{n-m}$ possible $(n-m)$-paths. Each yields a unique good path to $x + y = n$ since all $(n-m)$-paths are distinct. Hence, at least $2^{n-|M|}$ good paths to $x + y = n$ exist.

Anti-ninja paths

Start at $(0, 0)$. If both $(0, 1), (1, 0)$ are mines, then the result follows vacuously. If $(0, 1)$ is a mine, then any path is forced to go from $(0, 0)$ to $(1, 0)$, after which we can reduce to a path of length $n-1$ with $M$ decrease by one and $2^{(n-1)-(|M|-1)} = 2^{n-|M|}$. By symmetry the same holds if $(1, 0)$ is a mine. Finally, if neither are a mine, then a path can choose to go to either $(1, 0)$ or $(0, 1)$. If there are any mines with coordinate $0$, the result follows. Else, after this we can reduce to a path of length $n-1$, as $2 \cdot 2^{(n-1)-|M|} = 2^{n-|M|}$.

The bound is actually really bad. It is attainable but it is very loose. If $M$ get larger, the inequality the number of safe path is much greater than the expected bound?

We proceed with induction, with $n=1$ trivial. Suppose $n=1,2,\ldots,k-1$ all satisfy the hypothesis. Define the up- and right-routes as the paths with first step going to $(0,1)$ and $(0,1)$, respectively, and assume WLOG there exists a mine-avoiding path which is an up-route: Right-route exists: The inductive hypothesis gives us a lower bound of \[2^{(k-1)-|M|} + 2^{(k-1)-|M|} = 2^{k-|M|}.\] Right-route does not exist: In particular, the $x$-axis contains at least one mine, which can simply be ignored when considering up-routes. Thus our lower bound is still \[2^{(k-1)-(|M|-1)} = 2^{k-|M|}. \quad \blacksquare\]

We apply induction on $n$, with the base case $n=0$ being obviously true since $1 \ge 2^{-|M|}$. For the inductive step, assume that the inductive hypothesis holds for $n=k-1$. We consider the first step of the path. If the path starts by going to $(0,1)$, denote it as an upward-directed path and if it starts by going to $(1,0)$, denote it as a rightward-directed path. WLOG suppose that there exists an upward-directed mine-avoiding path. If there also exists a rightward-directed mine-avoiding path, we apply the inductive hypothesis to each direction to get the mine-avoiding number of paths is at least \[2^{(k-1)-|M|} + 2^{(k-1)-|M|} = 2^{(k-1)-|M|+1} = 2^{k-|M|}.\] Else, there must be a mine at $(i,0)$ for some positive integer $i \le n$, since otherwise a desired rightward-directed path would just consist of traveling along the $x$-axis. Thus, there is at most $|M|-1$ mines remaining in consideration of the upward-directed paths, and we can apply the inductive hypothesis to get that the number of mine-avoiding paths is at least \[2^{(k-1)-(|M|-1)} = 2^{k-|M|},\] as desired. $\blacksquare$

Stolen figure [asy][asy] size(5cm); dot((0,0)); for(int i=1; i<8; ++i) { dot((0,i),red); dot((i,0),green); for(int j=1; j<8-i; ++j) { dot((i,j),blue); } } [/asy][/asy] We induct on $n$, base case $n=1$ is obvious. Let $a,b$ and $c$ be the number of mines on the green, red, and blue regions respectively. then we have the following cases: Case 1: $a$ and $c$ are non zero. Case 2: One of them is zero. Case 3: Both are zero. Each case are proven easy by using induction hypothesis.