MathDB
CSMO Grade 11 Problem 8

Source: China Southeast Mathematical Olympiad

August 1, 2017
setcombinatorics

Problem Statement

Given the positive integer m≥2m \geq 2, n≥3n \geq 3. Define the following set S={(a,b)∣a∈{1,2,⋯ ,m},b∈{1,2,⋯ ,n}}.S = \left\{(a, b) | a \in \{1, 2, \cdots, m\}, b \in \{1, 2, \cdots, n\} \right\}. Let AA be a subset of SS. If there does not exist positive integers x1,x2,x3,y1,y2,y3x_1, x_2, x_3, y_1, y_2, y_3 such that x1<x2<x3,y1<y2<y3x_1 < x_2 < x_3, y_1 < y_2 < y_3 and (x1,y2),(x2,y1),(x2,y2),(x2,y3),(x3,y2)∈A.(x_1, y_2), (x_2, y_1), (x_2, y_2), (x_2, y_3), (x_3, y_2) \in A. Determine the largest possible number of elements in AA.
Back to ProblemsView on AoPS