MathDB

East German subsets

Source: IMO LongList 1988, East Germany 2, Problem 19 of ILL

October 22, 2005

combinatorics unsolvedcombinatorics

Problem Statement

Let

Z_{m,n}

be the set of all ordered pairs

(i,j)

with

i \in {1, \ldots, m}

and

j \in {1, \ldots, n}.

Also let

a_{m,n}

be the number of all those subsets of

Z_{m,n}

that contain no 2 ordered pairs

(i_1,j_1)

and

(i_2,j_2)

with

|i_1 - i_2| + |j_1 - j_2| = 1.

Then show, for all positive integers

m

and

k,

that

a^2_{m, 2 \cdot k} \leq a_{m, 2 \cdot k - 1} \cdot a_{m, 2 \cdot k + 1}.

Back to Problems View on AoPS