Barry Cox had an elegant approach with a nice twist, also observed by Franz Pichler:

The only equation you need for this is V − E + F = 2. The key thing to realize is that when you truncate P to form Q, you force all of the vertices of Q to be the intersection of 3 edges. From this, you get ...

V = 2E/3

... and of course,

E = 3V/2

Using the first formula, we end up with

V = 2(F − 2)

E = 3(F − 2)

Obviously, 2 and 3 are not factors of 1001, so that must be F. For Q, we have

F = 1001

V = 1998

E = 2997

But observe that we learn something about the initial polyhedron P. If P has
f faces, e edges, and v vertices, then

f + v = F = 1001

Therefore, Euler's formula yields e = 999.

So the problem could have been posed as: One of V, E, F is 1001. How many
edges are in the first polyhedron P?

Jerry Grossman observes that "the simplest case for P in this problem
appears to be a prism over a 333-gon. The number of vertices is, ominously,
666."