E-StoreHome » Ask & Discuss » Mathematics. » Algebra « Back to Discussion
Algebra
Here a challenge for all the GoIIT members,Experts and Administrators!!I am sick and tired of users posting such doubts which are so lame and stupid that they themselves can answer if they atleast read the book carefully!!!(No insult intended!!)Well , come on atleast post some good questions which we previously had(about one year ago when Blade X and Nugorama was there!!)!!So once again I am starting one such thread!!This question is open to all!!(Try to answer it)
The question reads: ( I will post the solution after 2 days !! So anyone trying you have two days to solve the problem)
For integer n>=4 find the minimal integer f(n) such that for any positive integer m , in any subset with f(n) elements of the set{ m,m+1,.........,m+n-1} there are atleast three mutually prime numbers.
Comments (24)
Hey man one day is already going to be over and no one has uptill now not even came up with any answer!!
It is a pretty shame fellas. Not even the experts!!!!!!!!!!!!!!!!!! C' mmon experts show us your expertise rather than copying articles and replying to such foolish posts .
The problem given can be solved not only in one way but there are two ways to solve the problem!!!
An attempt:
It is obvious that the f(n) has to be greater than the number of even integers lying in the set which is p = ![left[ rac{n}{2} ight]](http://alt2.artofproblemsolving.com/Forum/latexrender/pictures/9/6/b/96ba739451b635bb5760af2ff1f142e3cf5aa6ca.gif)
or ![left[ rac{n}{2} ight]+1](http://alt2.artofproblemsolving.com/Forum/latexrender/pictures/d/5/c/d5ccca46c41e09ca87ecca902df4e29fa0b416ef.gif)
Consider the subset containing all the even numbers.
Statement 1: Now I claim that it is now enough to be able to select two consecutive odd integers and we have three numbers that are mutually prime to each other.
Proof:
If we have the sequence 2n-1,2n,2n+1 it satisfies the condition that all three are mutually prime to each other.
If we have the sequence as 2n,2n+1,2n+2,2n+3, from the previous argument the sub-sequence 2n+1,2n+2,2n+3 satisfies the given conditions.
Statement 2: From the sequence 
it is enough to choose n+1 members to ensure that we always have at least two consecutive members
Proof: Arrange the numbers as 
If we choose n+1 numbers we are forced to choose some two that are from the same set, i.e. two consecutive numbers
If the last index of the sequence is 2n+1, we obviously need to choose n+2.
We can summarise this as: from the sequence 
it is enough to choose ![left[ rac{n+1}{2} ight]+1](http://alt1.artofproblemsolving.com/Forum/latexrender/pictures/6/4/e/64eaa981dca376c5ead7f18686fecb401e3c5c13.gif)
members to ensure that we always have at least two consecutive members.
Now the number of odd numbers is n-p from which we have to ensure that some two consecutive odd numbers are selected. From the above result this nothing but ![left[ rac{m+1}{2} ight]+1](http://alt2.artofproblemsolving.com/Forum/latexrender/pictures/e/9/b/e9b7db3b66ac6b342b6f3877f41e683576a26608.gif)
where m=n-p
Hence we need to select a subset of the size ![p+left[ rac{m+1}{2} ight]+1](http://alt1.artofproblemsolving.com/Forum/latexrender/pictures/1/d/a/1da3d697c557c0aa909c57a0f93d039b2da50db2.gif)
where p and m are as above
and this is the expression for f(n).
PS: the m here obviously has no relation to the m appearing in the problem statement.
![k = \left[ \frac{n}{2} \right]](http://alt1.artofproblemsolving.com/Forum/latexrender/pictures/7/9/6/796000b684845b7b70406cb48de15f39b4fb6d0a.gif)
![f(n) = k + \left[ \frac{k+1}{2} \right]+1](http://alt1.artofproblemsolving.com/Forum/latexrender/pictures/7/8/0/7803eb0598361371688b165050c3b7125a58bbdb.gif)
![f(n) = k + \left[ \frac{k}{2}\right]+2](http://alt1.artofproblemsolving.com/Forum/latexrender/pictures/0/2/5/02517ab0a60a336cf43283f2204516406f3326bc.gif)
![f(n) = k + \left[ \frac{k+1}{2}\right]+2](http://alt1.artofproblemsolving.com/Forum/latexrender/pictures/8/d/a/8dad803d9d949fcce287ebd9cba5ed4965cfe08e.gif)
If we have the sequence 2n-1,2n,2n+1 it satisfies the condition that all three are mutually prime to each other.
this was the statement given by hari sir. pls xplain it to me. its a bit tricky.
2n-1,2n,2n+1. if we take 2n to be 8. then 2n-1 = 7, 2n+1 =9.
7 is a prime, but 9 is not a prime.
pls xplain.
If we have the sequence 2n-1,2n,2n+1 it satisfies the condition that all three are mutually prime to each other. this was the statement given by hari sir. pls xplain it to me. its a bit tricky. 2n-1,2n,2n+1. if we take 2n to be 8. then 2n-1 = 7, 2n+1 =9. 7 is a prime, but 9 is not a prime. pls xplain.
If we have the sequence 2n-1,2n,2n+1 it satisfies the condition that all three are mutually prime to each other. this was the statement given by hari sir. pls xplain it to me. its a bit tricky. 2n-1,2n,2n+1. if we take 2n to be 8. then 2n-1 = 7, 2n+1 =9. 7 is a prime, but 9 is not a prime. pls xplain.
relatively prime means that they do not have any prime factors in common.
Any two consecutive numbers are relatively prime:
Proof: Let the numbers be n and n+1. If p is a prime that divides n and n+1, it also divides their difference =1
Likewise any two consecutive odd numbers are relatively prime, as proceeding as above p would have to divide 2 i.e. p =2, but we know that no odd number is divisible by 2.
So, 2n-1,2n, 2n+1 are all mutually relatively prime
Great effort sir!!!!!!Kudos to you!!!! It s good to know that we still have experts like you!! Was the question a good one to think over??How was it sir??
Now coming to the problem, it was indeed a very good effort but you have been too ambiguous with the answer , but even I cannot nullify your answer !!( To be true your answer was not exactly i was looking for!!)
But the solution that is given requires an even more stronger assumptions and even more perfect statements.
Some places here and there even I could not understand !!
Ok now wait a bit while I upload the solution( today I will upload my self made solution and tomorrow the solution given in the book!!)
And once again kudos to you sir!!
(Now sir please review my solution and say whether it is more perfect than yours or not)
Here the first solution(Self made):
At first we verify the equations that f(4)=4 , f(5)=5, f(6)=6 hold. Now
I know that even though it is off the olympiad type but don't you think sir that whatever things that we cannot do complain that it is of the higher level(olympiad type)I think that the problem lies with us that we forget to adorn the beauty of the numbers!!
The second solution that is given in the book makes use of the exclusion and inclusion principle.I will upload it soon!!
(And one more thing sir I just wanted to know that even though I had qualified for the INMO this year I am finding it way too difficult to balance my boards and entrance and now this olympiad preparation.So can you advise me one thing sir that should i focus more on the entrance or on the olympiads.Can you help me with one thing sir can you say whether the book by Aurther angel ("Problem solving strategies ") a gud book??
Hope you liked the solution!!
Preparing for IIT-JEE ?
Arihant Revision Package for IIT JEE - Books, Practice Tests + Rank Predictor
@ INR 1,995/-
For Quick Info
Find Posts by Topics
Physics.
TopicsMathematics.
Chemistry.
Biology
Institutes
Parents
Board
Fun Zone
|
|
|
|
|
| 35,229,755 Engineering Questions Attempted |
6,69,530 Visitors Monthly |
79 Engg. Exam Covered |
431 Students Currently Online |
Connect with Us  |
 |
