This last result can be used to play card tricks, such as “teaching the cards to order
themselves” (see The Last Recreations, by Martin Gardner, for an explanation and some
further references). Quite simply, arrange nm numbers (distinct or not) in a rectangular
array of m rows by n columns. Rearrange every row independently, one by one, so that the numbers in each row are in non-decreasing order, from left to right. For example, take the rows “1 6 2 6 9” and “13 12 2 2 1”, which when rearranged become “1 2 6 6 9” and “1 2 2 12 13”. When done, rearrange the columns similarily, one by one, so that the numbers are in non-decreasing order, from front to back. Then look at the rows again :even though permuting the numbers in each column has altered the arrangements in the rows, the numbers in the rows are still in non-decreasing order from front to back. Proof:assume not, then there is a smaller number a placed to the right, and maybe to the back also, of a larger number b after rearranging the columns of array A. But the columns have all been ordered, so all numbers to the back of b, in the same column, are no smaller than b, and bigger than a (since b>a), and all of those in front of a, in the same column, are no bigger than a, so smaller than b. Consider now the moment just before the columns where rearranged, after the rows had been ordered. We want to show that there is no prior arrangement of numbers into an n by m array, such that the numbers in each row of this array have been sorted in non-decreasing order, that can lead to having at least one row that is not ordered anymore after rearranging the columns. So we want to “return” all numbers in A to their position prior to rearranging the columns. We will start by replacing all numbers behind b in b's column, including b, and all numbers in front of a in a's column, including a. Since b is to the left, and possibly in front of, a then we have at least m+1 numbers to replace in m rows. But for two numbers to be replaced in the same row, they must be in different columns, so that a number greater than or equal to b will be in the same row, to the left, of a number smaller than or equal to a, with a<b. This is a contradiction, since we are returning to the moment before rearranging the columns, that is, after rearranging the rows. So no n by m array of numbers can lead to disordered rows.when the numbers in the rows, and then in the columns, have been ordered in nondecreasing fashion.