Two numbers $x$ and $y$ are chosen at random from the numbers $1,2,3,4,\ldots,2004$. The probability that $x^3+y^3$ is divisible by $3$ is?
The correct answer is $\dfrac13$ while mine is $\dfrac{445}{2003}$
My attempt:
For $x^3+y^3$ to be divisible by $3$, EITHER both $x$ and $y$ should be a multiple of $3$ OR one of them should leave remainder $1$ when divided by $3$ and the other should leave remainder $2$.
Therefore, $$\text{no. of ways} = \frac{668 \times 667 + 668\times 668}{2004\times 2003} = \frac{445}{2003}$$
With replacement
As you basically note $x^3+y^3 \equiv x+y \pmod 3$, which follows from Fermat's Little Theorem.
We note that $2004 \equiv 0 \pmod 3$, so there's exactly $2004/3=668$ numbers equivalent to $i \pmod 3$, for all $i \in \{0,1,2\}$.
So, no matter what $x$ value is randomly chosen, there are $2004/3$ out of $2004$ (i.e., $1/3$ probability) of randomly choosing an $y$ value for which $y \equiv -x \pmod 3$.
We can do this like the method in the question: $$ \frac{\overbrace{668 \times 668}^{x \equiv 0, y \equiv 0} + \overbrace{668 \times 668}^{x \equiv 1, y \equiv 2} + \overbrace{668 \times 668}^{x \equiv 2, y \equiv 1}}{2004^2}=\frac{1}{3}. $$
Without replacement
If $x$ and $y$ are drawn without replacement, i.e., we assume $x \neq y$, then there's two distinctions: (a) when $x \equiv 0 \pmod 3$, there are $2004/3-1$ distinct $y$ values for which $x+y \equiv 0 \pmod 3$, and (b) there are $2004 \times 2003$ ordered pairs $(x,y)$, which also gives the probability: $$ \frac{\overbrace{668 \times 667}^{x \equiv 0, y \equiv 0} + \overbrace{668 \times 668}^{x \equiv 1, y \equiv 2} + \overbrace{668 \times 668}^{x \equiv 2, y \equiv 1}}{2004 \times 2003}=\frac{1}{3}. $$
To interpret this using the first method I mention, we have $1/3$ probability of any given value of $x \pmod 3$, and given a value of $x \pmod 3$, we have probability of either $667/2003$ (when $x \equiv 0 \pmod 3$) or $668/2003$ (when $x \not\equiv 0 \pmod 3$) of randomly choosing $y \equiv -x \pmod 3$. Since these are mutually exclusive events, we get the probability $$ \overbrace{\frac{1}{3} \times \frac{667}{2003}}^{x \equiv 0, y \equiv 0}+\overbrace{\frac{1}{3} \times \frac{668}{2003}}^{x \equiv 1, y \equiv 2}+\overbrace{\frac{1}{3} \times \frac{668}{2003}}^{x \equiv 2, y \equiv 1}=\frac{1}{3}. $$
The given answer seems to assume that $x \neq y$, which is this second case. However, the main problem is that it doesn't account for both cases $(x,y) \equiv (-1,1) \pmod 3$ and $(x,y) \equiv (1,-1) \pmod 3$.