Discrtete math proof by contradiction problem

Question

I have the following problem that I must prove by CONTRADICTION:

"Show that if you pick three socks from a drawer containing just blue socks and black socks, you must get either a pair of blue socks or a pair of black socks."

I started to solve it writing 2 propositions: p: I pick three socks from a drawer containing just blue socks and black socks. q: I get either a pair of blue socks or a pair of black socks.

The normal conditional statement can be: p -> q. Now, to prove by contradiction I have to start from: (not p -> q)

My book says that in order to negate a proposition (p in this case) I should write: "It is not the case that I pick three socks from a drawer containing just blue socks and black socks." Or I can also write "I do not pick three socks from a drawer containing just blue socks and black socks". I see that if I do not pick 3 socks then I can pick less than 3 or more than 3 or none at all.

How can I interpret this new statement? How can I start the solution?

Answer 1

To begin by contradiction of the statement "if $P$ then $Q$," you suppose $P$ and not $Q$ and show there's something wrong with that.

From a formal logic perspective, you take as a temporary premise $P$ and then as a temporary premise $\lnot Q$, and arrive at a contradiction. Once you're at a contradiction, you can dismiss $\lnot Q$ in favor of $Q$, and then close your conditional as if $P$ then $Q$.

In this case, you say "Suppose I pick three socks out of the drawer, and I get neither a blue pair nor a black pair."

From there, can you argue that you must have some kind of contradiction?

Answer 2

With a proof by contradiction, we assume that the statement is false, and show that this leads to a contradiction (i.e. something that is false). In your case, we want to prove the statement: $\textbf{If}$ I pick three socks from a drawer that contains only blue and black socks $\textbf{then}$ I get either a blue or a black pair. The negation of this statement is that there is a way to pick three socks such that that are no (blue or black) pairs. If we assume that this is true, then we can have at most one black and at most one blue sock. That we have at most one black sock implies that we have at least two blue socks, which is a contradiction with the statement that we only have at most one blue sock.