MathDB
Mapping and Number of element of set

Source: 1992 Japan Mathematical Olympiad Finals, Problem 4

November 2, 2009
linear algebracombinatorics

Problem Statement

Let A A be a m×n (m≠n) m\times n\ (m\neq n) matrix with the entries 0 0 and 1 1. Suppose that if f f is injective such that f:{1, 2, ⋯ , m}⟶{1, 2, ⋯ , n} f: \{1,\ 2,\ \cdots ,\ m\}\longrightarrow \{1,\ 2,\ \cdots ,\ n\}, then there exists 1≤i≤m 1\leq i\leq m such that (i, f(i)) (i,\ f(i)) element is 0 0. Prove that there exist S⊆{1, 2, ⋯ , m} S\subseteq \{1,\ 2,\ \cdots ,\ m\} and T⊆{1, 2, ⋯ , n} T\subseteq \{1,\ 2,\ \cdots ,\ n\} satisfying the condition: i) i) if i∈S, j∈T i\in{S},\ j\in{T}, then (i, j) (i,\ j) entry is 0 0. ii) ii) card\ S \plus{} card\ T > n.
Back to ProblemsView on AoPS