Mixing
In a sequence of $34$ odd integers $a_1,a_2, cdots , a_34$ between $1$ and $100$ there exist $i neq j$ such that $a_imid a_j$.
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
In a sequence of $34$ odd integers $a_1,a_2, cdots , a_34$ between $1$ and $100$ there exist $i neq j$ such that $a_i mid a_j$.
My attempt $:$
If one of the $34$ odd integers be $1$ we are clearly done with the proof. Otherwise $a_i geq 3$ for all $i=1,2, cdots , 34$. By division algorithm $a_i=3m_i + r_i$ for $0 leq r_i leq 2$. Since $3 leq a_i leq 100$ it is clear that $1 leq m_i leq 33$. Since we have $34$ integers by Pigeonhole principle there exist $i < j$ such that $m_i = m_j= k$ (say). Then $a_i = 3k + r_i$ and $a_j = 3k + r_j$. If $k$ is even then both of $r_i$ and $r_j$ should be odd since both of $a_i$ and $a_j$ are odd. Since $0 leq r_i leq 2$ and $0 leq r_j leq 2$. So we have $r_i=r_j=1$ in this case. Which implies $a_i=a_j$ and hence clearly $a_i mid a_j$ which proves the claim. But I find difficulty when $k$ is odd.
How do I tackle this case? Please help me in this regard.
Thank you very much.
combinatorics
asked Jul 15 at 6:27
Debabrata Chattopadhyay.
13611
 |Â
show 1 more comment
up vote
1
down vote
favorite
In a sequence of $34$ odd integers $a_1,a_2, cdots , a_34$ between $1$ and $100$ there exist $i neq j$ such that $a_i mid a_j$.
My attempt $:$
If one of the $34$ odd integers be $1$ we are clearly done with the proof. Otherwise $a_i geq 3$ for all $i=1,2, cdots , 34$. By division algorithm $a_i=3m_i + r_i$ for $0 leq r_i leq 2$. Since $3 leq a_i leq 100$ it is clear that $1 leq m_i leq 33$. Since we have $34$ integers by Pigeonhole principle there exist $i < j$ such that $m_i = m_j= k$ (say). Then $a_i = 3k + r_i$ and $a_j = 3k + r_j$. If $k$ is even then both of $r_i$ and $r_j$ should be odd since both of $a_i$ and $a_j$ are odd. Since $0 leq r_i leq 2$ and $0 leq r_j leq 2$. So we have $r_i=r_j=1$ in this case. Which implies $a_i=a_j$ and hence clearly $a_i mid a_j$ which proves the claim. But I find difficulty when $k$ is odd.
How do I tackle this case? Please help me in this regard.
Thank you very much.
combinatorics
asked Jul 15 at 6:27
Debabrata Chattopadhyay.
13611
2
Can you prove that if you have $51$ numbers between $1$ and $100$ then one of them is divisible by another one?
– Lord Shark the Unknown
Jul 15 at 6:30
Yes of course. By taking the prime factorization of each $a_i$ as $2^k_i. r_i$ for $i=1,2, cdots, 51$. Then all $r_i$'s are odd and they are $51$ in numbers. So by Pigeonhole principle there exist $i neq j$ such that $r_i=r_j$. WLOG we may assume that $i < j$. Then $a_i mid a_j$. Isn't it so?
– Debabrata Chattopadhyay.
Jul 15 at 6:37
2
Can you adapt this trick to your problem?
– Lord Shark the Unknown
Jul 15 at 6:37
In this case the prime factorization of $a_i$ starts from $3$.
– Debabrata Chattopadhyay.
Jul 15 at 6:43
Can you please give me some suggestion? I can't catch it on my own.
– Debabrata Chattopadhyay.
Jul 15 at 6:47
 |Â
show 1 more comment
up vote
1
down vote
favorite
up vote
1
down vote
favorite
In a sequence of $34$ odd integers $a_1,a_2, cdots , a_34$ between $1$ and $100$ there exist $i neq j$ such that $a_i mid a_j$.
My attempt $:$
If one of the $34$ odd integers be $1$ we are clearly done with the proof. Otherwise $a_i geq 3$ for all $i=1,2, cdots , 34$. By division algorithm $a_i=3m_i + r_i$ for $0 leq r_i leq 2$. Since $3 leq a_i leq 100$ it is clear that $1 leq m_i leq 33$. Since we have $34$ integers by Pigeonhole principle there exist $i < j$ such that $m_i = m_j= k$ (say). Then $a_i = 3k + r_i$ and $a_j = 3k + r_j$. If $k$ is even then both of $r_i$ and $r_j$ should be odd since both of $a_i$ and $a_j$ are odd. Since $0 leq r_i leq 2$ and $0 leq r_j leq 2$. So we have $r_i=r_j=1$ in this case. Which implies $a_i=a_j$ and hence clearly $a_i mid a_j$ which proves the claim. But I find difficulty when $k$ is odd.
How do I tackle this case? Please help me in this regard.
Thank you very much.
combinatorics
asked Jul 15 at 6:27
Debabrata Chattopadhyay.
13611
In a sequence of $34$ odd integers $a_1,a_2, cdots , a_34$ between $1$ and $100$ there exist $i neq j$ such that $a_i mid a_j$.
My attempt $:$
If one of the $34$ odd integers be $1$ we are clearly done with the proof. Otherwise $a_i geq 3$ for all $i=1,2, cdots , 34$. By division algorithm $a_i=3m_i + r_i$ for $0 leq r_i leq 2$. Since $3 leq a_i leq 100$ it is clear that $1 leq m_i leq 33$. Since we have $34$ integers by Pigeonhole principle there exist $i < j$ such that $m_i = m_j= k$ (say). Then $a_i = 3k + r_i$ and $a_j = 3k + r_j$. If $k$ is even then both of $r_i$ and $r_j$ should be odd since both of $a_i$ and $a_j$ are odd. Since $0 leq r_i leq 2$ and $0 leq r_j leq 2$. So we have $r_i=r_j=1$ in this case. Which implies $a_i=a_j$ and hence clearly $a_i mid a_j$ which proves the claim. But I find difficulty when $k$ is odd.
How do I tackle this case? Please help me in this regard.
Thank you very much.
combinatorics
asked Jul 15 at 6:27
Debabrata Chattopadhyay.
13611
edited Jul 15 at 7:09
asked Jul 15 at 6:27
Debabrata Chattopadhyay.
13611
asked Jul 15 at 6:27
Debabrata Chattopadhyay.
13611
asked Jul 15 at 6:27
Debabrata Chattopadhyay.
13611
13611
2
Can you prove that if you have $51$ numbers between $1$ and $100$ then one of them is divisible by another one?
– Lord Shark the Unknown
Jul 15 at 6:30
Yes of course. By taking the prime factorization of each $a_i$ as $2^k_i. r_i$ for $i=1,2, cdots, 51$. Then all $r_i$'s are odd and they are $51$ in numbers. So by Pigeonhole principle there exist $i neq j$ such that $r_i=r_j$. WLOG we may assume that $i < j$. Then $a_i mid a_j$. Isn't it so?
– Debabrata Chattopadhyay.
Jul 15 at 6:37
2
Can you adapt this trick to your problem?
– Lord Shark the Unknown
Jul 15 at 6:37
In this case the prime factorization of $a_i$ starts from $3$.
– Debabrata Chattopadhyay.
Jul 15 at 6:43
Can you please give me some suggestion? I can't catch it on my own.
– Debabrata Chattopadhyay.
Jul 15 at 6:47
 |Â
show 1 more comment
2
Can you prove that if you have $51$ numbers between $1$ and $100$ then one of them is divisible by another one?
– Lord Shark the Unknown
Jul 15 at 6:30
Yes of course. By taking the prime factorization of each $a_i$ as $2^k_i. r_i$ for $i=1,2, cdots, 51$. Then all $r_i$'s are odd and they are $51$ in numbers. So by Pigeonhole principle there exist $i neq j$ such that $r_i=r_j$. WLOG we may assume that $i < j$. Then $a_i mid a_j$. Isn't it so?
– Debabrata Chattopadhyay.
Jul 15 at 6:37
2
Can you adapt this trick to your problem?
– Lord Shark the Unknown
Jul 15 at 6:37
In this case the prime factorization of $a_i$ starts from $3$.
– Debabrata Chattopadhyay.
Jul 15 at 6:43
Can you please give me some suggestion? I can't catch it on my own.
– Debabrata Chattopadhyay.
Jul 15 at 6:47
2
2
Can you prove that if you have $51$ numbers between $1$ and $100$ then one of them is divisible by another one?
– Lord Shark the Unknown
Jul 15 at 6:30
Can you prove that if you have $51$ numbers between $1$ and $100$ then one of them is divisible by another one?
– Lord Shark the Unknown
Jul 15 at 6:30
Yes of course. By taking the prime factorization of each $a_i$ as $2^k_i. r_i$ for $i=1,2, cdots, 51$. Then all $r_i$'s are odd and they are $51$ in numbers. So by Pigeonhole principle there exist $i neq j$ such that $r_i=r_j$. WLOG we may assume that $i < j$. Then $a_i mid a_j$. Isn't it so?
– Debabrata Chattopadhyay.
Jul 15 at 6:37
Yes of course. By taking the prime factorization of each $a_i$ as $2^k_i. r_i$ for $i=1,2, cdots, 51$. Then all $r_i$'s are odd and they are $51$ in numbers. So by Pigeonhole principle there exist $i neq j$ such that $r_i=r_j$. WLOG we may assume that $i < j$. Then $a_i mid a_j$. Isn't it so?
– Debabrata Chattopadhyay.
Jul 15 at 6:37
2
2
Can you adapt this trick to your problem?
– Lord Shark the Unknown
Jul 15 at 6:37
Can you adapt this trick to your problem?
– Lord Shark the Unknown
Jul 15 at 6:37
In this case the prime factorization of $a_i$ starts from $3$.
– Debabrata Chattopadhyay.
Jul 15 at 6:43
In this case the prime factorization of $a_i$ starts from $3$.
– Debabrata Chattopadhyay.
Jul 15 at 6:43
Can you please give me some suggestion? I can't catch it on my own.
– Debabrata Chattopadhyay.
Jul 15 at 6:47
Can you please give me some suggestion? I can't catch it on my own.
– Debabrata Chattopadhyay.
Jul 15 at 6:47
 |Â
show 1 more comment
3 Answers
3
active
oldest
votes
up vote
4
down vote
accepted
Consider the prime factorization of $a_i$ as $$a_i=3^k_i.r_i, mathrm for i=1,2, cdots , 34.$$ Where $r_i$'s are odd integers between $1$ and $100$ since so are $a_i$'s and $r_i$'s are relatively prime to $3$. Now there are $17$ odd integers between $1$ and $100$ which are divisible by $3$. So there are $33$ odd integers between $1$ and $100$ which are relatively prime to $3$. Since $r_i$'s are $34$ in numbers so there exist $i neq j$ such that $r_i=r_j$. WLOG let us assume that $k_i leq k_j$. Then clearly $a_i mid a_j$ and we are done with the proof.
answered Jul 15 at 13:33
Arnab Chatterjee.
1,174318
add a comment |Â
up vote
0
down vote
WLOG assume that $i<j$ implies $a_i<a_j$. Let $a_i=3^k_ir_i$ where $3^k_i||a_i$. Since $a_i$ is odd, then $r_i$ must be odd too so it is of the form
$$r_i=p_1^alpha_1cdots p_m^alpha_m$$
Where $p_i$s are primes less than $100$ but more than $3$ and $alpha_i$s are positive integers. There are 23 primes that $p_i$ can be. Can you continue?
answered Jul 15 at 9:47
user496634
19518
add a comment |Â
up vote
0
down vote
There are $50$ odd numbers $n$ in the range $1le nle100$. Of these $17$ are odd multiples of $3$, place these in set $S_1$. Hence $33$ odd numbers are prime to $3$ in this range, place these in set $S_2$. Now if we pick $34$ odd numbers, one has to be in set $S_1$, say $a$, and one in $S_2$, say $b$, having $bmid a$, by the Pigeonhole Principle.
answered Jul 15 at 14:52
Daniel Buck
2,3341624
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
Consider the prime factorization of $a_i$ as $$a_i=3^k_i.r_i, mathrm for i=1,2, cdots , 34.$$ Where $r_i$'s are odd integers between $1$ and $100$ since so are $a_i$'s and $r_i$'s are relatively prime to $3$. Now there are $17$ odd integers between $1$ and $100$ which are divisible by $3$. So there are $33$ odd integers between $1$ and $100$ which are relatively prime to $3$. Since $r_i$'s are $34$ in numbers so there exist $i neq j$ such that $r_i=r_j$. WLOG let us assume that $k_i leq k_j$. Then clearly $a_i mid a_j$ and we are done with the proof.
answered Jul 15 at 13:33
Arnab Chatterjee.
1,174318
add a comment |Â
up vote
4
down vote
accepted
Consider the prime factorization of $a_i$ as $$a_i=3^k_i.r_i, mathrm for i=1,2, cdots , 34.$$ Where $r_i$'s are odd integers between $1$ and $100$ since so are $a_i$'s and $r_i$'s are relatively prime to $3$. Now there are $17$ odd integers between $1$ and $100$ which are divisible by $3$. So there are $33$ odd integers between $1$ and $100$ which are relatively prime to $3$. Since $r_i$'s are $34$ in numbers so there exist $i neq j$ such that $r_i=r_j$. WLOG let us assume that $k_i leq k_j$. Then clearly $a_i mid a_j$ and we are done with the proof.
answered Jul 15 at 13:33
Arnab Chatterjee.
1,174318
add a comment |Â
up vote
4
down vote
accepted
up vote
4
down vote
accepted
Consider the prime factorization of $a_i$ as $$a_i=3^k_i.r_i, mathrm for i=1,2, cdots , 34.$$ Where $r_i$'s are odd integers between $1$ and $100$ since so are $a_i$'s and $r_i$'s are relatively prime to $3$. Now there are $17$ odd integers between $1$ and $100$ which are divisible by $3$. So there are $33$ odd integers between $1$ and $100$ which are relatively prime to $3$. Since $r_i$'s are $34$ in numbers so there exist $i neq j$ such that $r_i=r_j$. WLOG let us assume that $k_i leq k_j$. Then clearly $a_i mid a_j$ and we are done with the proof.
answered Jul 15 at 13:33
Arnab Chatterjee.
1,174318
Consider the prime factorization of $a_i$ as $$a_i=3^k_i.r_i, mathrm for i=1,2, cdots , 34.$$ Where $r_i$'s are odd integers between $1$ and $100$ since so are $a_i$'s and $r_i$'s are relatively prime to $3$. Now there are $17$ odd integers between $1$ and $100$ which are divisible by $3$. So there are $33$ odd integers between $1$ and $100$ which are relatively prime to $3$. Since $r_i$'s are $34$ in numbers so there exist $i neq j$ such that $r_i=r_j$. WLOG let us assume that $k_i leq k_j$. Then clearly $a_i mid a_j$ and we are done with the proof.
answered Jul 15 at 13:33
Arnab Chatterjee.
1,174318
answered Jul 15 at 13:33
Arnab Chatterjee.
1,174318
answered Jul 15 at 13:33
Arnab Chatterjee.
1,174318
answered Jul 15 at 13:33
Arnab Chatterjee.
1,174318
1,174318
add a comment |Â
add a comment |Â
up vote
0
down vote
WLOG assume that $i<j$ implies $a_i<a_j$. Let $a_i=3^k_ir_i$ where $3^k_i||a_i$. Since $a_i$ is odd, then $r_i$ must be odd too so it is of the form
$$r_i=p_1^alpha_1cdots p_m^alpha_m$$
Where $p_i$s are primes less than $100$ but more than $3$ and $alpha_i$s are positive integers. There are 23 primes that $p_i$ can be. Can you continue?
answered Jul 15 at 9:47
user496634
19518
add a comment |Â
up vote
0
down vote
WLOG assume that $i<j$ implies $a_i<a_j$. Let $a_i=3^k_ir_i$ where $3^k_i||a_i$. Since $a_i$ is odd, then $r_i$ must be odd too so it is of the form
$$r_i=p_1^alpha_1cdots p_m^alpha_m$$
Where $p_i$s are primes less than $100$ but more than $3$ and $alpha_i$s are positive integers. There are 23 primes that $p_i$ can be. Can you continue?
answered Jul 15 at 9:47
user496634
19518
add a comment |Â
up vote
0
down vote
up vote
0
down vote
WLOG assume that $i<j$ implies $a_i<a_j$. Let $a_i=3^k_ir_i$ where $3^k_i||a_i$. Since $a_i$ is odd, then $r_i$ must be odd too so it is of the form
$$r_i=p_1^alpha_1cdots p_m^alpha_m$$
Where $p_i$s are primes less than $100$ but more than $3$ and $alpha_i$s are positive integers. There are 23 primes that $p_i$ can be. Can you continue?
answered Jul 15 at 9:47
user496634
19518
WLOG assume that $i<j$ implies $a_i<a_j$. Let $a_i=3^k_ir_i$ where $3^k_i||a_i$. Since $a_i$ is odd, then $r_i$ must be odd too so it is of the form
$$r_i=p_1^alpha_1cdots p_m^alpha_m$$
Where $p_i$s are primes less than $100$ but more than $3$ and $alpha_i$s are positive integers. There are 23 primes that $p_i$ can be. Can you continue?
answered Jul 15 at 9:47
user496634
19518
answered Jul 15 at 9:47
user496634
19518
answered Jul 15 at 9:47
user496634
19518
answered Jul 15 at 9:47
user496634
19518
19518
add a comment |Â
add a comment |Â
up vote
0
down vote
There are $50$ odd numbers $n$ in the range $1le nle100$. Of these $17$ are odd multiples of $3$, place these in set $S_1$. Hence $33$ odd numbers are prime to $3$ in this range, place these in set $S_2$. Now if we pick $34$ odd numbers, one has to be in set $S_1$, say $a$, and one in $S_2$, say $b$, having $bmid a$, by the Pigeonhole Principle.
answered Jul 15 at 14:52
Daniel Buck
2,3341624
add a comment |Â
up vote
0
down vote
There are $50$ odd numbers $n$ in the range $1le nle100$. Of these $17$ are odd multiples of $3$, place these in set $S_1$. Hence $33$ odd numbers are prime to $3$ in this range, place these in set $S_2$. Now if we pick $34$ odd numbers, one has to be in set $S_1$, say $a$, and one in $S_2$, say $b$, having $bmid a$, by the Pigeonhole Principle.
answered Jul 15 at 14:52
Daniel Buck
2,3341624
add a comment |Â
up vote
0
down vote
up vote
0
down vote
There are $50$ odd numbers $n$ in the range $1le nle100$. Of these $17$ are odd multiples of $3$, place these in set $S_1$. Hence $33$ odd numbers are prime to $3$ in this range, place these in set $S_2$. Now if we pick $34$ odd numbers, one has to be in set $S_1$, say $a$, and one in $S_2$, say $b$, having $bmid a$, by the Pigeonhole Principle.
answered Jul 15 at 14:52
Daniel Buck
2,3341624
There are $50$ odd numbers $n$ in the range $1le nle100$. Of these $17$ are odd multiples of $3$, place these in set $S_1$. Hence $33$ odd numbers are prime to $3$ in this range, place these in set $S_2$. Now if we pick $34$ odd numbers, one has to be in set $S_1$, say $a$, and one in $S_2$, say $b$, having $bmid a$, by the Pigeonhole Principle.
answered Jul 15 at 14:52
Daniel Buck
2,3341624
answered Jul 15 at 14:52
Daniel Buck
2,3341624
answered Jul 15 at 14:52
Daniel Buck
2,3341624
answered Jul 15 at 14:52
Daniel Buck
2,3341624
2,3341624
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2852231%2fin-a-sequence-of-34-odd-integers-a-1-a-2-cdots-a-34-between-1-and-1%23new-answer', 'question_page');
);
Post as a guest
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
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
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
2
Can you prove that if you have $51$ numbers between $1$ and $100$ then one of them is divisible by another one?
– Lord Shark the Unknown
Jul 15 at 6:30
Yes of course. By taking the prime factorization of each $a_i$ as $2^k_i. r_i$ for $i=1,2, cdots, 51$. Then all $r_i$'s are odd and they are $51$ in numbers. So by Pigeonhole principle there exist $i neq j$ such that $r_i=r_j$. WLOG we may assume that $i < j$. Then $a_i mid a_j$. Isn't it so?
– Debabrata Chattopadhyay.
Jul 15 at 6:37
2
Can you adapt this trick to your problem?
– Lord Shark the Unknown
Jul 15 at 6:37
In this case the prime factorization of $a_i$ starts from $3$.
– Debabrata Chattopadhyay.
Jul 15 at 6:43
Can you please give me some suggestion? I can't catch it on my own.
– Debabrata Chattopadhyay.
Jul 15 at 6:47