11Sorry, but just a minute.....We've to prove that there's a number whose difference from some integer is at max 1/n....I hope this is what we have 2 prove?
Prove that among the +ve numbers a,2a,3a,...,(n-1)a, there is one that differs by an integer by at most 1/n
-
UP 0 DOWN 0 0 14
14 Answers
11
1I don't really get this......
suppose we have 1/3, 2/3, 1, 4/3, 5/3, 2
ie. a=1/3 and n=5
then there is no such number whose difference from an integer is atmost 1/5
1Let the numbers " a , 2a , 3a , ........ ( n - 1 ) a " be marked on a real line . Also , let another real line have each interval between consecutive integers divided into " n " equal parts .
Now , wrap both real lines around a circle C having circumference of one unit in the same direction , preferably clock - wise , and starting with the same point " O " , which is an integer .
The second line divides C into n equal arcs , each having length " 1n " , while the first line marks " n - 1 " points on C . Now , if either of these " n - 1 " points are adjacent to O , i . e , they lie on the two immediate arcs next to O , then we are done ! Why ? Simply because the length of the arc is greater than the distance between the point and O .
Else , the " n - 1 " points are to be found in the remaining " n - 2 " arcs , which by Pigeon - Hole Principle , would imply that at least two of these lie on the same arc .
Let us suppose , that " x a " and " y a " ( x > y ) are two multiples of " a " that lie on the same arc . Then we must have ,
( x - y ) a < 1n
because , again , the length of the arc is greater than the distance between these two points .
But " ( x - y ) a " is again a multiple of " a " .
So , voila !
12 can be written in the form 1(3-1) ....a=1,n=3
2 differs from 2(an integer) by 0 which is less than 1/n = 1/3 !!!!!
1Notice that the problem states : - " at most 1n " , not " at least 1n " .
1i mean '0' is less than 1/3...
Ok....if u r correct.....if i consider 3 as the integer, then difference is 3-2=1 which is greater than 1/3.......
Is my method correct ?
1But the problem specifically states that we can find such a multiple of " a " that differs from " an " integer by at most " 1n " , not from just any integer .
In your case , " 2 " differs from " 2 " by " 0 ", which is less than " 13 " , but that does not mean that we should consider " 3 , 4 , 5 , 6 , ............" and so on .
1So u mean we need to prove that for each a(real>0) and n(natural),we can find one that differs from an integer by at most 1/n......rite?
thanx for the help ....
21Solution:
Let us assume the opposite that there will be no such number.
Consider the n boxes. [0,1/n] , (1/n , 2/n] ,...[(n-1)/n,1)
We have chosen (n-1) numbers. Look at their fractional parts.According to our assumption all the (n-1) fractions (pigeons) will fly to [1/n,2/n) ,[2/n,3/n)...[(n-2)/n, (n-1)/n) these n-2 boxes.So By PHP 1 some box must contain more than one pigeon. On subtracting them we prove that the fractional part of any one of those (n-1) numbers we choose lies between (0,1/n). This is a contradiction.
P.S: I am not convinced with the attempt of bijection between numerical values and lengths in # 8.
After 40 mins try when i could finally get it , i felt so stupid. i gave it to someone who did it in less than 5 mins. The problem was unknown to him too