Let $P$ be a regular $n$-gon $A_1A_2\ldots A_n$. We aim to find all positive integers $n$ such that for each permutation $\sigma(1), \sigma(2), \ldots, \sigma(n)$, there exists $1 \le i, j, k \le n$ such that the triangles $A_iA_jA_k$ and $A_{\sigma(i)}A_{\sigma(j)}A_{\sigma(k)}$ are both acute, both right, or both obtuse.

Consider first a regular $2n$-gon for $n \ge 2$. Let $A_i$ and $A_j$ be two vertices which are diametrically opposite. If $A_{\sigma(i)}$ and $A_{\sigma(j)}$ are still diametrically opposite, then any third vertex $A_k$ will work since $\angle A_iA_kA_j = 90^\circ = \angle A_{\sigma(i)}A_{\sigma(k)}A_{\sigma(j)}$.

Otherwise, let $A_k$ be the vertex such that $A_{\sigma(k)}$ is diametrically opposite to $A_{\sigma(i)}$. Then $\angle A_iA_kA_j = 90^\circ = \angle A_{\sigma(i)}A_{\sigma(j)}A_{\sigma(k)}$. Note that this is trivially true for an equilateral triangle, but it is false for a regular pentagon (consider $ABCDE$ and $A'D'B'E'C'$).

Consider now a regular $2n+1$-gon for $n \ge 3$. Clearly, there are no right triangles. The number of obtuse triangles with a particular diagonal as the longest side is equal to the number of vertices between the endpoints of this diagonal, going the shorter way.

Since there are $2n+1$ diagonals of each length, the total number of obtuse triangles is
$$(2n+1)\sum_{i=1}^{n-1} i = \frac{1}{2}(n-1)n(2n+1).$$
The total number of triangles is
$$\binom{2n+1}{3} = \frac{1}{3}(2n-1)n(2n+1).$$
Since
$$\frac{\frac{1}{2}(n-1)}{\frac{1}{3}(2n-1)} = \frac{1}{2} + \frac{n-2}{4n-2} > \frac{1}{2}$$
for $n \ge 3$, there are more obtuse triangles than acute ones. By the pigeonhole principle, there exist 3 vertices such that their initial and permuted positions both determine obtuse triangles.

Therefore, the property holds for all $n$ except $n = 5$.

The answer is: \boxed{n \neq 5}.