How to show something is not a one-way function? Lets say that $f:\{0,1\}^* \to \{0,1\}^*$ is a strong one way function.
Let
$h(x)=f(x)||x_n$ where $x_n$ is the $n$th bit of $x$.

I understand that $h$ will not be a strong one-way function. However, I wish to gain an intuitive understanding why that is.
Actually the proof that $h$ is one-way is not that trivial... First, a reminder on definitions. A function $f$ is (strongly) one-way if for all probabilistic polynomial-time adversaries $A$, all polynomials $p$ and all sufficiently large $n$, we have
$$\mathrm{Pr}[A(f(U_n),1^n) \in f^{-1}(U_n)] &lt; \frac{1}{p(n)}$$
(where $U_n$ represents a random variable with uniform distribution over all strings of length $n$). Put in words, we choose uniformly a string $x$ of length $n$, we compute $y = f(x)$ and we run $A$ on input $(y,1^n)$, noting its output $x'$. Then the definition states that the probability that $f(x') = y$ is less than $1/p(n)$. We prove that $h$ is one-way by contradiction. That is, assuming that $h$ is not one-way, we show that $f$ is not one-way, contradicting our hypothesis.

So what does it mean to say that $h$ is not one-way. It is easily seen that "all sufficiently large" is equivalent to "all but a finite number", so we obtain the following. There is a probabilistic polynomial-time algorithm $A_h$ and a polynomial $p_h$ such that for infinitely many $n$ we have
$$\mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n)] \ge \frac{1}{p_h(n)}.$$
We restrict out attention to such $n$. We will show that there is a probabilistic polynomial-time algorithm $A_f$ and a polynomial $p_f$ such that for all such (infinitely many) $n$, we have
$$\mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n)] \ge \frac{1}{p_f(n)}.$$

$A_f$ works as follows, on input $(f(U_n), 1^n)$ (that is, on input $(y,1^n)$ where $y = f(x)$ for a uniformly chosen $x$ of length $n$).


Run $s \gets A_h(y||0,1^n)$. If $f(s) = y$, output $s$ and halt.
Run $t \gets A_h(y||1,1^n)$. If $f(t) = y$, output $t$ and halt.
Output $0^n$ and halt.


$A_f$ clearly runs in probabilistic polynomial-time, and we analyse its success probability. We observe that if the last bit of $U_n$ is $0$ and the call to $A_h$ in step 1 succeeds, then $A_f$ will succeed. Likewise, if the last bit of $U_n$ is $1$ and the call to $A_h$ in step 2 suceeds, $A_f$ succeeds. Hence (letting $\mathrm{last}(X)$ be the last bit of $X$)
$$\mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 0] \ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 0] $$
and
$$\mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 1] \ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 1].$$

Now,
$$\begin{align*}
\mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n)]
  &amp;= \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \wedge \mathrm{last}(U_n) = 0] \\
  &amp;\quad {}+{} \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \wedge \mathrm{last}(U_n) = 1] \\
  &amp;= \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 0]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 0] \\
  &amp;\quad {}+{} \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 1]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 1] \\
  &amp;\ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 0]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 0] \\
  &amp;\quad {}+{} \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 1]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 1] \\
  &amp;\ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \wedge \mathrm{last}(U_n) = 0] \\
  &amp;\quad {}+{} \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \wedge \mathrm{last}(U_n) = 1] \\
  &amp;\ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n)] \\
  &amp;\ge \frac{1}{p_h(n)}.
\end{align*}$$