IMO 1988 LL GDR24

Let Zm,n be the set of all ordered pairs (i, j) with i \in

imolonglistmathematicsolympiad

IMO 1988 LL GDR24

Origin: GDR

Problem

Let Zm,n be the set of all ordered pairs (i, j) with i \in {1, . . . , m} and j \in{1, . . ., n}. Also let am,n be the number of all those subsets of Zm,n that contain no two ordered pairs (i1, j1), (i2, j2) with |i1 −i2| + |j1 −j2| = 1. Show that for all positive integers m and k, a2 m,2k \leqam,2k−1am,2k+1.