6. C6 (FRA) Let $p$ and $q$ be relatively prime positive integers. A subset $S$ of $\{0,1,2, \ldots\}$ is called ideal if $0 \in S$ and for each element $n \in S$, the integers $n+p$ and $n+q$ belong to $S$. Determine the number of ideal subsets of $\{0,1,2, \ldots\}$.
6. Every integer $z$ has a unique representation $z=p x+q y$, where $x, y \in \mathbb{Z}$, $0 \leq x \leq q-1$. Consider the region $T$ in the $x y$-plane defined by the last inequality and $p x+q y \geq 0$. There is a bijective correspondence between lattice points of this region and nonnegative integers given by $(x, y) \mapsto$ $z=p x+q y$. Let us mark all lattice points of $T$ whose corresponding integers belong to $S$ and color in black the unit squares whose left-bottom vertices are at marked points. Due to the condition for $S$, this coloring has the property that all points lying on the right or above a colored point are colored as well. In particular, since the point $(0,0)$ is colored, all points above or on the line $y=0$ are colored. What we need is the number of such colorings of $T$. The border of the colored subregion $C$ of $T$ determines a path from $(0,0)$ to $(q,-p)$ consisting of consecutive unit moves either to the right or downwards. There are $\binom{p+q}{p}$ such paths in total. We must find the number of such paths not going below the line $l: p x+q y=0$. Consider any path $\gamma=A_{0} A_{1} \ldots A_{p+q}$ from $A_{0}=(0,0)$ to $A_{p+q}=(q,-p)$. We shall see the path $\gamma$ as a sequence $G_{1} G_{2} \ldots G_{p+q}$ of moves to the right $(R)$ or downwards ( $D$ ) with exactly $p D$ 's and $q R$ 's. Two paths are said to be equivalent if one is obtained from the other by a circular shift of the corresponding sequence $G_{1} G_{2} \ldots G_{p+q}$. We note that all the $p+q$ circular shifts of a path are distinct. Indeed, $G_{1} \ldots G_{p+q} \equiv$ $G_{i+1} \ldots G_{i+p+q}$ would imply $G_{1}=G_{i+1}=G_{2 i+1}=\cdots$ (where $G_{j+p+q}=$ $G_{j}$ ), so $G_{1}=\cdots=G_{p+q}$, which is impossible. Hence each equivalence class contains exactly $p+q$ paths. Let $l_{i}, 0 \leq i<p+q$, be the line through $A_{i}$ that is parallel to the line $l$. Since $\operatorname{gcd}(p, q)=1$, all these lines are distinct. Let $l_{m}$ be the unique lowest line among the $l_{i}$ 's. Then the path $G_{m+1} G_{m+2} \ldots G_{m+p+q}$ is above the line $l$. Every other cyclic shift gives rise to a path having at least one vertex below the line $l$. Thus each equivalence class contains exactly one path above the line $l$, so the number of such paths is equal to $\frac{1}{p+q}\binom{p+q}{p}$. Therefore the answer is $\frac{1}{p+q}\binom{p+q}{p}$.