0
$\begingroup$

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 ?

$\endgroup$
  • 2
    $\begingroup$ Voted to close because it belongs on math.stackexchange.com instead, as it's about checking an exercise from a math book. $\endgroup$ – xnor Dec 31 '14 at 15:40
  • $\begingroup$ Hi @xnor -- I will post it on math.SE , but is it not a puzzle . Does the book it is from really matter ? $\endgroup$ – pranav Dec 31 '14 at 16:08
  • $\begingroup$ I guess you could have puzzle from a book like this, but this problem is just about applying the basics that a student learned for the book. It isn't perplexing and there little creativity in solving it. $\endgroup$ – xnor Dec 31 '14 at 16:24
  • $\begingroup$ Well actually the book does not give any exposition to puzzle solving in the text . But , I completely get your point @xnor , and I hope that you will not close this question and let it be here :) $\endgroup$ – pranav Jan 1 '15 at 4:29
  • 2
    $\begingroup$ @xnor We don't have a policy to exclude math questions. $\endgroup$ – Gilles Jan 1 '15 at 14:12
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi @randal'thor , thanks for the clarification :) . Why is my WLOG assumption not actually WLOG ? Can you provide some pointers ... $\endgroup$ – pranav Dec 31 '14 at 16:09
  • 3
    $\begingroup$ @pranav A better question is why do you think it is WLOG? You need to prove WLOGness to be able to use it. To see why it's not WLOG, note that you've only used the fact that at least one of each consecutive pair is corrupt, which isn't enough (e.g. all the even ones could be honest and all the odd ones corrupt). A more general principle: if there's too much interdependence, you can't assume WLOG. See my edited answer. $\endgroup$ – Rand al'Thor Dec 31 '14 at 16:18
  • $\begingroup$ @pranav if one of each pair A,B and B,C is corrupt it could be only one, B, is corrupt. If "wlog" the first of each pair is corrupt, then two of them must be corrupt. $\endgroup$ – Florian F Feb 2 '15 at 9:40
4
$\begingroup$

The clue to the question is

given any two Freedonian senators, at least one is corrupt.

So there are no two senators where both of them are honest. So either there is one senerator who is honest or none.

As we already know at least one of the Freedonian senators is honest

So we can safely conclude there is one and only one honest senator

$\endgroup$
  • 1
    $\begingroup$ This is the same as the first part of my answer, but an hour later. $\endgroup$ – Rand al'Thor Dec 31 '14 at 16:55
1
$\begingroup$

Here is a different approach that uses basic combinatorics:

  • Denote with $h$ the number of honest senators.
  • We already know that $h \ge$ 1 from the problem
  • The number of pairs of honest senators is given by the 2-combinations of $h$: there are $\binom h2$ of them.
  • As the problem says, this must be zero, hence $\binom h2 = 0 \implies 2 > h \implies h \le 1$.
  • Combine with the previous result to get $h$ = 1.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.