15. From $1,2, \cdots, 2004$, choose $k$ numbers such that among the chosen $k$ numbers, there are definitely 3 numbers that can form the side lengths of a triangle (here it is required that the three side lengths of the triangle are all different). What is the minimum value of $k$ that satisfies the condition?
15. This problem is equivalent to:

Selecting $k-1$ numbers from $1,2, \cdots, 2004$, such that no three of these numbers can form the lengths of the sides of a triangle (all sides being unequal). What is the maximum value of $k$ that satisfies this condition?
For any array that meets the above conditions,
when $k=4$, the smallest 3 numbers are $1,2,3$. From this, the array can be continuously expanded: as long as the number added is greater than or equal to the sum of the two largest numbers already in the array. Therefore, to maximize $k$, the number added should be equal to the sum of the two largest numbers in the array. Thus, we get:
$$
\begin{array}{l}
1,2,3,5,8,13,21,34,55,89,144, \\
233,377,610,987,1597
\end{array}
$$

There are 16 numbers in total. For any array $a_{1}, a_{2}, \cdots, a_{n}$ that meets the above conditions, it is clear that $a_{i}$ is always greater than or equal to the $i$-th number in (1). Therefore, $n \leqslant 16 \leqslant k-1$. Hence, the minimum value of $k$ is 17.