诚实教授的问题
100 professors total, some honest and some not.
honest will always say the truth.
not hosest will sometimes lie.
and honest people is more than not-honest ones.
You can ask any professor the following question about any other people: "Professor Y , is Professor X honest?" Professor Y will answer with either "yes" or "no." Design an algorithmthat, with no more than 198 questions, would allow you to figure out which of the 100 professors are honest.
honest will always say the truth.
not hosest will sometimes lie.
and honest people is more than not-honest ones.
You can ask any professor the following question about any other people: "Professor Y , is Professor X honest?" Professor Y will answer with either "yes" or "no." Design an algorithmthat, with no more than 198 questions, would allow you to figure out which of the 100 professors are honest.
回复列表
我们先假设professor1是honest 的,提问"Professor 2 , is Professor 1 honest?"可以判断Professor 2是honest或not-honest ,依次类推,可以推出99个Professors的honest或not-honest ,然后数数honest多还是not-honest 多,根据honest people is more than not-honest ones判断假设成不成立,成立就ok了,不成立就是每个人都相反,也就ok了,一共提问了99个问题
看看这样分析对不对啊?
看看这样分析对不对啊?
楼上的不对。
提出99个问题后，你可以把所有不诚实的教授找出来。根据honest people is more than not-honest ones，99个回答yes或no的教授中的少数派一定是不诚实的教授，只有他们才可能说谎。但多数派并不都是诚实的教授，因为not hosest will sometimes lie，而不是一定说谎，不诚实的教授也可能说了真话，有一部分撒谎者混进了多数派。
最糟糕的情况是这样，被提问的99个教授中的不诚实者全部说了真话，虽然这种概率很小，但不能排除。此时，仅仅确认了第一个教授是不是诚实者。如果第一个教授是诚实者，那也好办，依次问他剩余99个教授是不是诚实的，这样总共99*2=198个问题就搞定了。如果第一个教授是说谎者，能不能在198个问题内确定所有人身份就难说了。所以最好换一种方法。
提出99个问题后，你可以把所有不诚实的教授找出来。根据honest people is more than not-honest ones，99个回答yes或no的教授中的少数派一定是不诚实的教授，只有他们才可能说谎。但多数派并不都是诚实的教授，因为not hosest will sometimes lie，而不是一定说谎，不诚实的教授也可能说了真话，有一部分撒谎者混进了多数派。
最糟糕的情况是这样，被提问的99个教授中的不诚实者全部说了真话，虽然这种概率很小，但不能排除。此时，仅仅确认了第一个教授是不是诚实者。如果第一个教授是诚实者，那也好办，依次问他剩余99个教授是不是诚实的，这样总共99*2=198个问题就搞定了。如果第一个教授是说谎者，能不能在198个问题内确定所有人身份就难说了。所以最好换一种方法。
