请教个问题，10*10队列的问题，有人会吗？回复一个

养猪的西瓜

100个人站称一个10*10的队列
从每行中选出最高的组成一个组，然后选择最矮的，为甲
从每列中选出最矮的组成一个组，然后选择最高的，为乙

问甲乙谁高？

麻烦给出计算或者推理步骤

[ 本帖最后由 养猪的西瓜 于 2008-12-16 20:30 编辑 ]

tvspz

养猪的西瓜

我日，没一个会的？是不是标题要耸动才可以得到回复？

碎镜

填空题还是大题 这区别很大
填空题 可以特殊值做 一下就出来了
大题的话 要给出严密的证明 我还没想出来

Springsun

哦，题目没看清，编辑下。
甲>=乙，推理待续。

[ 本帖最后由 Springsun 于 2008-12-16 20:51 编辑 ]

碎镜

甲>=乙
马上给出证明过程

Springsun

假如甲的坐标是（x,y），乙的坐标是（a，b）。那么由条件“从每行中选出最高的组成一个组，然后选择最矮的，为甲”得，甲>坐标(a，y），由条件“从每列中选出最矮的组成一个组，然后选择最高的，为乙”得，坐标（a，y）>乙。所以甲>坐标(a，y）>乙。只有刚好当x=a，且y=b时，行列选出的人是同一个人时一样高。

[ 本帖最后由 Springsun 于 2008-12-16 21:05 编辑 ]

碎镜

10*10的矩阵
设每一个元素为E(x,y)  x,y<=10且x,y∈N*
以题设的取值后
设甲=E(x1,y1)  乙=E(x2,y2)
因为甲出自每行中的最大值 则E(x1,y1)=Max[E(x1,yn)]
因为乙出自每列中的最小值 则E(x2,y2)=Min[E(xn,y2)]
问题化为对比Max[E(x1,yn)]和Min[E(xn,y2)]之间的大小关系.

根据筛选规则,Min[E(xn,y2)]必然小于或等于E(x1,yn)
又因为甲=E(x1,y1)=Max[(x1,yn)]
所以E(x2,y2)=Min[E(xn,y2)]<=E(x1,yn)<=Max[E(x1,yn)]=E(x1,y1)

得证E(x2,y2)<=E(x1,y1)