Difference between revisions of "Floor function"
(expand) |
m |
||
| Line 1: | Line 1: | ||
The greatest integer function, also known as the '''floor function''', gives the greatest integer less than or equal to its argument. The floor of <math>x</math> is usually denoted by <math>\lfloor x \rfloor</math> or <math>[x]</math>. The action of this function is the same as "rounding down." On a [[positive]] argument, this function is the same as "dropping everything after the decimal point," but this is ''not'' true for negative values. | The greatest integer function, also known as the '''floor function''', gives the greatest integer less than or equal to its argument. The floor of <math>x</math> is usually denoted by <math>\lfloor x \rfloor</math> or <math>[x]</math>. The action of this function is the same as "rounding down." On a [[positive]] argument, this function is the same as "dropping everything after the decimal point," but this is ''not'' true for negative values. | ||
| + | |||
| + | == Properties == | ||
| + | * <math>[a+b]\ge [a]+[b]</math> for all real <math>(a,b)</math>. | ||
| + | * [[Hermite's Identity]]: <cmath>\left[a\right]+\left[a+\frac{1}{n}\right]+\ldots+\left[a+\frac{n-1}{n}\right] = [na]</cmath> | ||
| + | |||
==Examples== | ==Examples== | ||
| Line 17: | Line 22: | ||
where <math>\{x\}</math> is the fractional part of <math>x</math>. | where <math>\{x\}</math> is the fractional part of <math>x</math>. | ||
| + | |||
| + | == Olympiad Problems == | ||
| + | * [1981 USAMO #5] If <math>x</math> is a positive real number, and <math>n</math> is a positive integer, prove that | ||
| + | <cmath>[nx] > \frac{[x]}{1} + \frac{[2x]}{2} + \frac{[3x]}{3} + ... + \frac{[nx]}{n},</cmath> | ||
| + | where <math>[t]</math> denotes the greatest integer less than or equal to <math>t</math>. | ||
| + | |||
| + | [http://www.mathlinks.ro/viewtopic.php?t=174312 AoPS discussion 1] | ||
| + | |||
| + | [http://www.mathlinks.ro/viewtopic.php?t=101711 AoPS discussion 2] | ||
| + | |||
| + | * [1968 IMO #6] Let <math>[x]</math> denote the integer part of <math>x</math>, i.e., the greatest integer not exceeding <math>x</math>. If <math>n</math> is a positive integer, express as a simple function of <math>n</math> the sum <cmath>\left[\frac{n+1}{2}\right]+\left[\frac{n+2}{4}\right]+...+\left[\frac{n+2^k}{2^{k+1}}\right]+\ldots</cmath> | ||
| + | |||
==See Also== | ==See Also== | ||
*[[Ceiling function]] | *[[Ceiling function]] | ||
Revision as of 20:15, 9 March 2009
The greatest integer function, also known as the floor function, gives the greatest integer less than or equal to its argument. The floor of 
is usually denoted by 
or ![$[x]$](http://latex.artofproblemsolving.com/b/c/e/bceb7b14e55d33a8bca29b7863ad3cdae95afce4.png)
. The action of this function is the same as "rounding down." On a positive argument, this function is the same as "dropping everything after the decimal point," but this is not true for negative values.
Properties
![$[a+b]\ge [a]+[b]$](//latex.artofproblemsolving.com/e/6/b/e6b432a8bad3719a012a49b4e6a91528887c3522.png)
for all real 
.- Hermite's Identity:
![\[\left[a\right]+\left[a+\frac{1}{n}\right]+\ldots+\left[a+\frac{n-1}{n}\right] = [na]\]](//latex.artofproblemsolving.com/f/7/4/f74287048d257e37b47f631515da1b2071ce3c13.png)
![$[a+b]\ge [a]+[b]$](http://latex.artofproblemsolving.com/e/6/b/e6b432a8bad3719a012a49b4e6a91528887c3522.png)
for all real 
.![\[\left[a\right]+\left[a+\frac{1}{n}\right]+\ldots+\left[a+\frac{n-1}{n}\right] = [na]\]](http://latex.artofproblemsolving.com/f/7/4/f74287048d257e37b47f631515da1b2071ce3c13.png)
Examples
A useful way to use the floor function is to write 
, where y is an integer and k is the leftover stuff after the decimal point. This can greatly simplify many problems.
Alternate Definition
Another common definition of the floor function is
![\[\lfloor x \rfloor = x-\{x\}\]](http://latex.artofproblemsolving.com/f/0/8/f08050f59ce7fe0a9ca89436b6fc4bc457641904.png)
where 
is the fractional part of .
Olympiad Problems
- [1981 USAMO #5] If
is a positive real number, and 
is a positive integer, prove that
is a positive integer, prove that![\[[nx] > \frac{[x]}{1} + \frac{[2x]}{2} + \frac{[3x]}{3} + ... + \frac{[nx]}{n},\]](http://latex.artofproblemsolving.com/e/6/3/e638fb866f4cc5f83251ee225ac311b2dccfe8cd.png)
where ![$[t]$](http://latex.artofproblemsolving.com/8/a/8/8a86702dc60b9db916798b1115a6b6822bf828b9.png)
denotes the greatest integer less than or equal to 
.
- [1968 IMO #6] Let
![$[x]$](//latex.artofproblemsolving.com/b/c/e/bceb7b14e55d33a8bca29b7863ad3cdae95afce4.png)
denote the integer part of , i.e., the greatest integer not exceeding . If is a positive integer, express as a simple function of the sum ![\[\left[\frac{n+1}{2}\right]+\left[\frac{n+2}{4}\right]+...+\left[\frac{n+2^k}{2^{k+1}}\right]+\ldots\]](//latex.artofproblemsolving.com/6/b/a/6ba05e683d271bf4c948c7f9b9420f104be804e1.png)
![\[\left[\frac{n+1}{2}\right]+\left[\frac{n+2}{4}\right]+...+\left[\frac{n+2^k}{2^{k+1}}\right]+\ldots\]](http://latex.artofproblemsolving.com/6/b/a/6ba05e683d271bf4c948c7f9b9420f104be804e1.png)
