18
$\begingroup$

I started writing a proof using the method of proof by contradiction and encountered a situation which was true. More specifically, the hypothesis that I set out to prove was:

If the first 10 positive integer is placed around a circle, in any order, there exists 3 integer in consecutive locations around the circle that have a sum greater than or equal to 17. (From Discrete Mathematics and its Applications - K. Rosen)

This is how I proceeded:

Let $a_i$ denote the $i^{th}$ integer on the boundary of the circle. To proceed with proof by contradiction, we assume that $\forall i$

$a_i + a_{i+1} + a_{i+2} < 17$

Then,

$a_1 + a_2 + a_3 < 17$

$a_2 + a_3 + a_4 < 17$

$\vdots$

$a_{10} + a_1 + a_2 < 17$

$\therefore\ 3 \cdot (a_1 + a_2 + \dots + a_{10}) < 17 \cdot10$

$\Rightarrow\ 3 \cdot 55 < 170$

$\Rightarrow\ 165 < 170$

which is true. What does this mean?

P.S. I am not looking for the solution to this problem. I am aware of how to prove the claim. I am just curious about what it means to arrive at a truth after assuming the negation of the hypothesis.

$\endgroup$
9
  • 15
    $\begingroup$ It doesn't mean very much -- you've made the assumption that any three consecutive numbers will sum to no more than 16, so if after making that assumption you conclude that it's true, then you've just sort of gone in a circle $\endgroup$
    – Sort of Damocles
    Sep 13, 2018 at 16:21
  • 11
    $\begingroup$ It means your proof doesn't work. Either proof by contradiction is not the right approach, or you need to find stronger statements you can make. In the present instance, you really haven't used the fact the $3$ number are consecutive in any way. $\endgroup$
    – saulspatz
    Sep 13, 2018 at 16:22
  • $\begingroup$ @Vasya $a_9+a_{10}+a_1$ is implicitly part of the $\vdots$ $\endgroup$
    – Henry
    Sep 13, 2018 at 16:27
  • 3
    $\begingroup$ I should certainly hope it means nothing, because what's the difference between "not leading to a contradiction" and "I couldn't find a contradiction"? Assume the Riemann hypothesis is false. Hmm, can't seem to think of a contradiction off the top of my head. Guess it must be true. $\endgroup$
    – Jack M
    Sep 14, 2018 at 9:12
  • 1
    $\begingroup$ The simplest way to get from your non-proof to a genuine contradiction is to replace "<17" with "<=16" since we are dealing with integers. That then gives "165 <= 160" which is the contradiction you seek. But I agree with the others who say that if you don't arrive at a contradiction, your "proof" isn't proving anything one way or another (though it may give you an idea for a counter-example) $\endgroup$
    – JDL
    Sep 14, 2018 at 14:51

5 Answers 5

Reset to default
46
$\begingroup$

Your goal is to show that $p$ is false.

If $p \implies q$ and $q$ is true.

We can't conclude if $p$ is true or false. Hence, we get an inconclusive situation.

$\endgroup$
6
  • $\begingroup$ Could you provide some context by telling what $p$ and $q$ are in the case of this example? $\endgroup$
    – Eulerian
    Sep 13, 2018 at 16:45
  • 1
    $\begingroup$ your $p$ is "every $3$ in consecutive locations around the table has a sum that is less than $17$. your $q$ is $165<170$. $\endgroup$
    – Siong Thye Goh
    Sep 13, 2018 at 16:54
  • 11
    $\begingroup$ yup, if it's sunny ($p$) , i go to play ($q$). But if you observe that I go to play, you can't conclude that it's sunny. $\endgroup$
    – Siong Thye Goh
    Sep 13, 2018 at 17:13
  • 4
    $\begingroup$ Note that the implications of many algebraic manipulations work in both directions - for example, $x + 1 = 2$ implies $x = 1$, but $x = 1$ also implies $x + 1 = 2$. If all the steps in your proof are reversible then you've shown $q$ to imply $p$, thus $p$ is true. But that's not the case in your example - the step where you sum up your inequalities is a single-direction implication (the statement after your three dots does not imply the 10 statements before it). $\endgroup$
    – MartianInvader
    Sep 13, 2018 at 21:08
  • 1
    $\begingroup$ It could be set up a little differently to work. Although $165<170$ is true it is still a contradiction because an average sum of $16.5$ necessitates scores both above and below $16.5$ because it is not a whole number. $\endgroup$
    – Phil H
    Sep 13, 2018 at 21:18
29
$\begingroup$

It means that your precise approach does not work, but since this does not provide a counterexample it means the question would still be open.

Seeing $170-165$ is so small, there may be a way to save your proof. Try $$a_i + a_{i+1} + a_{i+2} \le 16$$

leading to $$3 \cdot (a_1 + a_2 + \dots + a_{10}) \le 16 \cdot10$$ and $$165 \le 160$$ for a contradiction

$\endgroup$
4
  • $\begingroup$ I see it now, thanks $\endgroup$
    – Vasili
    Sep 13, 2018 at 16:29
  • $\begingroup$ Woah! I didn't know that proofs could be tweaked like this to change the conclusions. Thanks for your input! However, could you explain why arriving at a truth $(165 < 170)$ does not mean that the initial assumptions must be true? $\endgroup$
    – Eulerian
    Sep 13, 2018 at 16:44
  • 2
    $\begingroup$ @NihalJain If you show $p \implies q$ then this excludes the possibility that $p$ is true and $q$ is false, but there remain three possibilities: (1) $p$ is true and $q$ is true; (2) $p$ is false and $q$ is true; (3) $p$ is false and $q$ is false. If you also know that $q$ is true then that excludes (3), but does not help in deciding between (1) and (2), so it is possible that $p$ is true and it is possible that $p$ is false. $\endgroup$
    – Henry
    Sep 13, 2018 at 17:08
  • $\begingroup$ @Henry yes, this point was made even below. I've understood where I went wrong. Thanks :) $\endgroup$
    – Eulerian
    Sep 13, 2018 at 17:40
2
$\begingroup$

A proof by contradiction functions by saying "if A is false, B must be true. I can prove that B is false, so A cannot be false."

You proved that B is true. This means that A could be false, but is not necessarily so because we have made no statements that relate the truth of A to the truth of B.

$\endgroup$
1
$\begingroup$

You can (more or less) avoid the complications of a proof by contradiction by reasoning as follows:

The total of the $10$ sums of consecutive triplets $a_i+a_{i+1}+a_{i+2}$ is $3 \times 55 = 165$. Therefore the average of the sums of consecutive triplets is $165/10 = 16.5$. But each sum is an integer, and if a set of integers has an average of $16.5$, at least one of them must be $\ge 17$.

(It could perhaps be argued that the final claim here requires a proof, and that would be a proof by contradiction.)

$\endgroup$
2
  • 1
    $\begingroup$ I don't see how this answers the actual question being asked, namely what does it mean when you try proof by contradiction and don't find a contradiction. $\endgroup$
    – David Z
    Sep 15, 2018 at 0:32
  • $\begingroup$ @DavidZ The original question was already answered but the discussion had moved on. I was offering an alternative approach. $\endgroup$
    – gandalf61
    Sep 15, 2018 at 6:30
0
$\begingroup$

Try this. Assuming there is a solution that always sums to less than $17$ for $3$ consecutive numbers, and building around the number $10$, the only possible number combinations adjacent to $10$ will be $4$ numbers from the subset $1,2,3,4,5$. Taking the maximum of these as $1,5$ and $2,4$ $(1,5,10,2,4)$ leaves a minimum sequence of $3,6,7,8,9$.

These $5$ numbers are impossible to arrange so all $3$ consecutive numbers in this subset are less than $17$. That is, the only $3$ numbers summing to less than $17$ are $6,3,7$ and adding an $8$ or $9$ to this sequence results in a $3$ consecutive number sum being greater than $16$. Hence the impossibility or contradiction of this assumption.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .