MathDB
3 x 9 matrix with conditions on the first three columns

Source: China Second Round Olympiad 2009

February 18, 2012
linear algebramatrixcombinatorics proposedcombinatorics

Problem Statement

Let P=[aij]3×9P=[a_{ij}]_{3\times 9} be a 3×93\times 9 matrix where aij≥0a_{ij}\ge 0 for all i,ji,j. The following conditions are given: [*]Every row consists of distinct numbers; [*]∑i=13xij=1\sum_{i=1}^{3}x_{ij}=1 for 1≤j≤61\le j\le 6; [*]x17=x28=x39=0x_{17}=x_{28}=x_{39}=0; [*]xij>1x_{ij}>1 for all 1≤i≤31\le i\le 3 and 7≤j≤97\le j\le 9 such that j−i≠6j-i\not= 6. [*]The first three columns of PP satisfy the following property (R)(R): for an arbitrary column [x1k,x2k,x3k]T[x_{1k},x_{2k},x_{3k}]^T, 1≤k≤91\le k\le 9, there exists an i∈{1,2,3}i\in\{1,2,3\} such that xik≤ui=min⁡(xi1,xi2,xi3)x_{ik}\le u_i=\min (x_{i1},x_{i2},x_{i3}). Prove that: a) the elements u1,u2,u3u_1,u_2,u_3 come from three different columns; b) if a column [x1l,x2l,x3l]T[x_{1l},x_{2l},x_{3l}]^T of PP, where l≥4l\ge 4, satisfies the condition that after replacing the third column of PP by it, the first three columns of the newly obtained matrix P′P' still have property (R)(R), then this column uniquely exists.
Back to ProblemsView on AoPS