First off, since $ p$ and $ q$ are relatively prime, any integer $ x$ can be represented in the form $ x = ap + bq$ where $ a,b$ are integer coefficients. Second, it is clear that every ideal subset contains a subset $ T = \{ up + vq : u,v\in\mathbb{N}_0 \}$, implying that ideal subsets can differ only by elements $ ap + bq\not\in T$ (hence, it is necessary that either $ a$ or $ b$ is negative). Notice that if $ x = ap + bq$ then $ x = (a\pm q)p + (b\mp p)q$, implying that every positive integer $ x$ that is not in $ T$ admit a reduced form: $ x = ap + bq$ with $ - q < a < 0$, $ 0 < b < p$, and $ \frac {b}{ - a} > \frac {p}{q}$ It is clear that if an ideal subset contains $ x = ap + bq$ then it also contains $ up + vq$ for all $ u\geq a$ and $ v\geq b$. Therefore, every ideal subset is uniquely defined by a pair of sequences: $ q > - a_1 > - a_2 > \dots > - a_m > 0$ and $ p > b_1 > b_2 > \dots > b_m > 0$ with $ \frac {b_j}{ - a_j} > \frac {p}{q}$ for all $ j=1,\dots,m$. It is easy to see that every pair of such sequences define a path from $ (0,0)$ to $ (q,p)$ in the integer grid $ [0,q]\times[0,p]$ where every step increments both coordinates and does not go below the line connecting the points $ (0,0)$ and $ (q,p)$.

I think your answer is incorrect, unless I'm misunderstanding the question. Consider $ (p,q)=(3,5)$. Clearly the set contains at least $ \mathbb{N}_0/\{1,2,4,7\}$ Depending on our choices of which numbers to include in the set, we can also achieve each of: $ \mathbb{N}_0/\{1,2,4\}$ (include only $ 7$ extraneously) $ \mathbb{N}_0/\{1,2\}$ (include $ 4$ extraneously, which auto-adds $ 7$) $ \mathbb{N}_0/\{1,4\}$ (include $ 2$) $ \mathbb{N}_0/\{2\}$ (include $ 1$) $ \mathbb{N}_0/$ (include $ 1$ and $ 2$) This yields 6 different sets, which is NOT $ {6 \choose 2}$ as your solution states.

me@home, thanks for the (counter)example. I've corrected the solution and got the answer as the number of paths in the integer grid but no closed formula yet. In particular, the six ideal sets in your example with $ p=3$ and $ q=5$ correspond to the following paths: (0,0) -> (5,3) (0,0) -> (1,1) -> (2,3) -> (5,3) (0,0) -> (1,1) -> (3,3) -> (5,3) (0,0) -> (1,3) -> (5,3) (0,0) -> (2,3) -> (5,3) (0,0) -> (3,3) -> (5,3)

Previously, I found only 6 different sets, while there are actually seven - I missed $ \mathbb{N}_0/\{1\}$ I've thought about this a little more, and its actually a rather deep problem. For instance, I've solved the trivial case when $ (p,q)=(n,n+1)$. Then, the numbers can be arranged into a "triangle of implication" and the number of sets is equal to $ \frac{{ 2n \choose n}}{n+1}$, which is a Catalan number. Extending the idea of a triangle of implication, I've come up with some ways to efficiently compute answers (in, say, a computer algorithm) but no nice closed form answers. I'm sort of confident about this because lots of particular answers are rather large primes... all in all i'm confused about how this could have been a proposed contest problem.

At kalva there is a page proposing similar ideas for this problem, and a closed formula: http://web.archive.org/web/20060925154521/http://www.kalva.demon.co.uk/short/soln/sh00c6.html. However, it's very too long to read, which really decourages people. A well-structured proof (probably with lemmata and clear drawings) in LaTeX on this site would still be highly appreciated!

Another solution is given at http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1218952