I was working my way through some puzzles in Discrete Maths by Rosen, when I came across the following question:
Freedonia has fifty senators. Each senator is either honest or corrupt.
Suppose you knowthat at least one of the Freedonian senators is honest and that, given any two Freedonian senators, at least one is corrupt.
Based on these facts, can you determine how many Freedonian senators are honest and how many are corrupt? If so, what is the answer?
My solution:
- Let the senators be numbered from 1 to 50 ( in order ) say S1 , S2 ,... , S50
- Now taking pairwise senators on at a time : (S1,S2) ; (S2,S3) ; ... ; (S49,S50)
- Without Loss of Generality assume that the Liar Senator is the first one in each pair $\Rightarrow$ S1,S2,..,S49
- Now , the only Senator left is S50 , who is Honest and also satisfies the constraints of the question
- Hence , there are 49 corrupt senators and 1 honest senator
My question:
Am I right ?
Answer
A simpler proof:
Assume there's more than one honest senator, and pick two. Among those two, neither is corrupt. Contradiction.
Having chosen the pairs (S1,S2), (S2,S3), etc., you can't make a sweeping WLOG assumption about all of them together, since they depend on each other (e.g. the second pair is related to the first via S2). Also in your answer you've only used the fact that in any consecutive pair of senators, at least one is corrupt. This isn't enough, since S1, S3, S5, ... could be corrupt and S2, S4, S6, ... honest.
In short: your answer is right, but your argument is wrong.
No comments:
Post a Comment