10
$\begingroup$

Five competitors (A, B, C, D and E) are arguing about a swimming test that rewards the 1st, 2nd and 3rd places with gold, silver and bronze medals, respectively. The following assertions about the test are false, though one assertion from each (note each has two assertions) may be true.

• A did not get gold and B did not get silver;
• D did not get silver and B did not get bronze;
• C won a medal, but D didn't;
• A won a medal, but C didn't;
• D won a medal and E did, too.

Note: the answer is only about the first three places since the last two can't be said for sure.

$\endgroup$
12
$\begingroup$

(3) and (4) together say that if A won a medal, C did, and if C won a medal, D did. (5) says that if E won a medal, D didn't - and therefore neither did A or C. This results in only two medallists at most, so E did not win a medal. Now there's only one non-medallist in A,B,C,D, which must be either A or B.

Now suppose D didn't get silver. Then B got bronze (2) and A got gold (1), but this contradicts the deduction that one of A and B failed to win a medal.

Therefore D got silver. (1) then says A got gold, and so C must be bronze. B and E failed to win medals.

$\endgroup$
6
$\begingroup$

A slightly more formal solution

This happens to be a Boolean satisfiability problem where we want a model for the variables: $A,B,C,D,E$ where they take values disjointly from $\{gold,silver,bronze,nothing1,nothing2\}$.

The formulae that act as constraints on the system are:

  • $f1 = (A \not= gold \land B \not=silver)$
  • $f2 = (D \not= silver \land B \not= bronze)$
  • $f3 = (C \in \{gold,silver,bronze\} \land D \not\in \{gold,silver,bronze\})$
  • $f4 = (A \in \{gold,silver,bronze\} \land C \not\in \{gold,silver,bronze\})$
  • $f5 = (D \in \{gold,silver,bronze\} \land E \not\in \{gold,silver,bronze\})$
  • $fz = (\lnot (f1 \lor f2 \lor f3 \lor f4 \lor f5))$

There is a satisfying model where:

  • $A = gold$
  • $D = silver$
  • $C = bronze$
  • $B = nothing1$
  • $E = nothing2$

You can easily encode this in SMT-LIB2 and execute here using this code:

(declare-datatypes()((M g s b n1 n2)))
(declare-const A M)
(declare-const B M)
(declare-const C M)
(declare-const D M)
(declare-const E M)
(assert(distinct A B C D E))
;A did not get gold and B did not get silver
(define-fun f1 () Bool (and (not (= A g)) (not (= B s))))
;D did not get silver and B did not get bronze
(define-fun f2 () Bool (and (not (= D s))(not (= B b))))
;C won a medal, but D didn't
(define-fun f3 () Bool (and (or (= C g)(= C s)(= C b))(or (= D n1)(= D n2))))
;A won a medal, but C didn't
(define-fun f4 () Bool (and (or (= A g)(= A s)(= A b))(or (= C n1)(= C n2))))
;D won a medal and E did, too
(define-fun f5 () Bool (and (or (= D g)(= D s)(= D b))(or (= E g)(= E s)(= E b))))
(assert(not (or f1 f2 f3 f4 f5)))
(check-sat)
(get-model)
$\endgroup$
  • $\begingroup$ shouldn't f3 be modified? D didn't get medal, B might've $\endgroup$ – Debanjan Chakraborty Dec 3 '14 at 11:14
2
$\begingroup$

Since all sentences are false, from (1) either A get gold or B get silver. And from (2) either D get silver or B get bronze.

Let's suppose B got silver. Then B didn't get bronze, so from (2) D must get silver too, and we have a contradiction (B and D both get silver).

So, A must get gold. For (4) to be false, C must also get a medal. And for (3) to be false, D must also get a medal. Since we have our 3 medalists, B and E must not get a medal. Then, from (2) we have that D get silver. And C is left with bronze.

$\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.