Quote Originally Posted by Julian View Post
Got a new question!

Was looking through old exams, studying for final, and there is this one pigeonhole problem which I just don't get.

Let x be an irrational number. Show that for some positive integer j not exceeding 6, the absolute value of the difference between jx and the nearest integer to jx is less than 1/6.

Part 2: Use the above to explain why it is possible to approximate the irrational number e = 2.71828blahblah... using a rational number of the form p/q (where 0 < q < 7) with error less than 1/6, |e-(p/q)| < 1/6
This one seems a little more trivial than the others; I think I see it intuitively but can't really write a more formal proof for it because I feel like I'm skipping a logical step somewhere.

Basically, if you have an irrational number x, you can define a range for x: (a + b/6, a + (b+1)/6), where a is an integer and b is an integer in {0, 1, 2, 3, 4, 5}. It's just a whole number plus a remainder, where the remainder falls into possible pigeonholes between each integer with width 1/6.

Rounding x gets you two values: a and a+1.

Assuming round(x) = a:

For |jx - (a)| < 1/6, you need to be able to show that the remainder term after multiplication by j falls within (0, 1/6). In order for that to happen, you need a value of j where jb ≡ 0 mod 6, which seems trivial because if 6 is a possible value of j, then obviously 6b ≡ 0 mod 6.

Assuming round(x) = a+1:

For |(a+1) - jx| < 1/6, you need to be able to show that the remainder term after multiplication by j falls within (5/6, 6/6), and thus jb ≡ 5 mod 6, which is just as trivial for the possible values of j and b.

Part 2: In the generalized case, if you divide up the number line into segments of width 1/q, there's going to be some integer p such that p/q < e < (p+1)/q. The distance from e to either possible rational bounding it has to be less than 1/q because that's the total length of each interval, and thus |e - p/q| < 1/q.

To make an error less than 1/6, you just define q = 6, which falls within the given bounds (0 < q < 7).