Question

If \(x\) is a real number and \(n\) is an integer, prove that among \(x, 2x, \cdots , (n-1)x\), at least one differs from an integer by at most \(1/n\).

Answer 1

intuitively it sorta makes sense to me cause I am imagining the remainder when x is divided by n and then it would end up lying between every single pair of integers. So like for instance if I pick x=8.2 in mod n=3 that would make x=2.2 and then x=2.2, 2x= 1.4, and then if I chop it up mod 1 we'd end up with .2 and .4 and idk if this is making less sense or not but .2 < .333... so it works.

Answer 2

i dont buy it

Answer 3

what if n = inf

Answer 4

and x= pi

Answer 5

oh true if n =inf then uve convered all the digits , and there must basically an integer

Answer 6

cool

Answer 7

I feel like there's some algebra way to show this

Answer 8

I whittled it down to:
\[S=\{bx\}_{b=0}^{n-1}\]\[a \in S\]
\[\min\{|\lfloor a \rfloor - a| , |\lceil a \rceil - a| \} \le \frac{1}{n}\]

I dunno if that helps to see writen like this or not.

Answer 9

Proving it for \(x \in [0, 1)\) is sufficient as we're interested in only the fractional part. Additionally, it is trivial for \([0, 1/n]\) and \([(n-1)/n, 1]\), so we've got to think about the stuff that lies in between.

Answer 10

okau it is starting look a bit simpler

Answer 11

umm so lets consider the simpler cases, for example
some intger and .5
lets say 2.5....
for 0.5, n=2 is the best test,

in this case if u have a real number around 2.5 automatically its either 1/2 closer to the integer below or above it, this can be like the base case

Answer 12

now lets see the case above for n=3

Answer 13

now ur decimal value has to be split into 3 regits

Answer 14

regions*

Answer 15

2.0 to 2.33, 2.33 to 2.66, 2.66 to 2.99

Answer 16

I'm fairly positive that it's an application of some variant of the pigeonhole principle, since there are \(n-2\) holes and \(n-1\) pigeons. But that doesn't work.

Answer 17

as u can see once again atleast one of those decimal values will come closer again to less than 1/3 when multipled by 1,2

Answer 18

since its either on the edge or inbetween the region

Answer 19

i think thisi s a sufficient thing to prove by induction

Answer 20

ill work in it, but i feel like it makes sense to me, i dont wannnaa show it exactlllyyy T_T

Answer 21

oh ill show u for n regions okay

Answer 22

Hello past self :)
We prove this by contradiction. Suppose none of those numbers differs by at most \(1/n\) from an integer. Then all fractional parts lie in the region \((1/n, (n - 1)/n)\). This can be divided into \(n - 2\) intervals, where the \(i\)-th interval is \(i/n\) to \((i + 1) / n\). By Pigeonhole principle, two of those numbers lie in the same interval, say \(ax\) and \(bx\) (\(a < b)\). They differ by at most \(1/n\) since they're in the same interval, so \((a - b)x \le 1/ n\). But since \(a, b \in \{1, 2, \cdots, n - 1\} \Rightarrow a - b \in \{1, 2, \cdots, n - 1\}\), and so we have found a desired number.