From the set of all permutations $f$ of $\{1, 2, ... , n\}$ that satisfy the condition:
$f(i) \geq i-1$   $i=1,...,n$
one is chosen uniformly at random. Let $p_n$ be the probability that the chosen permutation $f$ satisfies
$f(i) \leq i+1$  $i=1,...,n$
Find all natural numbers $n$ such that $p_n > \frac{1}{3}$.
1. **Define the sets and initial conditions:**
   - Let \( A_n \) be the number of permutations \( f \) of \(\{1, 2, \ldots, n\}\) satisfying \( f(i) \geq i-1 \) for \( i = 1, \ldots, n \).
   - Let \( B_n \) be the number of permutations \( f \) of \(\{1, 2, \ldots, n\}\) satisfying both \( f(i) \geq i-1 \) and \( f(i) \leq i+1 \) for \( i = 1, \ldots, n \).

2. **Calculate \( A_n \):**
   - We have \( A_{n+1} = 2A_n \). This is because:
     - If \( f(n+1) = n+1 \), the rest of the permutation is one satisfying the inequality for \(\{1, \ldots, n\}\), giving \( A_n \) permutations.
     - If \( f(n+1) = n \), there exists \( i_0 \in \{1, \ldots, n\} \) such that \( f(i_0) = n+1 \). The function \(\Phi\) maps this to a permutation of \(\{1, \ldots, n\}\) satisfying the inequality, giving another \( A_n \) permutations.
   - Therefore, \( A_{n+1} = 2A_n \).
   - Given \( A_1 = 1 \), we deduce \( A_n = 2^{n-1} \).

3. **Calculate \( B_n \):**
   - We have \( B_{n+1} = B_n + B_{n-1} \). This is because:
     - If \( f(n+1) = n+1 \), the rest of the permutation is one satisfying both inequalities for \(\{1, \ldots, n\}\), giving \( B_n \) permutations.
     - If \( f(n+1) = n \), then \( f(n) = n+1 \) and the rest of the permutation is one satisfying both inequalities for \(\{1, \ldots, n-1\}\), giving \( B_{n-1} \) permutations.
   - Therefore, \( B_{n+1} = B_n + B_{n-1} \).
   - Given \( B_1 = 1 \) and \( B_2 = 2 \), we solve this linear recurrence relation.

4. **Solve the recurrence relation for \( B_n \):**
   - The characteristic equation of the recurrence relation \( B_{n+1} = B_n + B_{n-1} \) is \( x^2 = x + 1 \), which has roots \( \alpha = \frac{1 + \sqrt{5}}{2} \) and \( \beta = \frac{1 - \sqrt{5}}{2} \).
   - Thus, the general solution is \( B_n = c_1 \alpha^n + c_2 \beta^n \).
   - Using the initial conditions \( B_1 = 1 \) and \( B_2 = 2 \):
     \[
     \begin{cases}
     c_1 \alpha + c_2 \beta = 1 \\
     c_1 \alpha^2 + c_2 \beta^2 = 2
     \end{cases}
     \]
   - Solving this system, we find \( c_1 = \frac{3 + \sqrt{5}}{5} \) and \( c_2 = \frac{2 - \sqrt{5}}{5} \).
   - Therefore, \( B_n = \frac{3 + \sqrt{5}}{5} \left( \frac{1 + \sqrt{5}}{2} \right)^n + \frac{2 - \sqrt{5}}{5} \left( \frac{1 - \sqrt{5}}{2} \right)^n \).

5. **Calculate \( p_n \):**
   - The probability \( p_n \) is given by:
     \[
     p_n = \frac{B_n}{A_n} = \frac{B_n}{2^{n-1}}
     \]
   - Substituting \( B_n \) and \( A_n \):
     \[
     p_n = \frac{\frac{3 + \sqrt{5}}{5} \left( \frac{1 + \sqrt{5}}{2} \right)^n + \frac{2 - \sqrt{5}}{5} \left( \frac{1 - \sqrt{5}}{2} \right)^n}{2^{n-1}}
     \]
   - Simplifying, we get:
     \[
     p_n = \frac{3 + \sqrt{5}}{5} \left( \frac{1 + \sqrt{5}}{4} \right)^n + \frac{2 - \sqrt{5}}{5} \left( \frac{1 - \sqrt{5}}{4} \right)^n
     \]

6. **Determine \( n \) such that \( p_n > \frac{1}{3} \):**
   - It is straightforward to see that \( p_n \leq 2 \left( \frac{1 + \sqrt{5}}{4} \right)^n \).
   - Since \( \frac{1 + \sqrt{5}}{4} \approx 0.809 \), we have \( p_n < \frac{1}{3} \) for \( n > 8 \).
   - Direct checking shows that \( n \) such that \( p_n > \frac{1}{3} \) are \( 1, 2, 3, 4, 5, 6 \).

The final answer is \( \boxed{ \{1, 2, 3, 4, 5, 6\} } \).