This is Frobenius stamps problem, case $n=2$, also known as Sylvester's problem. All positive integers no less than $pq-p-q+1$ can be expressed as $mp + nq$, and exactly half of the other cannot ...

Define $[n]_q$ as the remainder when $n$ is divided by $q$, and for $0\le i\le q-1$, let $a_i$ denote the smallest integer such that $qa_i+[pi]_q\in S$. Then it's clear that $S$ is ideal iff $a_0=0$ and for $1\le i\le q-1$, $0\le a_i\le a_{i-1}+\frac{p+[p(i-1)]_q-[pi]_q}{q}=a_{i-1}+\left\lfloor\frac{pi}{q}\right\rfloor-\left\lfloor\frac{p(i-1)}{q}\right\rfloor$ (consider "jumping" between the residue classes $p(i-1)\pmod{q}$ and $pi\pmod{q}$), i.e. if $b_i=a_i-\left\lfloor\frac{pi}{q}\right\rfloor$ for $0\le i\le q-1$ with $b_0=0$, then there is a clear bijection between the ideal subsets and the nonincreasing lattice paths (each step of length $1$) from $(0,0)$ to $(q,-p)$ that never drop below the line $px+qy=0$. Now take $t_i=p$ if the $i^{th}$ step is rightward and $t_i=-q$ if the $i^{th}$ step is downward so that $t_1+\cdots+t_{p+q}=0$, and consider the partial sums $s_i=t_1+\cdots+t_i$ for $1\le i\le p+q$. Since $p,q$ are relatively prime, they are pairwise distinct. Notice that the index $1\le m\le p+q$ that minimizes $s_m$ is the only one that satisfies $s_{i+m}-s_m\ge0$ for all $1\le i\le p+q$ (indices taken $\pmod{p+q}$). But $S$ is ideal iff $s_i\ge0$ for all $i$, so exactly one cyclic shift of indices gives a working $S$, i.e. there are \[\frac{1}{p+q}\binom{p+q}{p}\]ideal subsets.

The answer is $\frac{1}{p+q}\binom{p+q}{p}$. Assume $p < q$. We create a Young tableaux (in English notation) as follows: the top row consists of the numbers $\{ (p-1)q, (p-2)q, \dots, q, 0 \}$ in that order and a column starting with $kq$ has has all the positive numbers of the form $\{kq-p, kq-2p, \dots\}$. An example with $(p,q) = (4,7)$ is shown below. \[ \begin{bmatrix} 21 & 14 & 7 & 0 \\ 17 & 10 & 3 \\ 13 & 6 & \\ 9 & 2 \\ 5 \\ 1 \end{bmatrix} \]The main idea is that an ideal set of $S$ corresponds exactly to a subset of this Young tableau which is closed upwards and to the left, and contains the top row. In fact readers familiar with the Frobenius coin problem (or the chicken mc-nugget variation) will notice that the $\tfrac12(p-1)(q-1)$ entries not in the top row correspond to exactly the elements not obtained by coins of weights $p$ and $q$. To count this, we give another bijection: it's equivalent to the number of up-right paths from $A = (0,0)$ to $B = (p,q)$ that stay above the diagonal line. Indeed, we can situate the Young tableu with the upper-right $0$ positioned at $B$; then given a path from $A$ to $B$ we take all the elements of the tableaux on or above this path. [asy][asy] draw( (0,0)--(4,7) ); dot("$0$", (4,7), dir(45), blue+4); dot("$7$", (3,7), dir(135), blue); dot("$3$", (3,6), dir(135), blue); dot("$14$", (2,7), dir(135), blue); dot("$10$", (2,6), dir(135), blue); dot("$6$", (2,5), dir(135), blue); dot("$2$", (2,4), dir(135), blue); dot("$21$", (1,7), dir(135), blue); dot("$17$", (1,6), dir(135), blue); dot("$13$", (1,5), dir(135), blue); dot("$9$", (1,4), dir(135), blue); dot("$5$", (1,3), dir(135), blue); dot("$1$", (1,2), dir(135), blue); dot("$A$", origin, dir(225), red+4); for (int i=1; i<=7; ++i) dot( (0,i), grey+1.5); for (int i=0; i<=1; ++i) dot( (1,i), grey+1.5); for (int i=0; i<=3; ++i) dot( (2,i), grey+1.5); for (int i=0; i<=5; ++i) dot( (3,i), grey+1.5); for (int i=0; i<=6; ++i) dot( (4,i), grey+1.5); [/asy][/asy] Then it's a classical problem that the number of such paths is $\frac{1}{p+q} \binom{p+q}{p}$. (The proof is by the ``cyclic shift method'': show that given a sequence of $p$ right moves and $q$ left moves, exactly one cyclic shift of this sequence gives a valid path.)

We claim that the number of ideal sets is $\frac{1}{p+q}\binom{p+q}{p}$. To see this, label the lattice points $(x,y)$ that satisfy $0\le x\le p$ and $y\ge 0$ with the number $py-qx$. The first claim is that every nonnegative integer label is achieved at some point. Since $p$ and $q$ are relatively prime, for every $n$, there are some integers $x'$ and $y'$ such that $py'-qx'=n$. Note that $(x'+kp,y'+kq)$, so we have some solution $(x,y) $ with $0\le x\le p$. Then, $y=\frac{n+qx}{p}\ge 0$, as desired. For any ideal set $S$, let $A$ be the lattice points that have label in $S$. It is easy to see that if $(x,y)\in A$, then $(x-a,y+b)\in S$ for all nonnegative integers $a$ and $b$. Since $0\in S$, we have that $(0,0),(p,q)\in A$. Thus, any $(x,y)$ with $y\ge q$ is automatically in $A$. Therefore, we may restrict our attention to the region $0\le x\le p$ and $0\le y\le q$, such that $py-qx\ge 0$. In particular, it suffices to determine what subset of these lattice points may be in $A$. As we noted, if $(x,y)\in A$, then $(x-1,y+1)\in A$ as well (as long as $(x-1,y+1)$ has a label). Thus, the points of $A$ in this region are exactly points above some path that only goes up and to the right from $(0,0)$ to $(p,q)$, staying above the line $py-qx=0$. Conversley, note that any $A$ that is of this forms leads to an ideal $S$. Thus, the number of ideal sets is simply the number of lattice paths from $(0,0)$ to $(p,q)$ that are always in the region $py-qx\ge 0$. The path is made up of $p+q$ steps, which we denote as $w_1,\ldots,w_{p+q}\in\{p,-q\}$. Here, $w_i=p$ corresponds to going up one unit, and $w_i=-q$ corresponds to going right one unit. We wish to count the number of such sequences that satisfy $w_1+\cdots+w_{p+q}=0$ and \[\sigma_{n}:=w_1+\cdots+w_n\ge 0\]for all $n\in[0,p+q-1]$. For any sequence, not necessarily satisfying $\sigma_{n}\ge 0$, we claim that exactly one cyclic shift of it works. Let $m$ be the index such that $\sigma_{m}$ is minimal. Clearly, if $\sigma_{m}<0$, then the sequence is invalid, so if the sequence is valid, then $\sigma_{m}=0$. But if $m\ne 0$, then we have $py-qx=0$ for $0\le x\le p$ and $0\le y\le q$ with $(x,y)\ne(0,0),(p,q)$, which can't happen since $p$ and $q$ are relatively prime. Thus, if the sequence is valid, then the we have the minimum at the start. Conversely, consider the sequence $(w_{m+1},\ldots,w_{p+q},w_1,\ldots,w_m)$. Here, all the partial sums are nonnegative since they are of the form $\sigma_n-\sigma_m$ for some $n$. Thus, this is the one and only cyclic shift of any given sequence that is valid. Thus, for all $\binom{p+q}{p}$ paths from $(0,0)$ to $(p,q)$, exactly one from the $p+q$ cyclically equivalent paths stays above $py-qx=0$, so there are a total of $\boxed{\frac{1}{p+q}\binom{p+q}{p}}$ such paths.

I claim that the answer is $\frac{1}{p+q}\binom{p+q}{q}$. Note that, by the Frobenius Coin Problem, all numbers larger than $mn-m-n$ are in an ideal set $S$. Call a number $i$, a generator, if $i\in S$, $i-jp-kq\not\in S\forall (j,k)\in(\mathbb{Z}_{\ge_0}^2\setminus(0,0))$. Then, $0$ is always a generator, and we have that $S$ is uniquely determined by its set of generators. We will now construct a bijection between the number of ideal sets and the number of gridwalks from $(0,0)$ to $(p,q)$ which do not pass $qx-py=0$. Suppose we number every lattice point such that $(x,y)$ is given the number $qx-py$. Obviously, the set of points enclosed by $\{qx-py>0, y>0,x<p\}$ all contain distinct labels, and I claim that these labels are precisely the numbers which cannot be expressed as $ip+jq$ for $i,j\in\mathbb{Z}_{\ge 0}$. If we assumed the contrary, then $ip+jq=xq-yp\implies (i+y)p=(x-j)q$, so $x-j$ is a positive multiple of $p$, which is absurd since $x<p$. Thus, the set of possible generators is entirely enclosed within this triangle. To choose a suitable set of generators, no generator can be $ip+jq$ more than another one, for $i,j\in\mathbb{Z}_{\ge 0}$, and in the coordinate plane, this corresponds to two points such that the line connecting them has negative slope. So, to choose a valid set of generators, we pick $(x_1,y_1),\ldots,(x_k,y_k)$ such that $\{x_i\}$ and $\{y_i\}$ are both increasing. Now, if we interpret these points as "peaks" of a path from $(0,0)$ to $(p,q)$ (i.e. points $(x,y)$ such that $y$ is strictly larger than the height of all other points on the path with $x$ coordinate $\le x$), we can easily see that any choice of generators does indeed correspond with a path of the aforementioned form, and vice versa. So, we have a bijection. To count such paths, consider a sequence of moves, consisting of $p$ "rights" and $q$ "ups," say $P=m_1m_2\ldots m_{p+q}$. If $P$ is a valid path, and we consider a cycle shift of it: $m_im_{i+1}\ldots m_{p+q}m_1\ldots m_{i-1}$, note that the ratio of ups to rights in $m_1\ldots m_{i-1}$ is strictly less than $\frac{q}{p}$, so this ratio is greater than $\frac{q}{p}$ in $m_i\ldots m_{p+q}$. Thus, this path crosses $y=\frac{q}{p}x$ at some point in the first $p+q+1-i$ positions. On the other hand, if we are given an arbitrary path $P$, we can construct a valid cyclic permutation of it by considering the following algorithm: Consider the first move, $m_i$ for which $P$ crosses the line. Then, take the cyclic permutation $m_{i+1}\ldots m_i$, and repeat. After each iteration, the number of contiguous moves starting from the end which do not cross the line is strictly increasing, so this process eventually terminates, yielding a good path. Combining these two results, we see that each permutation of $p$ "rights" and $q$ "ups" has exactly one good cyclic permutation. $\gcd(p,q)=1$, so no permutations yield cyclic symmetry. Thus, the number of paths, and hence ideal sets is just $\frac{1}{p+q}\binom{p+q}{q}$, as desired.

The answer is $\frac{1}{p+q}\binom{p+q}{p}$ Let $A=\{ap+bq|a,b\geq 0\}$. The condition is equvialent to that if $n\in S$ then $n+A\subset S$. By Frobenius Coin problem, for every $a\geq (p-1)(q-1)$ we have $a\in A$. Therefore we may only count the number of subset of $S=\{0,1,2,...,pq-p-q\}$ which satisfies the condition. Let $B=S\setminus A$, and let $C=A\cap S$ CLAIM. $f(b)=pq-p-q-b$ is a bijection from $B$ to $C$ Proof. Firstly, we show that $|B|=|C|=\frac{(p-1)(q-1)}{2}$. Indeed, $C$ are the unions of the sets $$C_i=\{jp+iq|\quad 0\leq j<\frac{pq-p-q-iq}{p}\}$$where $0\leq i\leq p-2$. Now notice that $$|C_i|=1+\left\lfloor\frac{pq-p-q-iq}{p} \right\rfloor=\left\lfloor \frac{(p-1-i)q}{p} \right\rfloor$$hence $$|C|=\left\lfloor \frac{q}{p}\right\rfloor+\left\lfloor \frac{2q}{p} \right\rfloor+...+\left\lfloor \frac{(p-1)q}{p} \right\rfloor$$since $(p,q)=1$ we have that $q,2q,...,(p-1)q$ are congruent to $1,2,...,p-1$ mod $p$ in some order. Therefore, $$|C|=\frac{1}{p}(q(1+2+...+(p-1))-(1+2+...+(p-1)))=\frac{(p-1)(q-1)}{2}$$as desired. Now notice that if $a+b=pq-p-q$, then $a$ and $b$ can't both belong to $C$, otherwise we will have $pq-p-q\in C$ since $C$ is closed under addition. Therefore the claim follows from pigeonhole principle. $\blacksquare$ Now obviously each ideal subset must contain $C$, therefore we shall only count the number of possible subsets of $B$ which can be the union of an ideal subset and $B$, now under the bijection described in the CLAIM, the image of such subsets are subsets of $C$ such that if n belongs to it, then both $n-p$ and $n-q$ belong to it. Consider such a subset $Q$. Let $c_i$ be the largest number such that $(c_i-1)p+iq\in Q$(define $c_i=0$ if no such number exists, then the only constraints on these numbers are $$c_0\leq c_1\leq c_2\leq ...\leq c_{p-2}$$and $$c_i+1\leq \left\lfloor \frac{(i+1)q}{p} \right\rfloor$$Now this numbers corresponds bijectively to a path from $(0,0)$ to $(q,p)$ which never passes through the line $px=qy$ and only uses up and right move. The following is a famous result but we are still gonna prove it. CLAIM. The number of such paths is exactly $\frac{1}{p+q}\binom{p+q}{p}$ Proof. If we are allow to pass through the line then there will be $\binom{p+q}{q}$ paths, we divide these paths into equivalence classes, by defining two paths to be related if one of them can be shifted to another cyclically. Then each equivalence classes has $p+q$ elements, we claim that each equivalence classes have exactly one element which does not pass through the diagonal. We can consider the one-dimensional problem by representing a up and down move by a move with displacement $\frac{q}{p+q}$ and $-\frac{p}{p+q}$ respectively. Let the equivalence class contains cyclic permutation of the numbers $a_1,a_2,...,a_{p+q}$. Notice that the path never cross the diagonal if and only if $a_1+a_2+...+a_k>0$ for each $1\leq k\leq p+q-1$. Now we have $a_1+a_2+...+a_{p+q}=0$. Using exactly same reasoning as I used here, we can show that there are at least one such path, now if there are two such paths, WLOG assume $$a_1,a_2,...,a_{p+q}$$and $$a_{i+1},a_{i+2},...,i_{i+p+q}$$are two such paths, then $a_1+a_2+...+a_i>0$ and $a_{i+1}+...+a_{p+q}>0$, so $a_1+a_2+...+a_{p+q}>0$, contradiction.

The answer is $\tfrac{1}{p+q}\tbinom{p+q}{p}$. Consider the up-right lattice paths from $(0, 0)$ to $(p, q)$ above the line $y=\tfrac{q}{p}x$ where all points on the path have nonnegative $x$ and $y$-coordinates less than $p$ and $q$, respectively; we claim that there is a bijection with these paths and the ideal subsets of $\mathbb{Z}_{\ge 0}$. We construct the bijection as follows: Label each lattice point $(x, y)$ above $y=\tfrac{q}{p}x$ with nonnegative $x$ and $y$-coordinates bounded by $p$ and $q$, respectively with $qx-py$. Note that all of the labels that are not the origin are positive, and the origin has label $0$, and are precisely the set nonnegative integers that cannot be expressed as $ip+jq$ for nonnegative $i$ and $j$. Each path corresponds to a subset of $\mathbb{Z}_{\ge 0}$ by considering the labels on the path. This set corresponds to a unique ideal set by taking the complement with universal set $\mathbb{Z}_{\ge 0}$. Now given an ideal set $S$, take its complement $S'$, and assign each element of $S'$ to a unique ordered pair of nonnegative integers $(x, y)$ with $x < p$ and $y < q$ such that it is $qx-py$. One can easily see that the lattice points associated with each ordered pair can form a lattice path due to the restriction on $S$, completing the bijection. Now to enumerate these paths, we prove the following generalization due to Bizley and Grossman (independently). We follow Bizley's approach. Lemma: [Bizley, 1954] Denote by $f(bn, an)$ the number of up-right paths from $(0, 0)$ to $(bn, an)$ weakly below $y=\frac{a}{b}x$. Then \[ f(bn, an) = \langle t^n \rangle \exp \sum_{j=1}^{\infty} \frac{1}{j(a+b)} \binom{(a+b)j}{aj} t^j. \]Proof. In our proof, we let $f_j(bn, an)$ be the number of up-right paths from $(0, 0)$ to $(bn, an)$ weakly below $y=\frac{a}{b}x$ with $j$ contacts (not including the origin). We call such a path a {$\tfrac{a}{b}$-path. A highest point of a path is a point on the path that follows and precedes different steps. Additionally, we say that a cyclic shift of a path can be obtained by removing the section of the path from $(0, 0)$ to some $(r, s)$ on the path, and moving that section to the other end so that $(0, 0)$ is moved to $(bn, an)$. The key idea is that the highest points on the path are not affected by cyclic shifts, and there are exactly $j$ cyclic shifts that transform a $\tfrac{a}{b}$-path with $j$ highest points to a $\tfrac{a}{b}$-path with $j$ contacts, vice versa. Thus the number of paths with $t$ highest points is \begin{align*} \frac{1}{j}n(a+b)f_j(bn, an). \end{align*}For notational purposes, define \[ F_n(a, b) := \frac{1}{n(a+b)} \binom{(a+b)n}{an}. \]We sum equation (1) over $1 \le j \le k$ to obtain \begin{align*} F_n(a, b) = \sum_{j=1}^n \frac{1}{j} f_j(bn, an). \end{align*}Let $g_j(bn, an)$ be the number of paths from $(0, 0)$ to $(bn, an)$ with $j$ highest points. Then, \begin{align*} f_j(bn, an) = \sum g_{a_1}(bn, an) \cdot \ldots \cdot g_{a_j}(bn, an), \end{align*}where the sum is taken over all $j$-tuples $(a_1, \ldots, a_j)$ of nonnegative integers with sum $n$. Equation (3) rewrites as \begin{align*} f_j(bn, an) = \langle t^n \rangle [P(t)]^j, \end{align*}where \[ P(t) := \sum_{i=1}^{\infty} g_i(bn, an) t^n. \]Hence, \begin{align*} F_n(a, b) = \langle t^n \rangle \sum_{i=1}^n \frac{1}{i} [P(t)]^i = \langle t^n \rangle \sum_{i=1}^{\infty} \frac{1}{i} [P(t)]^i = - \langle t^n \rangle \log(1-P(t)). \end{align*}Isolating $P(t)$, we obtain \[ P(t) = 1- e^{-F_1t-F_2t^2-\ldots}. \]Now $f_j(bn, an)=\langle t^j \rangle (1- e^{-F_1t-F_2t^2-\ldots})^j$, so \[ f(bn, an) = \sum_{j=1}^n \langle t^n \rangle (1- e^{-F_1t-F_2t^2-\ldots})^j= \langle t^n \rangle e^{F_1t+F_2t^2+\ldots}, \]which proves the desired result. Thus, taking $n=1$ in the lemma, we do some basic differentiation to find that the number of paths we want to count is indeed $\tfrac{1}{p+q}\tbinom{p+q}{p}$, and we conclude.

Fun ENUMERATIVE COMBINATORICS problem. The lattice point labeling is motivated by the fact that p and q can be thought of as weights for x and y coordinates, and by experience it's actually pretty common for these types of problems that have ``two degrees of freedom'' to have a bijection with a 2D graph (i can think of 2 bijection examples off the top of my head but don't quite know the contest names, one was a jmo problem the other an isl as well). $\newline$ The answer is $\boxed{\frac{1}{p+q}\binom{p+q}{p}}$. $\textit{Label}$ the lattice points $(x,y)$ that satisfy $0\le x\le p$ and $y\ge 0$ with the number $py-qx$. Note that Every nonnegative integer label is achieved at some point; this follows by $py-qx=n$ and $(x,y)\to(x+kp,y+kq)$, so there's $x\in[0,p],y\ge0$ by shifting. Let $S_{p,q}$ be the lattice points that have label in $S$. It suffices to determine the number of subsets of the lattice points in $x\in[0,p],y\in[0,q]:py-qx\ge 0$ since \[0\in S\implies(0,0),(p,q)\in S_{p,q}\text{ and }(x,y)\in S_{p,q}\implies(x-a,y+b)\in S\forall a,b\in\mathbb N_0.\] We'll (biject again!) take the obvious interpretation $w_1,\ldots,w_{p+q}\in\{p,-q\}$, where $w_i=p$ corresponds to y increases by 1 and $w_i=-q$ corresponds to x increases by 1. We'll count the number of such sequences that satisfy $w_1+...+w_{p+q}=0$ and $\sigma_{n}:=w_1+...+w_n\ge 0\forall n\in[0,p+q-1]$. (Assume henceforth though that we don't take for granted that $\sigma_n\ge0$.) Now take $m:\sigma_{m}=\min_{i\in[1,p+q-1]}\sigma_i$ (and take $m\ne0,p+q$ if there is another value). Note that since $\gcd(p,q)=1,\sigma_{m}\ne0$, m=0 is the only value in order to stay not below the line. Consider the sequence $(w_{m+1},...,w_{p+q},w_1,...,w_m)$. All the partial sums \[ s_i= \begin{cases} \sum_{i=1}^{p+q-m}w_{m+i}+\sum_{i=1}^{m+i+1\mod{p+q}}w_{i}=\sigma_{p+q}-\sigma_m+\sigma_{m+i+1\mod{p+q}}\ge0 & \text{if } m+i+1>p+q \\ w_{m+1}+...+w_{m+i+1}=\sigma_{m+i+1}-\sigma_m\ge0 & \text{if } m+i+1\le p+q. \end{cases} \]This sequence is valid, and any cyclic shift by assumption that $\sigma_m$ is minimal means in \[(w_{m+i},...,w_{p+q},w_1,...,w_m,w_{m+1},...,w_{m+i-1}),\text{ we have }w_{m+1}+...+w_{m+i-1}>0\]\[\implies\sum_{j=i}^{p+q-m}w_{m+j}+\sum_{i=1}^{m}w_{i}=\sum_{i=1}^{p+q}w_i-(w_{m+1}+...+w_{m+i-1})<0,\]contradiction (this partial sum is negative). Hence exactly one in every p+q cyclic shifts of sequences are valid (i.e. stay above the y=qx/p line), so there are $\boxed{\frac{1}{p+q}\binom{p+q}{p}}$ ways, as claimed.

Let $U$ be the set of nonnegative integers less than or equal to $pq-p-q$ that are representable as $ap+bq$ for some nonnegative integers $a$ and $b$. Let $V$ be $\{0,1,\dots,pq-p-q\}\setminus U$ be the set of nonnegative integers less than or equal to $pq-p-q$ that are not representable as $ap+bq$ for some nonnegative integers $a$ and $b$. According to the Chicken McNugget theorem, if $x$ is in $V$ then $pq-p-q-x$ is in $U$. This means that if $x\in V$ then it can be represented as $pq-p-q-ap-bq$ for some nonnegative integers $a$, $b$. Furthermore, any number greater than $pq-p-q$ must be representable, so if $x\not\in V$ then $x\in S$. $~$ Now, we write out the elements of $V$ in a grid in the following way: write $pq-p-q$ on the bottom left corner. For any $x$ on the grid, if $x>p$ then write $x-p$ above it, and if $x>q$ then write $x-q$ to the right of it. Here is an example for $p=5,q=7$. [asy][asy] for (int i = 0; i < 4; ++i) { for (int j = 0; j < 5; ++j) { draw(box((i,j),(i+1,j+1))); } } label("23",(0.5,0.5)); label("18",(0.5,1.5)); label("13",(0.5,2.5)); label("8",(0.5,3.5)); label("3",(0.5,4.5)); label("16",(1.5,0.5)); label("11",(1.5,1.5)); label("6",(1.5,2.5)); label("1",(1.5,3.5)); label("9",(2.5,0.5)); label("4",(2.5,1.5)); label("2",(3.5,0.5)); [/asy][/asy] Color a cell blue if the number is in $S$. Note that if a cell is blue then all cells below it or to the left of it must also be blue, and that all such sets of cells satisfies the ideal condition. Therefore, there is a bijection between ideal sets and paths from the top left to the bottom right that stays on edges of cells that have numbers in them. [asy][asy] draw((5,0)--(0,7)); draw((5,0)--(4,0)--(4,1)--(3,1)--(3,2)--(2,2)--(2,4)--(1,4)--(1,5)--(0,5)--(0,7),blue+linewidth(2)); for (int i = 0; i < 5; ++i) { for (int j = 0; j < 7; ++j) { draw(box((i,j),(i+1,j+1))); } } label("23",(0.5,0.5)); label("18",(0.5,1.5)); label("13",(0.5,2.5)); label("8",(0.5,3.5)); label("3",(0.5,4.5)); label("16",(1.5,0.5)); label("11",(1.5,1.5)); label("6",(1.5,2.5)); label("1",(1.5,3.5)); label("9",(2.5,0.5)); label("4",(2.5,1.5)); label("2",(3.5,0.5)); [/asy][/asy] It is easy to see why the current grid is smaller than $p\times q$ on both dimensions. Extend the grid upward and rightward to a $p$ by $q$ grid and draw the main diagonal, as shown. Now, we show that a path stays on edges of cells with numbers in them if and only if the path stays under the main diagonal. This is obvious: assign each coordinate $(x,y)$ with $x$ and $y$ integers the value $pq-qx-py$. This is the same as the number that is in the cell directly below and to the left of it and it is necessary and sufficient for this number to be positive for every point on the path so $pq-qx-py>0$ which implies lower than main diagonal. It is well known then that the answer is $\tfrac{1}{p+q}\tbinom{p+q}{p}$