beatricalwu

Answered

2022-07-17

Discrete maths: proof by contradiction

I have a prove by contradiction question. For example, say 15 children together gathered 100 marbles.

How do I prove by contradiction that some pair of children gathered the same number?

I have a prove by contradiction question. For example, say 15 children together gathered 100 marbles.

How do I prove by contradiction that some pair of children gathered the same number?

Answer & Explanation

phravincegrln2

Expert

2022-07-18Added 19 answers

Step 1

You begin by assuming that the desired result is false: no two children gathered the same number of marbles. In that case what is the smallest possible number of marbles that they could have gathered altogether? The smallest set of 15 different non-negative integers is

$M=\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\};$

if each child gathered a different number of marbles, they must have gathered at least as are in the set M. How many is that? Is that possible if they gathered 100 marbles altogether?

Step 2

If the answer to that last question is no, you’ve reached the desired contradiction: you’ve shown that it’s impossible for each of them to have gathered a different number of marbles. This of course implies that two of them must have gathered the same number.

You begin by assuming that the desired result is false: no two children gathered the same number of marbles. In that case what is the smallest possible number of marbles that they could have gathered altogether? The smallest set of 15 different non-negative integers is

$M=\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\};$

if each child gathered a different number of marbles, they must have gathered at least as are in the set M. How many is that? Is that possible if they gathered 100 marbles altogether?

Step 2

If the answer to that last question is no, you’ve reached the desired contradiction: you’ve shown that it’s impossible for each of them to have gathered a different number of marbles. This of course implies that two of them must have gathered the same number.

Noelanijd

Expert

2022-07-19Added 3 answers

Step 1

Just to expand on Brian's answer, to outline the general approach when writing a proof by contradiction:

- We have the "givens", which is one or more "knowns" or premises that we accept as true (as given). Call them premises P.

- We have a conclusion we need to prove: Call this C.

So our objective is to show that $P\to C$. That is, if the premise(s) is/are true, then the conclusion must be true.

A proof by contradiction then explores what would happen if C were to be false, with the aim of finding a contradiction:

Step 2

We start by assuming $\mathrm{\neg}C.\phantom{\rule{thickmathspace}{0ex}}$.

- "Suppose P is true, and assume it is not the case that C holds."

then ⋮

then ⋮

- Contradiction!

(Having assumed $\mathrm{\neg}C$, we are led to conclude something that simply CANNOT BE TRUE, given the premises and what we know to be true.)

- Therefore, if P is true, it cannot be the case that that our assumption $\mathrm{\neg}C$ is correct; that is, we reject the assumption "NOT C" , in order to avoid a contradiction, and are left, by default, to conclude that it is C which must follow from P

- Therefore, $P\to C$

Just to expand on Brian's answer, to outline the general approach when writing a proof by contradiction:

- We have the "givens", which is one or more "knowns" or premises that we accept as true (as given). Call them premises P.

- We have a conclusion we need to prove: Call this C.

So our objective is to show that $P\to C$. That is, if the premise(s) is/are true, then the conclusion must be true.

A proof by contradiction then explores what would happen if C were to be false, with the aim of finding a contradiction:

Step 2

We start by assuming $\mathrm{\neg}C.\phantom{\rule{thickmathspace}{0ex}}$.

- "Suppose P is true, and assume it is not the case that C holds."

then ⋮

then ⋮

- Contradiction!

(Having assumed $\mathrm{\neg}C$, we are led to conclude something that simply CANNOT BE TRUE, given the premises and what we know to be true.)

- Therefore, if P is true, it cannot be the case that that our assumption $\mathrm{\neg}C$ is correct; that is, we reject the assumption "NOT C" , in order to avoid a contradiction, and are left, by default, to conclude that it is C which must follow from P

- Therefore, $P\to C$

Most Popular Questions