
你能够推理出来吗?
题目:设有mn个实数排成一个m行n列的阵列,使得每一行上的n个数从左到右都按递增的顺序排列。下面,把每列上的m个数从上到下都按递增的顺序重排得到阵列,问这个新的阵列每一行中的n个数的大小顺序如何?给出结论并说明理由。
记者按:
宋春伟教授提供了答案,但是说实话,记者很努力地看了好几遍,连题都没读懂,答案也没读懂……我只感觉答案里的--(需要思考!),听起来比"显然可得"好受一些。
答案:
重新排好的阵列与原阵列一样,每一行上的n个数从左到右递增。为证明此事,我们仅需要在新的阵列中任选两列,证明在每一行上,左边那列的数比右边那列的数小。现在新阵列中任取两列,设左边那列第k行的数为x,右边那列第k行的数为y。注意到y在右边那列是第k小的(新阵列每列上的数从上到下递增),而原阵列每一行上的数从左到右按递增,故根据传递性在左边那列上应该至少存在k个比y小的数(需要思考!)。而x在左边那列是第k小的数,故比y小。










