Mixing
Discrtete math proof by contradiction problem
$begingroup$
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?
discrete-mathematics pigeonhole-principle
edited Jun 2 '15 at 16:01
Lord_Farin
15.6k636108
asked Feb 15 '15 at 19:05
JORGEJORGE
1069
$endgroup$
add a comment |
$begingroup$
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?
discrete-mathematics pigeonhole-principle
edited Jun 2 '15 at 16:01
Lord_Farin
15.6k636108
asked Feb 15 '15 at 19:05
JORGEJORGE
1069
$endgroup$
$begingroup$
By contradiction is not the most natural way. But let's do it. Suppose to the contrary that we get $le 1$ blues, and $le 1$ blacks. Then the total number of socks we picked is $le 1+1$, contradicting the fact that we picked $3$.
$endgroup$
– André Nicolas
Feb 15 '15 at 19:10
add a comment |
$begingroup$
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?
discrete-mathematics pigeonhole-principle
edited Jun 2 '15 at 16:01
Lord_Farin
15.6k636108
asked Feb 15 '15 at 19:05
JORGEJORGE
1069
$endgroup$
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?
discrete-mathematics pigeonhole-principle
discrete-mathematics pigeonhole-principle
edited Jun 2 '15 at 16:01
Lord_Farin
15.6k636108
asked Feb 15 '15 at 19:05
JORGEJORGE
1069
edited Jun 2 '15 at 16:01
Lord_Farin
15.6k636108
asked Feb 15 '15 at 19:05
JORGEJORGE
1069
edited Jun 2 '15 at 16:01
Lord_Farin
15.6k636108
edited Jun 2 '15 at 16:01
Lord_Farin
15.6k636108
edited Jun 2 '15 at 16:01
Lord_Farin
15.6k636108
15.6k636108
asked Feb 15 '15 at 19:05
JORGEJORGE
1069
asked Feb 15 '15 at 19:05
JORGEJORGE
1069
asked Feb 15 '15 at 19:05
JORGEJORGE
1069
1069
$begingroup$
By contradiction is not the most natural way. But let's do it. Suppose to the contrary that we get $le 1$ blues, and $le 1$ blacks. Then the total number of socks we picked is $le 1+1$, contradicting the fact that we picked $3$.
$endgroup$
– André Nicolas
Feb 15 '15 at 19:10
add a comment |
$begingroup$
By contradiction is not the most natural way. But let's do it. Suppose to the contrary that we get $le 1$ blues, and $le 1$ blacks. Then the total number of socks we picked is $le 1+1$, contradicting the fact that we picked $3$.
$endgroup$
– André Nicolas
Feb 15 '15 at 19:10
$begingroup$
By contradiction is not the most natural way. But let's do it. Suppose to the contrary that we get $le 1$ blues, and $le 1$ blacks. Then the total number of socks we picked is $le 1+1$, contradicting the fact that we picked $3$.
$endgroup$
– André Nicolas
Feb 15 '15 at 19:10
$begingroup$
By contradiction is not the most natural way. But let's do it. Suppose to the contrary that we get $le 1$ blues, and $le 1$ blacks. Then the total number of socks we picked is $le 1+1$, contradicting the fact that we picked $3$.
$endgroup$
– André Nicolas
Feb 15 '15 at 19:10
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
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?
answered Feb 15 '15 at 19:08
walkarwalkar
2,4661024
$endgroup$
$begingroup$
Thank you. Now it looks much better to prove it.
$endgroup$
– JORGE
Feb 15 '15 at 19:40
add a comment |
$begingroup$
The proof is of the form P -> Q, where P is 'Pick 3 socks from drawer' and Q is 'pair of blue socks OR pair of black socks '. Now we can use contra positive to prove notQ -> notP.
notQ - 'number of blue socks <=1 AND number of black socks <=1'
since drawer only contains blue and black socks, we can only pick blue+black socks, but
blue + black <= 2.
therefore we can't pick 3 socks from drawer , which is notP.
therefore notQ -> notP or in other words P -> Q
answered Sep 7 '18 at 18:50
AaronAaron
111
$endgroup$
$begingroup$
The topic of "proof by contradiction" is closely related to contraposition, but it would be worth expanding on this connection to improve the Answer. Note also that there are previous Answers here, and you should try to highlight what is novel in your post.
$endgroup$
– hardmath
Sep 7 '18 at 21:37
add a comment |
$begingroup$
We can prove this using the method of contradiction.
We assume that we neither get a pair of blue socks nor do we get a pair of black socks, i.e., the number of blue socks we get is less than or equal 1 and the number of black socks is also less than or equal to 2.
If a is the number of blue socks and b is the number of black socks that we get, a<=1 and b<=1.
Since there are only two types of socks, adding the two we get:
a + b <= 2.
The maximum number of socks we can pick to get a<=1 and b<=1 is 2.
But since we pick three socks, three is not less than or equal to 2. Therefore our supposition was wrong, and the proof by contradiction is complete.
answered Sep 7 '18 at 19:29
ThinkboomThinkboom
213
$endgroup$
add a comment |
$begingroup$
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.
answered Feb 15 '15 at 19:11
UncountableUncountable
3,040514
$endgroup$
add a comment |
$begingroup$
Hopefully this is helpful - if it gets down voted would appreciate how I could improve it.
Let $n = x +y $ and $n$ be of the domain socks, $x$ be of the domain blue socks, $y$ be of the domain black socks, and $P(n)$ represent number of socks picked from a drawer. The statement could be represented as:
$$P(n) to exists x exists y(x>(n-2) lor y>(n-2))$$
To prove by contradiction would need to show that $p land lnot q equiv mathbf F$
Let $p = P(n)$ and $lnot q =forall x forall y(xle (n-2) land y le (n-2))$ you can prove $lnot q equiv mathbf F$ by substituting $y = n-x$
$lnot q =forall x forall y(xle (n-2) land (n-x le n-2))$
Simplified to
$lnot q =forall x forall y(xle (n-2) land x ge 2)$
Substituting for $n=3$ means that $lnot q =forall x forall y(xle 1 land x ge 2) equiv mathbf F$ as $x$ cannot be both less than or equal to 1, and greater than or equal to 2.
answered Jan 20 at 16:50
ElliottElliott
596
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1149432%2fdiscrtete-math-proof-by-contradiction-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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?
answered Feb 15 '15 at 19:08
walkarwalkar
2,4661024
$endgroup$
$begingroup$
Thank you. Now it looks much better to prove it.
$endgroup$
– JORGE
Feb 15 '15 at 19:40
add a comment |
$begingroup$
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?
answered Feb 15 '15 at 19:08
walkarwalkar
2,4661024
$endgroup$
$begingroup$
Thank you. Now it looks much better to prove it.
$endgroup$
– JORGE
Feb 15 '15 at 19:40
add a comment |
$begingroup$
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?
answered Feb 15 '15 at 19:08
walkarwalkar
2,4661024
$endgroup$
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?
answered Feb 15 '15 at 19:08
walkarwalkar
2,4661024
answered Feb 15 '15 at 19:08
walkarwalkar
2,4661024
answered Feb 15 '15 at 19:08
walkarwalkar
2,4661024
answered Feb 15 '15 at 19:08
walkarwalkar
2,4661024
2,4661024
$begingroup$
Thank you. Now it looks much better to prove it.
$endgroup$
– JORGE
Feb 15 '15 at 19:40
add a comment |
$begingroup$
Thank you. Now it looks much better to prove it.
$endgroup$
– JORGE
Feb 15 '15 at 19:40
$begingroup$
Thank you. Now it looks much better to prove it.
$endgroup$
– JORGE
Feb 15 '15 at 19:40
$begingroup$
Thank you. Now it looks much better to prove it.
$endgroup$
– JORGE
Feb 15 '15 at 19:40
add a comment |
$begingroup$
The proof is of the form P -> Q, where P is 'Pick 3 socks from drawer' and Q is 'pair of blue socks OR pair of black socks '. Now we can use contra positive to prove notQ -> notP.
notQ - 'number of blue socks <=1 AND number of black socks <=1'
since drawer only contains blue and black socks, we can only pick blue+black socks, but
blue + black <= 2.
therefore we can't pick 3 socks from drawer , which is notP.
therefore notQ -> notP or in other words P -> Q
answered Sep 7 '18 at 18:50
AaronAaron
111
$endgroup$
$begingroup$
The topic of "proof by contradiction" is closely related to contraposition, but it would be worth expanding on this connection to improve the Answer. Note also that there are previous Answers here, and you should try to highlight what is novel in your post.
$endgroup$
– hardmath
Sep 7 '18 at 21:37
add a comment |
$begingroup$
The proof is of the form P -> Q, where P is 'Pick 3 socks from drawer' and Q is 'pair of blue socks OR pair of black socks '. Now we can use contra positive to prove notQ -> notP.
notQ - 'number of blue socks <=1 AND number of black socks <=1'
since drawer only contains blue and black socks, we can only pick blue+black socks, but
blue + black <= 2.
therefore we can't pick 3 socks from drawer , which is notP.
therefore notQ -> notP or in other words P -> Q
answered Sep 7 '18 at 18:50
AaronAaron
111
$endgroup$
$begingroup$
The topic of "proof by contradiction" is closely related to contraposition, but it would be worth expanding on this connection to improve the Answer. Note also that there are previous Answers here, and you should try to highlight what is novel in your post.
$endgroup$
– hardmath
Sep 7 '18 at 21:37
add a comment |
$begingroup$
The proof is of the form P -> Q, where P is 'Pick 3 socks from drawer' and Q is 'pair of blue socks OR pair of black socks '. Now we can use contra positive to prove notQ -> notP.
notQ - 'number of blue socks <=1 AND number of black socks <=1'
since drawer only contains blue and black socks, we can only pick blue+black socks, but
blue + black <= 2.
therefore we can't pick 3 socks from drawer , which is notP.
therefore notQ -> notP or in other words P -> Q
answered Sep 7 '18 at 18:50
AaronAaron
111
$endgroup$
The proof is of the form P -> Q, where P is 'Pick 3 socks from drawer' and Q is 'pair of blue socks OR pair of black socks '. Now we can use contra positive to prove notQ -> notP.
notQ - 'number of blue socks <=1 AND number of black socks <=1'
since drawer only contains blue and black socks, we can only pick blue+black socks, but
blue + black <= 2.
therefore we can't pick 3 socks from drawer , which is notP.
therefore notQ -> notP or in other words P -> Q
answered Sep 7 '18 at 18:50
AaronAaron
111
answered Sep 7 '18 at 18:50
AaronAaron
111
answered Sep 7 '18 at 18:50
AaronAaron
111
answered Sep 7 '18 at 18:50
AaronAaron
111
111
$begingroup$
The topic of "proof by contradiction" is closely related to contraposition, but it would be worth expanding on this connection to improve the Answer. Note also that there are previous Answers here, and you should try to highlight what is novel in your post.
$endgroup$
– hardmath
Sep 7 '18 at 21:37
add a comment |
$begingroup$
The topic of "proof by contradiction" is closely related to contraposition, but it would be worth expanding on this connection to improve the Answer. Note also that there are previous Answers here, and you should try to highlight what is novel in your post.
$endgroup$
– hardmath
Sep 7 '18 at 21:37
$begingroup$
The topic of "proof by contradiction" is closely related to contraposition, but it would be worth expanding on this connection to improve the Answer. Note also that there are previous Answers here, and you should try to highlight what is novel in your post.
$endgroup$
– hardmath
Sep 7 '18 at 21:37
$begingroup$
The topic of "proof by contradiction" is closely related to contraposition, but it would be worth expanding on this connection to improve the Answer. Note also that there are previous Answers here, and you should try to highlight what is novel in your post.
$endgroup$
– hardmath
Sep 7 '18 at 21:37
add a comment |
$begingroup$
We can prove this using the method of contradiction.
We assume that we neither get a pair of blue socks nor do we get a pair of black socks, i.e., the number of blue socks we get is less than or equal 1 and the number of black socks is also less than or equal to 2.
If a is the number of blue socks and b is the number of black socks that we get, a<=1 and b<=1.
Since there are only two types of socks, adding the two we get:
a + b <= 2.
The maximum number of socks we can pick to get a<=1 and b<=1 is 2.
But since we pick three socks, three is not less than or equal to 2. Therefore our supposition was wrong, and the proof by contradiction is complete.
answered Sep 7 '18 at 19:29
ThinkboomThinkboom
213
$endgroup$
add a comment |
$begingroup$
We can prove this using the method of contradiction.
We assume that we neither get a pair of blue socks nor do we get a pair of black socks, i.e., the number of blue socks we get is less than or equal 1 and the number of black socks is also less than or equal to 2.
If a is the number of blue socks and b is the number of black socks that we get, a<=1 and b<=1.
Since there are only two types of socks, adding the two we get:
a + b <= 2.
The maximum number of socks we can pick to get a<=1 and b<=1 is 2.
But since we pick three socks, three is not less than or equal to 2. Therefore our supposition was wrong, and the proof by contradiction is complete.
answered Sep 7 '18 at 19:29
ThinkboomThinkboom
213
$endgroup$
add a comment |
$begingroup$
We can prove this using the method of contradiction.
We assume that we neither get a pair of blue socks nor do we get a pair of black socks, i.e., the number of blue socks we get is less than or equal 1 and the number of black socks is also less than or equal to 2.
If a is the number of blue socks and b is the number of black socks that we get, a<=1 and b<=1.
Since there are only two types of socks, adding the two we get:
a + b <= 2.
The maximum number of socks we can pick to get a<=1 and b<=1 is 2.
But since we pick three socks, three is not less than or equal to 2. Therefore our supposition was wrong, and the proof by contradiction is complete.
answered Sep 7 '18 at 19:29
ThinkboomThinkboom
213
$endgroup$
We can prove this using the method of contradiction.
We assume that we neither get a pair of blue socks nor do we get a pair of black socks, i.e., the number of blue socks we get is less than or equal 1 and the number of black socks is also less than or equal to 2.
If a is the number of blue socks and b is the number of black socks that we get, a<=1 and b<=1.
Since there are only two types of socks, adding the two we get:
a + b <= 2.
The maximum number of socks we can pick to get a<=1 and b<=1 is 2.
But since we pick three socks, three is not less than or equal to 2. Therefore our supposition was wrong, and the proof by contradiction is complete.
answered Sep 7 '18 at 19:29
ThinkboomThinkboom
213
answered Sep 7 '18 at 19:29
ThinkboomThinkboom
213
answered Sep 7 '18 at 19:29
ThinkboomThinkboom
213
answered Sep 7 '18 at 19:29
ThinkboomThinkboom
213
213
add a comment |
add a comment |
$begingroup$
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.
answered Feb 15 '15 at 19:11
UncountableUncountable
3,040514
$endgroup$
add a comment |
$begingroup$
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.
answered Feb 15 '15 at 19:11
UncountableUncountable
3,040514
$endgroup$
add a comment |
$begingroup$
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.
answered Feb 15 '15 at 19:11
UncountableUncountable
3,040514
$endgroup$
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.
answered Feb 15 '15 at 19:11
UncountableUncountable
3,040514
answered Feb 15 '15 at 19:11
UncountableUncountable
3,040514
answered Feb 15 '15 at 19:11
UncountableUncountable
3,040514
answered Feb 15 '15 at 19:11
UncountableUncountable
3,040514
3,040514
add a comment |
add a comment |
$begingroup$
Hopefully this is helpful - if it gets down voted would appreciate how I could improve it.
Let $n = x +y $ and $n$ be of the domain socks, $x$ be of the domain blue socks, $y$ be of the domain black socks, and $P(n)$ represent number of socks picked from a drawer. The statement could be represented as:
$$P(n) to exists x exists y(x>(n-2) lor y>(n-2))$$
To prove by contradiction would need to show that $p land lnot q equiv mathbf F$
Let $p = P(n)$ and $lnot q =forall x forall y(xle (n-2) land y le (n-2))$ you can prove $lnot q equiv mathbf F$ by substituting $y = n-x$
$lnot q =forall x forall y(xle (n-2) land (n-x le n-2))$
Simplified to
$lnot q =forall x forall y(xle (n-2) land x ge 2)$
Substituting for $n=3$ means that $lnot q =forall x forall y(xle 1 land x ge 2) equiv mathbf F$ as $x$ cannot be both less than or equal to 1, and greater than or equal to 2.
answered Jan 20 at 16:50
ElliottElliott
596
$endgroup$
add a comment |
$begingroup$
Hopefully this is helpful - if it gets down voted would appreciate how I could improve it.
Let $n = x +y $ and $n$ be of the domain socks, $x$ be of the domain blue socks, $y$ be of the domain black socks, and $P(n)$ represent number of socks picked from a drawer. The statement could be represented as:
$$P(n) to exists x exists y(x>(n-2) lor y>(n-2))$$
To prove by contradiction would need to show that $p land lnot q equiv mathbf F$
Let $p = P(n)$ and $lnot q =forall x forall y(xle (n-2) land y le (n-2))$ you can prove $lnot q equiv mathbf F$ by substituting $y = n-x$
$lnot q =forall x forall y(xle (n-2) land (n-x le n-2))$
Simplified to
$lnot q =forall x forall y(xle (n-2) land x ge 2)$
Substituting for $n=3$ means that $lnot q =forall x forall y(xle 1 land x ge 2) equiv mathbf F$ as $x$ cannot be both less than or equal to 1, and greater than or equal to 2.
answered Jan 20 at 16:50
ElliottElliott
596
$endgroup$
add a comment |
$begingroup$
Hopefully this is helpful - if it gets down voted would appreciate how I could improve it.
Let $n = x +y $ and $n$ be of the domain socks, $x$ be of the domain blue socks, $y$ be of the domain black socks, and $P(n)$ represent number of socks picked from a drawer. The statement could be represented as:
$$P(n) to exists x exists y(x>(n-2) lor y>(n-2))$$
To prove by contradiction would need to show that $p land lnot q equiv mathbf F$
Let $p = P(n)$ and $lnot q =forall x forall y(xle (n-2) land y le (n-2))$ you can prove $lnot q equiv mathbf F$ by substituting $y = n-x$
$lnot q =forall x forall y(xle (n-2) land (n-x le n-2))$
Simplified to
$lnot q =forall x forall y(xle (n-2) land x ge 2)$
Substituting for $n=3$ means that $lnot q =forall x forall y(xle 1 land x ge 2) equiv mathbf F$ as $x$ cannot be both less than or equal to 1, and greater than or equal to 2.
answered Jan 20 at 16:50
ElliottElliott
596
$endgroup$
Hopefully this is helpful - if it gets down voted would appreciate how I could improve it.
Let $n = x +y $ and $n$ be of the domain socks, $x$ be of the domain blue socks, $y$ be of the domain black socks, and $P(n)$ represent number of socks picked from a drawer. The statement could be represented as:
$$P(n) to exists x exists y(x>(n-2) lor y>(n-2))$$
To prove by contradiction would need to show that $p land lnot q equiv mathbf F$
Let $p = P(n)$ and $lnot q =forall x forall y(xle (n-2) land y le (n-2))$ you can prove $lnot q equiv mathbf F$ by substituting $y = n-x$
$lnot q =forall x forall y(xle (n-2) land (n-x le n-2))$
Simplified to
$lnot q =forall x forall y(xle (n-2) land x ge 2)$
Substituting for $n=3$ means that $lnot q =forall x forall y(xle 1 land x ge 2) equiv mathbf F$ as $x$ cannot be both less than or equal to 1, and greater than or equal to 2.
answered Jan 20 at 16:50
ElliottElliott
596
answered Jan 20 at 16:50
ElliottElliott
596
answered Jan 20 at 16:50
ElliottElliott
596
answered Jan 20 at 16:50
ElliottElliott
596
596
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1149432%2fdiscrtete-math-proof-by-contradiction-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
By contradiction is not the most natural way. But let's do it. Suppose to the contrary that we get $le 1$ blues, and $le 1$ blacks. Then the total number of socks we picked is $le 1+1$, contradicting the fact that we picked $3$.
$endgroup$
– André Nicolas
Feb 15 '15 at 19:10