IMO 2000 SL C6

Origin: FRA | Category: Combinatorics

Problem

Let p and q be relatively prime positive integers. A subset S of {0, 1, 2, . . .} is called ideal if 0 \inS and for each element n \inS, the integers n + p and n + q belong to S. Determine the number of ideal subsets of {0, 1, 2 . . .}.

Solution

Every integer z has a unique representation z = px + qy, where x, y \inZ, 0 \leqx \leqq −1. Consider the region T in the xy-plane defined by the last inequality and px + qy \geq0. There is a bijective correspondence between lattice points of this region and nonnegative integers given by (x, y) "\to z = px + qy. 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 down- wards. There are
p+q p  such paths in total. We must find the number of such paths not going below the line l : px + qy = 0. Consider any path \gamma = A0A1 . . . Ap+q from A0 = (0, 0) to Ap+q = (q, −p). We shall see the path \gamma as a sequence G1G2 . . . Gp+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 G1G2 . . . Gp+q. We note that all the p + q circular shifts of a path are distinct. Indeed, G1 . . . Gp+q \equiv Gi+1 . . . Gi+p+q would imply G1 = Gi+1 = G2i+1 = \cdot \cdot \cdot (where Gj+p+q = Gj), so G1 = \cdot \cdot \cdot = Gp+q, which is impossible. Hence each equivalence class contains exactly p + q paths. Let li, 0 \leqi < p + q, be the line through Ai that is parallel to the line l. Since gcd(p, q) = 1, all these lines are distinct. Let lm be the unique lowest line among the li’s. Then the path Gm+1Gm+2 . . . Gm+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 equiv-

alence class contains exactly one path above the line l, so the number of such paths is equal to p+q
p+q p  . Therefore the answer is p+q
p+q p  .