Saturday, November
9, 2002 |
|
Aristotle selected
IN an n by n table, paint the smallest number in each row red and the smallest number in each column blue. The smallest number in the table is painted in both colours. We do not have any painted number in the row or column the smallest number belongs to. Delete this row and this column and get a table of the size n-1 by n-1. Repeat the process, i.e., find the smallest number in the new table; it is painted both red and blue; and delete the row and the column it belongs to. Iterating this process, we find all painted numbers and show that all such numbers are painted in both red and blue, i.e., both times, the same numbers were marked. "In a table of n
by n, there will be n x n number of squares that are filled with
different numbers. The smallest number of each row turns out to be in a
different column and the smallest number of each column turns out to be
in different row. This is possible if the first n numbers (if n by n
numbers are arranged in increasing order) are in the squares lying on
any of the two long diagonals of the table: first number in column1,
row1 square, next on C2.R2
..and nth on Cn Rn square, or the first
number is in Cn R1 square and nth in C1 Rn square. In a square, no two
points lying on the diagonal have same x or y," says Dr Tarsem Lal
of Khanna. |
1 2 3 4 5 6 7 8 9 This is a 10 by 10 matrix. There are 10 rows and 10 columns, such that, marking the lowest number in each column is equal to the lowest number in that row." "The trick is in having all the smallest numbers on the diagonal. Consider the n*n table a matrix of the order n*n (n rows and n columns). A11 A12 A13 A1j A1n Let this matrix be represented by A. While assigning value to the elements of the matrix, the smallest n numbers out of it should be placed for the elements having value I=j (A11, a22 Ann). Whatever be the other elements, it makes no difference. According to the first condition, the smallest number in each row is in different column which are elements having value I=j. Similarly, the smallest numbers in each column are in different row, which are again elements having value I=j; and, both times, the same numbers are picked, which satisfies the third condition," says Sudhanshu Arya of Naya Nangal in Punjab. Aristotle cleared the test without having to move in diagonals. Write at The Tribune or adityarishi99@yahoo.co.in |