Equivalence of minimization problems for Lipschitz function 
Assume that $f: \mathbb{R}^n \rightarrow \mathbb{R} $ is Lipschitz continuous with constant $M$ and that $S \subseteq \mathbb{R}^n$  is closed. Show that for $\lambda > M$ problem of minimizing $f(x) + \lambda d(x, S)$, where $d(x,S)$ is a distance from $x$ to $S$ have the same solutions as problem of minimizing $f(x)$ over $S$.

I know that because $S$ is closed, then there exists $b \in S$ such that $d(x, S) = d(x, b)$,
Because I now have some $b$ I can use Lipschitz condition to get $d(f(x), f(b)) \leq M d(x, b)$. But I don't see how to proceed further or if this actually gives something useful.
Edit: I have tried the following, but I got stuck
Let $x_S$ be the solution to the problem of minimizing $f(x)$ over $S$. Because $x_S \in S$ we have $d(x_S, S) = 0$.

*

*Assume $\hat x \in S$ is a solution to the problem of minimizing $f(x) + \lambda d(x, S)$. Because $\hat x \in S$ we have $d(\hat x, S) = 0$. Because it is a solution to the problem of minimizing $f(x) + \lambda d(x, S)$ we have that $f(\hat x) < f(x_S)$. But both points are in $S$ and $x_S$ minimizes $f(x)$ over $S$, so we have contradiction.

*Assume $\hat x \notin S$ is a solution to the problem of minimizing $f(x) + \lambda d(x, S)$. Then because $S$ is closed we have $d(\hat x, S) > 0$ (If $S$ wasn't closed then points from boundary of $S$ wouldn't be in $S$ and their distance to $S$ would be $0$). So we have $$f(\hat x) + \lambda d(\hat x, S) < f(x_S) + \lambda d(x_S, S) = f(x_S)$$
$$f(\hat x) - f(x_S) < - \lambda d(\hat x, S)$$
Both sides are negative, so by taking abolute value on both sides we get
$$|f(\hat x) - f(x_S)| > \lambda d(\hat x, S) > M d(\hat x, S)$$
Basically I wanted to get a contradiction with Lipschitz condition but for that I would need something like $d(\hat x, S) = d(\hat x, x_S)$ which I am not sure I can get. Buth this is what I have tried.

Edit 2:
Now I understand that I can frame minimization of $f(x)$ over $S$ as
$$\text{minimize } f(x)\\ \text{such that }d(x,S) = 0$$
Then $$\text{minimize} f(x) + \lambda d(x, S)$$ looks like a Lagrangian. Basically I think this changes the question to question about strong duality of this problem. Maybe.
 A: Lipschitz property of $f(\cdot)$ implies that
$$\| f(\mathbf{y})-f(\mathbf{x}^*)\|\leq M\| \mathbf{y}-\mathbf{x}^*\| <\lambda\| \mathbf{y}-\mathbf{x}^*\| $$
Now, let $\mathbf{x}^*$ be the optimal solution and assume $\mathbf{x}^*\notin S$. From the optimality of $\mathbf{x}^*$ we know that:
$$ f(\mathbf{x}^*)+\lambda \overbrace{\|\mathbf{y}-\mathbf{x}^*\|}^{d_s(\mathbf{x}^*)}\leq f(\mathbf{x}^s)$$
where $\mathbf{x}^s\in S$ is an optimal solution if we would restrict the domain to $S$ and $\mathbf{y}\in S$. Rearranging the terms and applying a norm on the inequality we get \begin{aligned}
&\lambda\|\mathbf{y}-\mathbf{x}^*\|\leq f(\mathbf{x}^s)-f(\mathbf{x}^*)\leq f(\mathbf{y})-f(\mathbf{x}^*) \Longrightarrow \\ &\lambda\|\mathbf{y}-\mathbf{x}^*\|\leq \| f(\mathbf{y})-f(\mathbf{x}^*)\|\end{aligned}
where we know from the optimality of $\mathbf{x}^s$ over $S$ that $f(\mathbf{x}^s)\leq f(\mathbf{y})$. However this is contradiction to the Lipschitz property. Therefore the optimal solution must be in $S$, and the problems $\min_{\mathbf{x}\in \mathbb{R}^n} \{f(\mathbf{x})+\lambda d_s(\mathbf{x})\}, \; \min_{\mathbf{x}\in s} \{f(\mathbf{x})\}$ are equivalent.
