MathDB
CSMO Grade 10 Problem 8

Source: CSMO Grade 10 Problem 8

August 6, 2017
combinatorics

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,y1,y2,y3x_1, x_2, y_1, y_2, y_3 such that x1<x2,y1<y2<y3x_1 < x_2, y_1 < y_2 < y_3 and (x1,y1),(x1,y2),(x1,y3),(x2,y2)∈A.(x_1, y_1), (x_1, y_2), (x_1, y_3), (x_2, y_2) \in A.Determine the largest possible number of elements in AA.
Back to ProblemsView on AoPS