Oldie but Goldie

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

14 Answers

11
Devil ·

Sorry, 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?

62
Lokesh Verma ·

yes.

341
Hari Shankar ·

??

1
Dipanjan Das ·

I 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

1
Dipanjan Das ·

oh sorry........got it now.
dont know what i was thinking...

341
Hari Shankar ·

:D. I wanted to give you time to reconsider. It paid off!

1
Ricky ·

Let 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 !

1
johncenaiit ·

2 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 !!!!!

1
Ricky ·

Notice that the problem states : - " at most 1n " , not " at least 1n " .

1
johncenaiit ·

i 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 ?

1
Ricky ·

But 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 .

1
johncenaiit ·

So 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 ....

1
Ricky ·

Yep .

21
Shubhodip ·

Solution:

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

Your Answer

Close [X]