Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are five competitor A, B, C, D, and E and they enter a running race that awards gold, silver, and bronze medals. Each of the following compound statements about the race is false, although one of the two clauses in each may be true.

1. A didn't win the gold, and B didn't win the silver.
2. D didn't win the silver, and E didn't win the bronze.
3. C won a medal, and D didn't.
4. A won a medal, and C didn't.
5. D and E both won medals.

Who won each of the medals?

Thanks in advance. Any help would be appreciated. :)

share|improve this question
    
This is the third "A tricky maths question" title that you have posted (today?), how about putting a bit more information into those titles? (And have you noticed that I remove the [logic] tag from each of those? Can you guess why? HINT: It doesn't belong there. :)) –  Asaf Karagila Mar 29 at 14:42
1  
Thanks for editing. Note that the word "logic" in mathematics means something else that what you probably have in mind. –  Jérémy Blanc Mar 29 at 14:59
1  
I don't understand why the logic tag is not appropriate. The question is about logic connectors and negation of proposition, isn't it a part of mathematical logic? –  Taladris Mar 29 at 15:52
2  
Are these problems for some other contest / competition that you're supposed to be participating in... ? –  Jason C Mar 29 at 22:01
1  
Yes. :) $ $ $ $ –  Harshal Gajjar Apr 1 at 6:00

5 Answers 5

up vote 3 down vote accepted

Let's look at statement 3 and 4, in particular we hypothesis that C loses. This implies that the second half of statement 4 is true, so this means that the first half is false: A didn't win a medal.

In statement 1 A didn't win the gold and that is true, this implies that is false that B didn't win silver, in other words B won the silver medal.

Now in statement 2, D didn't win the silver and that is true, because we know that it was actually B who won it, so again the second half is necessarily false: E won the bronze.

Now only D is left and he necessarily won the gold metal, but this is in contradiction with statement 5.

So in the end we can say that C won a medal.

Then because of statement 3, D won a medal.

Because of statement 5, E didn't won a medal.

Because of statement 2, D won a silver.

Because of statement 1, A won a gold.

We know that C won a medal, but because of the last 2 statement, we know he won a bronze medal

B necessarily lost

share|improve this answer
    
I have encountered many problems like this (but haven't been able to solve them :P) Can you please give me a piece of advice to solve these problems? –  Harshal Gajjar Mar 29 at 15:32
1  
Well, first of all try to figure out which statements are contradictory. Usually finding which of the two statements is true and which is false is the key to solve the problem. Then just make an assumption and test it. As you saw, I tested 3 and 4, because they were contradictory about C –  Lex Mar 29 at 15:57

I have encountered many problems like this (but haven't been able to solve them :P) Can you please give me a piece of advice to solve these problems?

I would start by converting all the statements from false statements into true statements, remembering that "or" includes the possibility of both being true.

False: A didn't win the gold, and B didn't win the silver.
True:  A won the gold or B won the silver. 

False: D didn't win the silver, and E didn't win the bronze.
True:  D won the silver or E won the bronze.

False: C won a medal, and D didn't.
True:  C won no medal or D won a medal.

False: A won a medal, and C didn't.
True:  A won no medal or C won a medal.

False: D and E both won medals.
True:  D won no medal or E won no medal.

So now we have five true statements:

1) A won the gold or B won the silver.
2) D won the silver or E won the bronze.
3) C won no medal or D won a medal.
4) A won no medal or C won a medal.
5) D won no medal or E won no medal.

Now make a guess. Let's guess that A did not win gold. Make a chart:

      GUESS ONE CHART
      GOLD SILVER BRONZE NONE
   A   NO
   B 
   C
   D
   E

Now fill in what we know on that chart. Since A did not win gold, B must have won silver:

      GUESS ONE CHART
      GOLD SILVER BRONZE NONE
   A   NO
   B       YES
   C
   D
   E

If B won silver then B didn't win anything else, and no one else won silver.

      GUESS ONE CHART
      GOLD SILVER BRONZE NONE
   A   NO   NO
   B   NO   YES     NO     NO
   C        NO
   D        NO
   E        NO

Now look at statement 2. In our hypothetical world, D didn't win the silver, so E must have won the bronze:

      GUESS ONE CHART
      GOLD SILVER BRONZE NONE
   A   NO   NO     NO
   B   NO   YES    NO     NO
   C        NO     NO
   D        NO     NO
   E   NO   NO     YES    NO

Now from statement 5 we know that D won no medal in this hypothetical world. We can't fill in the rest of the NONE column with NO because two people won no medal.

      GUESS ONE CHART
      GOLD SILVER BRONZE NONE
   A   NO   NO     NO
   B   NO   YES    NO     NO
   C        NO     NO
   D   NO   NO     NO     YES
   E   NO   NO     YES    NO

Now looking at the chart, the only person left for winning gold is C, and A won no medal. So fill that in:

      GUESS ONE CHART
      GOLD SILVER BRONZE NONE
   A   NO   NO     NO     YES
   B   NO   YES    NO     NO
   C   YES  NO     NO     NO
   D   NO   NO     NO     YES
   E   NO   NO     YES    NO

OK, we have completed the chart for the world in which A does not win gold. Does it match all the conditions?

1) A won the gold or B won the silver. YES.
2) D won the silver or E won the bronze. YES.
3) C won no medal or D won a medal. NO!

We have failed to meet a condition, so our guess must have been wrong. We now know a new fact:

6) A won the gold.

So let's try to fill out the chart again, knowing this new fact.

      REALITY CHART
      GOLD SILVER BRONZE NONE
   A   YES  NO     NO     NO
   B   NO
   C   NO
   D   NO
   E   NO

From statement 4 we know that:

      REALITY CHART
      GOLD SILVER BRONZE NONE
   A   YES  NO     NO     NO
   B   NO
   C   NO                 NO
   D   NO
   E   NO

From statement 3 we know that:

      REALITY CHART
      GOLD SILVER BRONZE NONE
   A   YES  NO     NO     NO
   B   NO
   C   NO                 NO
   D   NO                 NO
   E   NO

And now we know who won no medals:

      REALITY CHART
      GOLD SILVER BRONZE NONE
   A   YES  NO     NO     NO
   B   NO   NO     NO     YES
   C   NO                 NO
   D   NO                 NO
   E   NO   NO     NO     YES

From statement 2 we have:

      REALITY CHART
      GOLD SILVER BRONZE NONE
   A   YES  NO     NO     NO
   B   NO   NO     NO     YES
   C   NO   NO            NO
   D   NO   YES    NO     NO
   E   NO   NO     NO     YES

And that leaves

      REALITY CHART
      GOLD SILVER BRONZE NONE
   A   YES  NO     NO     NO
   B   NO   NO     NO     YES
   C   NO   NO     YES    NO
   D   NO   YES    NO     NO
   E   NO   NO     NO     YES

Now check the work:

1) A won the gold or B won the silver. YES.
2) D won the silver or E won the bronze. YES.
3) C won no medal or D won a medal. YES.
4) A won no medal or C won a medal. YES.
5) D won no medal or E won no medal. YES.

And we're done.

That solves the specific problem, but notice the general method:

  • Write down everything in terms of true statements; reasoning from falsehoods is difficult.
  • If there is not enough information to solve the problem directly, make a guess.
  • Explore the consequences of that guess. Do they lead to a contradiction? If so, the guess is wrong and you've deduced a new fact.
  • Track your knowledge in a carefully-labeled chart.

You might need to make multiple guesses; keep careful track of what guesses you've made. If you make guess X, get stuck, make guess Y, and deduce contradiction, then you've deduced that "if guess X is right then guess Y is wrong", not "X and Y are both wrong". Do you see why that is?

share|improve this answer
1  
Damn, I've been typing my own answer all this time and I just saw yours. –  Veritas Mar 29 at 17:10
    
Thank you very much. :D –  Harshal Gajjar Mar 29 at 17:57
    
@Veritas: I assure you I did not. !(!A&!B) is just a complicated way of writing A|B. –  Eric Lippert Mar 29 at 21:36
    
Sorry I misunderstood your wording! –  Veritas Mar 29 at 21:47
1  
Tip 1: Before making a guess, examine the set of rules. Making guesses which are touched by more rules tends to yield solutions more rapidly. Tip 2: After learning a piece of information which guarantees a statement will be true, remove that statement from consideration (e.g., after deciding that A won a gold, you can ignore statement 1; it has no more information to yield). Advanced Tip: If a guess is taking too long to help, try guessing the negation. If a guess and its negation both yield a conclusion, you can conclude that information is true, even without knowing which guess is true. –  Brian Mar 31 at 13:31

Ok so here is how to solve such problems:

Since the claims use AND to connect their statements and we know that the claims are false, then at least one of their statements must be false.

We begin by listing the possibilities and organizing them in triples :


  • 1.1 A didn't win the gold, B won the silver.
  • 1.2 A won the gold, B didn't win the silver.
  • 1.2 A won the gold, B won the silver.

  • 2.1 D didn't win the silver, E won the bronze.
  • 2.2 D won the silver, E didn't win the bronze.
  • 2.3 D won the silver, E won the bronze.

  • 3.1 C won a medal, D won a metal.
  • 3.2 C didn't win a medal, D didn't win a medal.
  • 3.3 C didn't win a medal, D won a medal.

  • 4.1 A won a medal, C won a medal.
  • 4.2 A didn't win a medal, C didn't win a medal.
  • 4.3 A didn't win a medal, C won a medal.

  • 5.1 D won a medal, E didn't win a medal.
  • 5.2 D didn't win a medal, E won a medal.
  • 5.3 D didn't win a medal, E didn't win a medal.

Now, for each triple, one of the statements is true. Therefore, what you need to do is choose a triple. I will choose 4. Next choose one of it's statements. I will choose 4.2.

For the next part it will be useful to make a small boolean table:

            A   B   C   D   E
Won Medal |   |   |   |   |   |
No Medal  |   |   |   |   |   |
Gold      |   |   |   |   |   |
Silver    |   |   |   |   |   |
Bronze    |   |   |   |   |   |

Assuming 4.2 is correct:

            A   B   C   D   E
Won Medal |   |   |   |   |   |
No Medal  | X |   | X |   |   |
Gold      |   |   |   |   |   |
Silver    |   |   |   |   |   |
Bronze    |   |   |   |   |   |

We are done with triple 4 so we must choose another triple in which one of the statements should be true according to what we know. We know that A and C have no medals so we need to find a triple that has relationships between A or C and another player.

Other than triple 4 the only triple that says something about A is the 1st triple. We know that A has no medal so he can't have the gold. Therefore 1.1 must be correct.

We update our table:

            A   B   C   D   E
Won Medal |   |   |   |   |   |
No Medal  | X |   | X |   |   |
Gold      |   |   |   |   |   |
Silver    |   | X |   |   |   |
Bronze    |   |   |   |   |   |

Now we have to choose one of the remaining triples, namely 2,3 and 5.

In the 5th triple we can see that none of the options is true since both E and D need to win a medal in order for the race to have 3 winners.

Since one statement has to be true but assuming that 4.2 was, correct logically led us to the conclusion that there isn't one, we can be certain that 4.2 cannot be correct.

We will just check all the remaining statements of the 4th triple. Namely 4.1 and 4.3.

If you choose 4.3 and repeat the same procedure , you will also come to an illogical conclusion. Therefore 4.1 must be the correct statement.

Here is the same procedure for 4.1 just to be sure:

            A   B   C   D   E
Won Medal | X |   | X |   |   |
No Medal  |   |   |   |   |   |
Gold      |   |   |   |   |   |
Silver    |   |   |   |   |   |
Bronze    |   |   |   |   |   |

Looking at the 3rd triple we can see that 3.1 can be the only correct statement. We update our table:

            A   B   C   D   E
Won Medal | X |   | X | X |   |
No Medal  |   |   |   |   |   |
Gold      |   |   |   |   |   |
Silver    |   |   |   |   |   |
Bronze    |   |   |   |   |   |

Looking at the 5th triple we can see that 5.1 can be the only correct statement so we update our table once again:

            A   B   C   D   E
Won Medal | X |   | X | X |   |
No Medal  |   |   |   |   | X |
Gold      |   |   |   |   |   |
Silver    |   |   |   |   |   |
Bronze    |   |   |   |   |   |

Looking at the 2nd triple we can see that 2.2 is the correct statement.

            A   B   C   D   E
Won Medal | X |   | X | X |   |
No Medal  |   |   |   |   | X |
Gold      |   |   |   |   |   |
Silver    |   |   |   | X |   |
Bronze    |   |   |   |   |   |

Finally looking at the 1st triple we can see that that the only correct statement is 1.2 since we already concluded that D has the silver.

            A   B   C   D   E
Won Medal | X |   | X | X |   |
No Medal  |   |   |   |   | X |
Gold      | X |   |   |   |   |
Silver    |   |   |   | X |   |
Bronze    |   |   |   |   |   |

Since only 3 can be the winners, A has the gold, D has the silver and C has to have the bronze.

share|improve this answer
1  
Thank you very much. :D –  Harshal Gajjar Mar 29 at 17:56

Hint: For example, $[A$ or $B]$ is false if and only if $[[$ not $A]$ and $[$not $B]]$ is true. So if you want you can write down five true statements.

The true statement derived from the first, for example, is $A$ won the gold or $B$ won the silver.

share|improve this answer

You can simply brute force it. Basiscall, you have to check all permutations of [0,0,1,2,3]. For the 3, you have 5 places to choose. For the 2 you have 4. For the 1 you have 3. That makes $3\cdot4 \cdot 5 = 60$ possibilites.

Here is a Python solution:

from itertools import permutations

class Medals:
    GOLD = 1
    SILVER = 2
    BRONZE = 3
    NONE = 0


medals = [Medals.GOLD, Medals.SILVER, Medals.BRONZE, Medals.NONE, Medals.NONE]

for A, B, C, D, E in set(permutations(medals)):
    if not (A != Medals.GOLD and B != Medals.SILVER) and \
       not (D != Medals.SILVER and E != Medals.BRONZE) and \
       not (C > Medals.NONE and D == Medals.NONE) and \
       not (A > Medals.NONE and C == Medals.NONE) and \
       not (D > Medals.NONE and E > Medals.NONE):
            print("A:%s B:%i C:%i D:%i E:%i" % (A, B, C, D, E))

See ideone to edit / run it.

Which gives only one possible solution:

A:1 B:0 C:3 D:2 E:0

Alternative solutions

The problem statement did not say that there is only one gold medal. So lets assume there are two. This would give the solutions:

A:1 B:3 C:1 D:2 E:0
A:1 B:1 C:3 D:2 E:0

If there are three bronze / silver / gold medals, there is no solution.

If there are two silver medals, there are the following solutions:

A:3 B:2 C:1 D:2 E:0
A:1 B:3 C:2 D:2 E:0
A:1 B:2 C:3 D:2 E:0

If there are two bronze medals, the solution is:

A:1 B:3 C:3 D:2 E:0

If there are two gold medals and due to two gold medals no silver medal, there is no solution.

If there are two silver medals and due to two silver medals no bronze medal, the solutions are:

A:0 B:2 C:1 D:2 E:0
A:1 B:0 C:2 D:2 E:0
share|improve this answer
    
I rechecked. If A won a gold, because of statement 4 and 3, C and D also win a medal. This implies no medal for B. –  Lex Mar 31 at 8:33
1  
Not sure, but it seems you forgot to add statement 4 in your interaction –  Lex Mar 31 at 8:36
    
@Lex: Thank you very much. I've fixed my solution –  moose Mar 31 at 8:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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