Let $n \geq 4$, and consider a (not necessarily convex) polygon $P_1P_2\hdots P_n$ in the plane. Suppose that, for each $P_k$, there is a unique vertex $Q_k\ne P_k$ among $P_1,\hdots, P_n$ that lies closest to it. The polygon is then said to be [i]hostile[/i] if $Q_k\ne P_{k\pm 1}$ for all $k$ (where $P_0 = P_n$, $P_{n+1} = P_1$).

(a) Prove that no hostile polygon is convex.
(b) Find all $n \geq 4$ for which there exists a hostile $n$-gon.
(a) We need to prove that no convex polygon \( P_1P_2 \cdots P_n \) is hostile. 

1. **Define the length of a diagonal** \( P_i P_j \) for \( 1 \le i < j \le n \) to be \( \min(j - i, n - (j - i)) \). This definition helps us measure the shortest path between two vertices in a cyclic manner.

2. **Define a tasty diagonal**: A diagonal \( P_i P_j \) is called tasty if either \( Q_i = P_j \) or \( Q_j = P_i \). 

3. **Consider the tasty diagonal of minimum length**: Without loss of generality (WLOG), assume the tasty diagonal \( P_i P_j \) has length \( j - i \) for \( 1 \le i < j \le n \). Suppose \( Q_i = P_j \).

4. **Case analysis**:
   - If \( j = i + 1 \), then \( P_i P_j \) is an edge of the polygon, which contradicts the definition of a hostile polygon since \( Q_i \ne P_{i \pm 1} \).
   - If \( j > i + 1 \), consider \( Q_{i+1} \). If \( Q_{i+1} = P_k \) where \( i \le k \le j \), then \( P_{i+1} Q_{i+1} \) is a tasty diagonal with length less than \( P_i P_j \), contradicting the assumption that \( P_i P_j \) is the shortest tasty diagonal.

5. **Intersection and contradiction**:
   - If \( P_{i+1} Q_{i+1} \) intersects \( P_i Q_i \) in its interior, apply the Triangle Inequality twice:
     \[
     P_i Q_i + P_{i+1} Q_{i+1} > P_i Q_{i+1} + P_{i+1} Q_i
     \]
   - This inequality contradicts the fact that \( P_i Q_i < P_i Q_{i+1} \) and \( P_{i+1} Q_{i+1} < P_{i+1} Q_i \).

6. **Symmetry**: The case where \( Q_j = P_i \) is analogous. We can reverse the labels of the \( P_i \)'s and use the same argument.

Thus, no convex polygon can be hostile. 

\(\blacksquare\)

(b) We need to find all \( n \ge 4 \) for which there exists a hostile \( n \)-gon.

1. **Constructing a hostile polygon**: For \( n \ge 4 \), we can construct a hostile polygon by ensuring that each vertex \( P_k \) has a unique closest vertex \( Q_k \) that is not adjacent to \( P_k \).

2. **Zigzag construction**: One way to achieve this is by creating a polygon that "zigzags" a lot. For example, consider a polygon where vertices are placed such that each vertex \( P_k \) has its closest vertex \( Q_k \) at a non-adjacent position.

3. **Verification**: By carefully placing the vertices, we can ensure that the conditions for a hostile polygon are met. This construction can be done for any \( n \ge 4 \).

Thus, there exists a hostile polygon for all \( n \ge 4 \).

\(\blacksquare\)

The final answer is \( \boxed{ n \ge 4 } \)