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."