[转]100囚犯之黑白手套

the47

用逆序对做
LZ多出新题啊~~~~~~~

yylxxch

这题可以用归纳法来做，题目的要求可视为最后100人可以按大小顺序排成一列。那么可以先排3个人，再一个个往里面加。事先规定站位从左到右依次变大。
一、3人的排序
规则如下：后一人观察前一人与再前一人的站位，若顺序正确则站在前一人右侧，若不对则站在前一人左侧。
1.a、b站好后c通过观察、站位，给出ab的大小关系。
2.a出列观察、站位，给出bc大小关系。
3.b出列观察、站位，给出ac大小关系。
此时信息量已足，排位即可。

二、在n人的队伍中加入一人
规则如下：若在已排好的n人（A1＜······＜An）中加入一人（该人应站在p位置，1 ≤ p ≤ n+1），可先令其站在最右端。观察前一人与p的站位（若p就是前一人则再顺推前一位），若顺序正确则站在前一人右侧，若不对则站在前一人左侧。
1.若p=1，A1出列观察p与An后，应站在p左侧，给出信息p＜An；A2出列观察A1与p后，应站在A1左侧，给出信息p＜A1。 此时信息已够p＜A1＜······＜An。
2.若p=n+1，A1出列观察p与An后，应站在p右侧，给出信息An＜p。此时信息已够A1＜······＜An＜p。
3.若1＜p＜n+1，则A1出列观察p与An后，站在p左侧，给出信息p＜An；A2出列观察A1与p后，应站在A1右侧，给出信息A1＜p；A3出列观察A2与p后，应站在A2右侧，给出信息A2＜p...到A（p+2）后站位为：A（p+2）···An、A1、A2···A（p-1）、A（p+1）、p
A（p+2）出列观察A（p+1）与p后，站在A（p+1）左侧，给出信息p＜A（p+1）。此时信息已够A1＜···＜A（p-1）＜p＜A（p+1）＜···＜An。

此方法并非最佳，额外开销颇大，期待可以直接从100人确定站位的方法。

cola_kitty

楼上这样这算信息交流吗？
如果这样算，那我想不出什么解答了；
如果这样不算，那大家一个一个排呗，找一个人做监督，对了左站，错了右站，其他所有人都排好以后这个人再找一个监督把自己排进去就行了

yylxxch

这个算信息交流的话，那就想不到什么获得信息的方法了==毕竟需要根据其他人的行动获得信息，完全自己推断...
期待逆序对的解释~

the47

回复 b.p.bravo 的帖子

没有没有，转帖很好，大家分享嘛~~~~


解法：（反白）大家多想想吧，这样的好题不多的说~~~~

假设囚犯都面向一个方向，令“左白右黑”为W1；“左黑右白”为W2；那么，只要W1，W2交替出现，就能成功；
  1游戏开始前，囚犯进行编号1，2，3......n;（每个人都知道自己的“编号”）
  2游戏开始后，根据实数大小而排队后，原来的顺序被打乱，如2，5，8，3，6，4........
  3逆序对为位于前面的某个数比位于后面的某个数更大的2个数，如上，有（5，3），（5，4），（8，3），（8，6），（8，4），（6，4）6个逆序对；
  4每个囚犯算出队伍中逆序对的个数（不包括自己），若与自己的编号同奇偶，则用W1；反之，用W2（在游戏开始前定好）。

dance with you

逆序对什么的好神奇……=