八达网

标题: 请教个问题，10*10队列的问题，有人会吗？回复一个 [打印本页]

作者: 养猪的西瓜 时间: 2008-12-16 19:42
标题: 请教个问题，10*10队列的问题，有人会吗？回复一个
100个人站称一个10*10的队列
从每行中选出最高的组成一个组，然后选择最矮的，为甲
从每列中选出最矮的组成一个组，然后选择最高的，为乙

问甲乙谁高？

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

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

作者: tvspz 时间: 2008-12-16 19:44

作者: 养猪的西瓜 时间: 2008-12-16 20:28
我日，没一个会的？是不是标题要耸动才可以得到回复？

作者: 碎镜 时间: 2008-12-16 20:45
填空题还是大题这区别很大
填空题可以特殊值做一下就出来了
大题的话要给出严密的证明我还没想出来

作者: Springsun 时间: 2008-12-16 20:49
哦，题目没看清，编辑下。
甲>=乙，推理待续。

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

作者: 碎镜 时间: 2008-12-16 20:55
甲>=乙
马上给出证明过程

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

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

作者: 碎镜 时间: 2008-12-16 22: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)

欢迎光临八达网 (https://www.8-da.com/)