MathNet 2006 — Part 03 Question 171

Let $M$ be a subset of $\{1, 2, \dots, 2006\}$ with the following property: For any three elements $x, y$ and $z$ ($x \lt y \lt z$) of $M$, $x + y$ does not divide $z$. Determine the largest possible size of $M$. Justify your claim.