Let the complex number $z = \cos\tfrac{1}{1000} + i \sin\tfrac{1}{1000}.$ Find the smallest positive integer $n$ so that $z^n$ has an imaginary part which exceeds $\tfrac{1}{2}.$
1. Given the complex number \( z = \cos\left(\frac{1}{1000}\right) + i \sin\left(\frac{1}{1000}\right) \), we can write it in polar form as \( z = \text{cis}\left(\frac{1}{1000}\right) \), where \(\text{cis} \theta = \cos \theta + i \sin \theta \).

2. By De Moivre's Theorem, for any integer \( n \), we have:
   \[
   z^n = \left( \text{cis} \frac{1}{1000} \right)^n = \text{cis} \left( \frac{n}{1000} \right)
   \]
   This means:
   \[
   z^n = \cos \left( \frac{n}{1000} \right) + i \sin \left( \frac{n}{1000} \right)
   \]

3. We need to find the smallest positive integer \( n \) such that the imaginary part of \( z^n \) exceeds \(\frac{1}{2}\). The imaginary part of \( z^n \) is given by:
   \[
   \Im(z^n) = \sin \left( \frac{n}{1000} \right)
   \]

4. We need:
   \[
   \sin \left( \frac{n}{1000} \right) > \frac{1}{2}
   \]

5. The smallest angle \(\theta\) for which \(\sin \theta > \frac{1}{2}\) is \(\theta = \frac{\pi}{6}\). Therefore, we need:
   \[
   \frac{n}{1000} > \frac{\pi}{6}
   \]

6. Solving for \( n \):
   \[
   n > 1000 \cdot \frac{\pi}{6}
   \]

7. Using the approximation \(\pi \approx 3.14159\):
   \[
   n > 1000 \cdot \frac{3.14159}{6} \approx 1000 \cdot 0.523598 \approx 523.598
   \]

8. Since \( n \) must be an integer, the smallest integer greater than 523.598 is 524.

Conclusion:
The smallest positive integer \( n \) such that the imaginary part of \( z^n \) exceeds \(\frac{1}{2}\) is \( \boxed{524} \).