5

Prove that if $a$ is real and $n$ natural. The distance between one of the numbers $a,2a,3a,...,na$ and a whole number is at most $\frac{1}{n}$.

This is a problem from discrete math, but hints from analysis would be appreciated.

yolo expectz
  • 363
  • 2
  • 13
  • 1
    I haven’t worked out an answer to this but my guess is that you would begin by writing $a = [a]+{a}$ where $[a]$ is the greatest integer less than or equal to $a$ and ${a}$ is the fractional part of $a$. From there, you could of multiples of the fractional parts and probably use the pigeonhole principle. Just an idea to get started at the very least. I’ll think more about it though. – user328442 Nov 17 '17 at 14:19
  • 1
    An answer to this question can be found here. See example 6 in the link. http://www.math.lsa.umich.edu/~hderksen/ProblemSolving/PS7.pdf – user328442 Nov 17 '17 at 14:23
  • http://mathworld.wolfram.com/NaturalNumber.html If you include 0 in the set of natural numbers then when a=0.1 and n=1 the maximum distance for this case is $\frac{1}{2n}$. – James Arathoon Nov 17 '17 at 14:24
  • Am I being thick. If $a=1.1$ and $n=10^m$; m being a positive non zero integer. The closest you can get to an integer is 0.1 and this is independent of the size of n as defined above. – James Arathoon Nov 17 '17 at 15:04
  • @JamesArathoon When $m = 1$ we have $1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9, 11$, and $11$ has distance $0$ from a whole number. – orlp Nov 17 '17 at 15:06
  • That's what I thought, I am being thick. – James Arathoon Nov 17 '17 at 15:08

2 Answers2

2

Any real $a$ can be written as $a=\lfloor a\rfloor+\{a\}$, where $\lfloor \cdot\rfloor$ is the greatest integer function and $\{a\}$ is the fraction part of $a$. Now note that $\{a\}\in[0,1)$ for any $a\in\mathbb{R}$. Partition the interval $[0,1)$ into $A_1,\cdots,A_n$ where $A_k=\left[\frac{k-1}{n},\frac{k}{n}\right)$ for $k\in\{1,\cdots,n\}$. Now $\{a\}$ must belong to one of these subintervals, say $A_i$. Then $\{xa\}\in\left[0,\frac{xi~mod~n}{n}\right)$. Now $\mathbb{Z}_n^*$, the nonzero elements of integers modulo $n$, is a multiplicative group. Hence for every integer $i\leq n,\exists~ x\leq n$ such that $xi\equiv1\mod n$. That is for some $x\leq n$, $xa$ is within a distance of $\frac{1}{n}$ from the integer $\lfloor x a\rfloor$ .

QED
  • 12,644
0

For the analysis intuition:

This is actually an interesting question of looking at the circle - $S^1$ and an angle $\theta$ and asking to prove that one of $\theta,\ ...,\ n\theta$ is close to $0$ by $\frac{1}{n}$.

To understand what I said above just look at everything mod $1$. I think now you can visualise why the statement is correct.

For the proof:

To prove that just divide to cases:

  1. $\theta \in [0,\frac{2\pi}{n}]$.
  2. $\theta \in [\frac{2\pi}{n},2\frac{2\pi}{n}]$.

. . .

k. $\theta \in [(k-1)\frac{2\pi}{n},k\frac{2\pi}{n}]$.

. . .

n. $\theta \in [(n-1)\frac{2\pi}{n},n\frac{2\pi}{n}]$.

And from here it's quite easy.

If I'm wrong feel free to brutally scold me.

Shaked
  • 316