Maths Olympiad Prep

Library / /407 of 520

Number theory Difficulty 6.6 National olympiad Prove it

Theorem 1 Let x,yx, y be real numbers. We have
(i) If xyx \leqslant y, then [x][y][x] \leqslant[y].
(ii) If x=m+v,mx=m+v, m is an integer, 0v<10 \leqslant v<1, then m=[x],v={x}m=[x], v=\{x\}. In particular, when 0x<10 \leqslant x<1, [x]=0,{x}=x[x]=0,\{x\}=x.
(iii) For any integer mm, [x+m]=[x]+m,{x+m}={x}[x+m]=[x]+m,\{x+m\}=\{x\}. {x}\{x\} is a periodic function with period 1. The graphs of [x][x] and {x}\{x\} are shown in Figure 1 and Figure 2, respectively.
(iv) [x]+[y][x+y][x]+[y]+1[x]+[y] \leqslant[x+y] \leqslant[x]+[y]+1, where one and only one of the equalities holds.
(v) [x]={[x],xZ,[x]1,xZ[-x]=\left\{\begin{array}{ll}-[x], & x \in \mathbb{Z}, \\ -[x]-1, & x \notin \mathbb{Z}\end{array}\right. and
{x}={{x}=0,xZ1{x},xZ\{-x\}=\left\{\begin{array}{ll} -\{x\}=0, & x \in \mathbb{Z} \\ 1-\{x\}, & x \notin \mathbb{Z} \end{array}\right.
(vi) For a positive integer mm, [[x]m]=[xm]\left[\frac{[x]}{m}\right]=\left[\frac{x}{m}\right].
(vii) The smallest integer not less than xx (denoted as [x][x]) is [x]-[-x].
(viii) The largest integer less than xx is [x]1-[-x]-1.
(ix) The smallest integer greater than xx is [x]+1[x]+1.
(x) The integer closest to xx is [x+1/2][x+1 / 2] and [x+1/2]-[-x+1 / 2]. When x+1/2x+1 / 2 is an integer, these two different integers are equidistant from xx; when x+1/2x+1 / 2 is not an integer, they are equal. \square
(xi) If x0x \geqslant 0, then the number of positive integers nn not exceeding xx is equal to [x][x], i.e.,
1nx1=[x]\sum_{1 \leqslant n \leqslant x} 1=[x]
(xii) Let aa and NN be positive integers, then the number of positive integers among 1,2,,N1,2, \cdots, N that are divisible by aa is [N/a][N / a].

Solution

(i) It follows from [x]xy<[y]+1[x] \leqslant x \leqslant y<[y]+1.
(ii) It follows from mx<m+1m \leqslant x < m+1 and the definition. This property is a commonly used technique when proving properties related to [x][x].
(iii) It follows from [x]+mx+m<([x]+m)+1[x]+m \leqslant x+m<([x]+m)+1 and the definition.
(iv) x+y=[x]+[y]+{x}+{y}x+y=[x]+[y]+\{x\}+\{y\} and 0{x}+{y}<20 \leqslant\{x\}+\{y\}<2. When 0{x}+{y}<10 \leqslant\{x\}+\{y\}<1, by (ii) we know [x+y]=[x]+[y][x+y]=[x]+[y]; when 1{x}+{y}<21 \leqslant\{x\}+\{y\}<2,
x+y=[x]+[y]+1+({x}+{y}1),x+y=[x]+[y]+1+(\{x\}+\{y\}-1),

By (ii) we know
[x+y]=[x]+[y]+1[x+y]=[x]+[y]+1
(v) It is obviously true when xx is an integer. When xx is not an integer, x=[x]{x}=-x=-[x]-\{x\}= [x]1+1{x},0<1{x}<1-[x]-1+1-\{x\}, 0<1-\{x\}<1, by (ii) we know the conclusion holds.
(vi) By the division algorithm, there exist integers q,rq, r, such that
[x]=qm+r,0r<m[x]/m=q+r/m,0r/m<1\begin{aligned} {[x] } & =q m+r, \quad 0 \leqslant r<m \\ {[x] / m } & =q+r / m, \quad 0 \leqslant r / m<1 \end{aligned}

From this and (ii), we deduce [[x]/m]=q[[x] / m]=q. On the other hand,
x/m=[x]/m+{x}/m=q+({x}+r)/mx / m=[x] / m+\{x\} / m=q+(\{x\}+r) / m

Noting that 0({x}+r)/m<10 \leqslant(\{x\}+r) / m<1, from this and (ii) we deduce [x/m]=q[x / m]=q. Therefore, (vi) holds.
(vii) Let the smallest integer not less than xx be aa, i.e., a1<xaa-1<x \leqslant a. Therefore, ax<a+1-a \leqslant -x<-a+1, so a=[x]-a=[-x], i.e., a=[x]a=-[-x].
(viii) and (ix) are left to the reader, using the same method as (vii).
(x) The integer closest to xx must be among [x][x] and [x]+1[x]+1. When x+1/2x+1 / 2 is an integer, these two numbers are equidistant from xx. It is easy to verify that [x]+1=[x+1/2][x]+1=[x+1 / 2] and [x]=[x]= [x1/2]=[x+1/2][x-1 / 2]=-[-x+1 / 2]. When x+1/2x+1 / 2 is not an integer, if {x}<1/2\{x\}<1 / 2, the integer closest to xx is [x][x]. Since x+1/2=[x]+{x}+1/2,0{x}+1/2<1x+1 / 2=[x]+\{x\}+1 / 2,0 \leqslant\{x\}+1 / 2<1, by (ii) we know [x]=[x+1/2][x]=[x+1 / 2]; if 1/2<{x}<11 / 2<\{x\}<1, the integer closest to xx is [x]+1[x]+1. Since x+1/2=[x]+1+{x}1/2,0<{x}1/2<1x+1 / 2=[x]+1+\{x\}-1 / 2,0<\{x\}-1 / 2<1, by (ii) we know [x]+1=[x+1/2][x]+1=[x+1 / 2]. When x+1/2x+1 / 2 is not an integer, by (v) we know
[x+1/2]=[x1/2]1=[x+1/21]1=[x+1/2]\begin{aligned} {[x+1 / 2] } & =-[-x-1 / 2]-1 \\ & =-[-x+1 / 2-1]-1=-[-x+1 / 2] \end{aligned}

The last step uses (iii). Proof completed.
(xi) Since the integer nxn \leqslant x is n[x]n \leqslant[x], it holds.
(xii) The positive integers divisible by aa are a,2a,3a,a, 2 a, 3 a, \cdots. Suppose the number of positive integers divisible by aa in 1,2,,N1,2, \cdots, N is kk, then there must be kaN<(k+1)ak a \leqslant N<(k+1) a, i.e., kN/a<k+1k \leqslant N / a<k+1, so it holds.

The symbol [x][x] is very useful. Here is an example.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.