MathDB

4

Part of 2009 China Second Round Olympiad

Problems(1)

3 x 9 matrix with conditions on the first three columns

Source: China Second Round Olympiad 2009

2/18/2012
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.
linear algebramatrixcombinatorics proposedcombinatorics