Mixing
A subset of size $101$ from $1, 2, 3, ldots, 200$ must contain one element which divides another
$begingroup$
Let $A$ be a subset of size 101 from the set ${$1, 2, 3, . . . , 200$}$ (of size 200). Show that $A$ contains an $x$ and a $y$ such that $x$ divides $y$.
This seems like it has something to do with the pigeon hole principle since we are choosing more than half of the elements from $A$. For instance, there has to be at least one $x in A$ such that $x<100$, but I'm not quite sure how to proceed from here. I guess another way to state this problem is to say there exists an $r$ such that $rA cap A$ is nonempty.
combinatorics elementary-number-theory
edited Jan 6 '15 at 3:53
6005
37k752127
asked Jan 6 '15 at 0:34
DHHDHH
178110
$endgroup$
add a comment |
$begingroup$
Let $A$ be a subset of size 101 from the set ${$1, 2, 3, . . . , 200$}$ (of size 200). Show that $A$ contains an $x$ and a $y$ such that $x$ divides $y$.
This seems like it has something to do with the pigeon hole principle since we are choosing more than half of the elements from $A$. For instance, there has to be at least one $x in A$ such that $x<100$, but I'm not quite sure how to proceed from here. I guess another way to state this problem is to say there exists an $r$ such that $rA cap A$ is nonempty.
combinatorics elementary-number-theory
edited Jan 6 '15 at 3:53
6005
37k752127
asked Jan 6 '15 at 0:34
DHHDHH
178110
$endgroup$
1
$begingroup$
A golden oldie. If $x$ and $y$ are pigeons (numbers between $1$ and $200$) then $x$ and $y$ belong in the same pigeonhole if $xle y$ and $frac{y}{x}$ is a power of $2$.
$endgroup$
– André Nicolas
Jan 6 '15 at 0:55
add a comment |
$begingroup$
Let $A$ be a subset of size 101 from the set ${$1, 2, 3, . . . , 200$}$ (of size 200). Show that $A$ contains an $x$ and a $y$ such that $x$ divides $y$.
This seems like it has something to do with the pigeon hole principle since we are choosing more than half of the elements from $A$. For instance, there has to be at least one $x in A$ such that $x<100$, but I'm not quite sure how to proceed from here. I guess another way to state this problem is to say there exists an $r$ such that $rA cap A$ is nonempty.
combinatorics elementary-number-theory
edited Jan 6 '15 at 3:53
6005
37k752127
asked Jan 6 '15 at 0:34
DHHDHH
178110
$endgroup$
Let $A$ be a subset of size 101 from the set ${$1, 2, 3, . . . , 200$}$ (of size 200). Show that $A$ contains an $x$ and a $y$ such that $x$ divides $y$.
This seems like it has something to do with the pigeon hole principle since we are choosing more than half of the elements from $A$. For instance, there has to be at least one $x in A$ such that $x<100$, but I'm not quite sure how to proceed from here. I guess another way to state this problem is to say there exists an $r$ such that $rA cap A$ is nonempty.
combinatorics elementary-number-theory
combinatorics elementary-number-theory
edited Jan 6 '15 at 3:53
6005
37k752127
asked Jan 6 '15 at 0:34
DHHDHH
178110
edited Jan 6 '15 at 3:53
6005
37k752127
asked Jan 6 '15 at 0:34
DHHDHH
178110
edited Jan 6 '15 at 3:53
6005
37k752127
edited Jan 6 '15 at 3:53
6005
37k752127
edited Jan 6 '15 at 3:53
6005
37k752127
37k752127
asked Jan 6 '15 at 0:34
DHHDHH
178110
asked Jan 6 '15 at 0:34
DHHDHH
178110
asked Jan 6 '15 at 0:34
DHHDHH
178110
178110
1
$begingroup$
A golden oldie. If $x$ and $y$ are pigeons (numbers between $1$ and $200$) then $x$ and $y$ belong in the same pigeonhole if $xle y$ and $frac{y}{x}$ is a power of $2$.
$endgroup$
– André Nicolas
Jan 6 '15 at 0:55
add a comment |
1
$begingroup$
A golden oldie. If $x$ and $y$ are pigeons (numbers between $1$ and $200$) then $x$ and $y$ belong in the same pigeonhole if $xle y$ and $frac{y}{x}$ is a power of $2$.
$endgroup$
– André Nicolas
Jan 6 '15 at 0:55
1
1
$begingroup$
A golden oldie. If $x$ and $y$ are pigeons (numbers between $1$ and $200$) then $x$ and $y$ belong in the same pigeonhole if $xle y$ and $frac{y}{x}$ is a power of $2$.
$endgroup$
– André Nicolas
Jan 6 '15 at 0:55
$begingroup$
A golden oldie. If $x$ and $y$ are pigeons (numbers between $1$ and $200$) then $x$ and $y$ belong in the same pigeonhole if $xle y$ and $frac{y}{x}$ is a power of $2$.
$endgroup$
– André Nicolas
Jan 6 '15 at 0:55
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Represent numbers from the set in this format, $x=2^pq$. Where $q$ is an odd integer and $1le q le 200$ and $p ge 0$.
How many choices of $q$ are there? How many numbers are you selecting? Can you apply pigeon hole principle now?
answered Jan 6 '15 at 1:06
arindam mitraarindam mitra
873815
$endgroup$
1
$begingroup$
Ah! I see now. There are only 100 such $q's$ but $A$ has 101 numbers in it. So there must be $x, y in A$ such that $x = 2^p q$ and $y = 2^r q$, and hence WLOG x divides y. Thanks! Clever trick. Need to remember any number can be written as a power of 2 times an odd number. When you say it like that, I guess it is pretty obvious!
$endgroup$
– DHH
Jan 6 '15 at 1:18
$begingroup$
Yup exactly. Most Pigeon hole problems have these kind of tricks. Once you discover that it becomes easy .:)
$endgroup$
– arindam mitra
Jan 6 '15 at 1:26
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%2f1092501%2fa-subset-of-size-101-from-1-2-3-ldots-200-must-contain-one-element-whic%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Represent numbers from the set in this format, $x=2^pq$. Where $q$ is an odd integer and $1le q le 200$ and $p ge 0$.
How many choices of $q$ are there? How many numbers are you selecting? Can you apply pigeon hole principle now?
answered Jan 6 '15 at 1:06
arindam mitraarindam mitra
873815
$endgroup$
1
$begingroup$
Ah! I see now. There are only 100 such $q's$ but $A$ has 101 numbers in it. So there must be $x, y in A$ such that $x = 2^p q$ and $y = 2^r q$, and hence WLOG x divides y. Thanks! Clever trick. Need to remember any number can be written as a power of 2 times an odd number. When you say it like that, I guess it is pretty obvious!
$endgroup$
– DHH
Jan 6 '15 at 1:18
$begingroup$
Yup exactly. Most Pigeon hole problems have these kind of tricks. Once you discover that it becomes easy .:)
$endgroup$
– arindam mitra
Jan 6 '15 at 1:26
add a comment |
$begingroup$
Represent numbers from the set in this format, $x=2^pq$. Where $q$ is an odd integer and $1le q le 200$ and $p ge 0$.
How many choices of $q$ are there? How many numbers are you selecting? Can you apply pigeon hole principle now?
answered Jan 6 '15 at 1:06
arindam mitraarindam mitra
873815
$endgroup$
1
$begingroup$
Ah! I see now. There are only 100 such $q's$ but $A$ has 101 numbers in it. So there must be $x, y in A$ such that $x = 2^p q$ and $y = 2^r q$, and hence WLOG x divides y. Thanks! Clever trick. Need to remember any number can be written as a power of 2 times an odd number. When you say it like that, I guess it is pretty obvious!
$endgroup$
– DHH
Jan 6 '15 at 1:18
$begingroup$
Yup exactly. Most Pigeon hole problems have these kind of tricks. Once you discover that it becomes easy .:)
$endgroup$
– arindam mitra
Jan 6 '15 at 1:26
add a comment |
$begingroup$
Represent numbers from the set in this format, $x=2^pq$. Where $q$ is an odd integer and $1le q le 200$ and $p ge 0$.
How many choices of $q$ are there? How many numbers are you selecting? Can you apply pigeon hole principle now?
answered Jan 6 '15 at 1:06
arindam mitraarindam mitra
873815
$endgroup$
Represent numbers from the set in this format, $x=2^pq$. Where $q$ is an odd integer and $1le q le 200$ and $p ge 0$.
How many choices of $q$ are there? How many numbers are you selecting? Can you apply pigeon hole principle now?
answered Jan 6 '15 at 1:06
arindam mitraarindam mitra
873815
edited Jan 6 '15 at 1:17
answered Jan 6 '15 at 1:06
arindam mitraarindam mitra
873815
answered Jan 6 '15 at 1:06
arindam mitraarindam mitra
873815
answered Jan 6 '15 at 1:06
arindam mitraarindam mitra
873815
873815
1
$begingroup$
Ah! I see now. There are only 100 such $q's$ but $A$ has 101 numbers in it. So there must be $x, y in A$ such that $x = 2^p q$ and $y = 2^r q$, and hence WLOG x divides y. Thanks! Clever trick. Need to remember any number can be written as a power of 2 times an odd number. When you say it like that, I guess it is pretty obvious!
$endgroup$
– DHH
Jan 6 '15 at 1:18
$begingroup$
Yup exactly. Most Pigeon hole problems have these kind of tricks. Once you discover that it becomes easy .:)
$endgroup$
– arindam mitra
Jan 6 '15 at 1:26
add a comment |
1
$begingroup$
Ah! I see now. There are only 100 such $q's$ but $A$ has 101 numbers in it. So there must be $x, y in A$ such that $x = 2^p q$ and $y = 2^r q$, and hence WLOG x divides y. Thanks! Clever trick. Need to remember any number can be written as a power of 2 times an odd number. When you say it like that, I guess it is pretty obvious!
$endgroup$
– DHH
Jan 6 '15 at 1:18
$begingroup$
Yup exactly. Most Pigeon hole problems have these kind of tricks. Once you discover that it becomes easy .:)
$endgroup$
– arindam mitra
Jan 6 '15 at 1:26
1
1
$begingroup$
Ah! I see now. There are only 100 such $q's$ but $A$ has 101 numbers in it. So there must be $x, y in A$ such that $x = 2^p q$ and $y = 2^r q$, and hence WLOG x divides y. Thanks! Clever trick. Need to remember any number can be written as a power of 2 times an odd number. When you say it like that, I guess it is pretty obvious!
$endgroup$
– DHH
Jan 6 '15 at 1:18
$begingroup$
Ah! I see now. There are only 100 such $q's$ but $A$ has 101 numbers in it. So there must be $x, y in A$ such that $x = 2^p q$ and $y = 2^r q$, and hence WLOG x divides y. Thanks! Clever trick. Need to remember any number can be written as a power of 2 times an odd number. When you say it like that, I guess it is pretty obvious!
$endgroup$
– DHH
Jan 6 '15 at 1:18
$begingroup$
Yup exactly. Most Pigeon hole problems have these kind of tricks. Once you discover that it becomes easy .:)
$endgroup$
– arindam mitra
Jan 6 '15 at 1:26
$begingroup$
Yup exactly. Most Pigeon hole problems have these kind of tricks. Once you discover that it becomes easy .:)
$endgroup$
– arindam mitra
Jan 6 '15 at 1:26
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%2f1092501%2fa-subset-of-size-101-from-1-2-3-ldots-200-must-contain-one-element-whic%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
1
$begingroup$
A golden oldie. If $x$ and $y$ are pigeons (numbers between $1$ and $200$) then $x$ and $y$ belong in the same pigeonhole if $xle y$ and $frac{y}{x}$ is a power of $2$.
$endgroup$
– André Nicolas
Jan 6 '15 at 0:55