Difference between revisions of "Floor function"
Cubealgo15 (talk | contribs) m (→Olympiad Problems) |
|||
| (28 intermediate revisions by 11 users not shown) | |||
| Line 1: | Line 1: | ||
| − | The greatest integer function, | + | 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>\lfloor a+b\rfloor\ge \lfloor a\rfloor+\lfloor b \rfloor</math> for all real <math>(a,b)</math>. | ||
| + | * [[Hermite's Identity]]: <cmath>\lfloor na\rfloor = \left\lfloor a\right\rfloor+\left\lfloor a+\frac{1}{n}\right\rfloor+\ldots+\left\lfloor a+\frac{n-1}{n}\right\rfloor</cmath> | ||
| + | |||
| + | ==Examples== | ||
*<math>\lfloor 3.14 \rfloor = 3</math> | *<math>\lfloor 3.14 \rfloor = 3</math> | ||
| − | *<math>\lfloor -2.7 \ | + | *<math>\lfloor 5 \rfloor = 5</math> |
| + | |||
| + | *<math>\lfloor -3.2 \rfloor = -4</math> | ||
| + | |||
| + | A useful way to use the floor function is to write <math>\lfloor x \rfloor=\lfloor y+k \rfloor</math>, 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 | ||
| + | |||
| + | <cmath>\lfloor x \rfloor = x-\{x\}</cmath> | ||
| + | |||
| + | where <math>\{x\}</math> is the fractional part of <math>x</math>. | ||
| + | |||
| + | == Problems == | ||
| + | === Introductory Problems === | ||
| + | * Let <math>[x]</math> denote the largest integer not exceeding <math>x</math>. For example, <math>[2.1]=2</math>, <math>[4]=4</math> and <math>[5.7]=5</math>. How many positive integers <math>n</math> satisfy the equation <math>\left[\frac{n}{5}\right]=\frac{n}{6}</math>. | ||
| + | (2017 PCIMC) | ||
| + | |||
| + | ===Intermediate Problems === | ||
| + | * Find the integer <math>n</math> satisfying <math>\left[\frac{n}{1!}\right]+\left[\frac{n}{2!}\right]+...+\left[\frac{n}{10!}\right]=1999</math>. Here <math>[x]</math> denotes the greatest integer less than or equal to <math>x</math>. | ||
| + | (1999-2000 Hong Kong IMO Prelim) | ||
| + | * What is the units (i.e., rightmost) digit of | ||
| + | <cmath>\left\lfloor \frac{10^{20000}}{10^{100}+3}\right\rfloor</cmath> | ||
| + | (1986 Putnam Exam, A-2) | ||
| + | * How many of the first 1000 [[positive integer]]s can be expressed in the form | ||
| − | + | <math>\lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 6x \rfloor + \lfloor 8x \rfloor</math>, | |
| + | |||
| + | where <math>x</math> is a [[real number]], and <math>\lfloor z \rfloor</math> denotes the greatest [[integer]] less than or equal to <math>z</math>? | ||
| + | |||
| + | [[1985 AIME Problems/Problem 10|(1985 AIME)]] | ||
| + | |||
| + | === Olympiad Problems === | ||
| + | * If <math>x</math> is a positive real number, and <math>n</math> is a positive integer, prove that | ||
| + | <cmath>[nx] \geq \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>. | ||
| + | |||
| + | (1981 USAMO, #5) ([http://www.mathlinks.ro/viewtopic.php?t=174312 Discussion 1]) ([http://www.mathlinks.ro/viewtopic.php?t=101711 Discussion 2]) | ||
| + | |||
| + | * 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> | ||
| + | (1968 IMO, #6) | ||
==See Also== | ==See Also== | ||
| − | *[[ | + | *[[Ceiling function]] |
| + | |||
| + | *[[Fractional part]] | ||
| + | |||
| + | [[Category:Functions]] | ||
Latest revision as of 20:05, 26 February 2024
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.
Contents
Properties
for all real 
.- Hermite's Identity:
![\[\lfloor na\rfloor = \left\lfloor a\right\rfloor+\left\lfloor a+\frac{1}{n}\right\rfloor+\ldots+\left\lfloor a+\frac{n-1}{n}\right\rfloor\]](//latex.artofproblemsolving.com/8/4/d/84ddeb9332a5aedd6606f0b8711d40bd60fecc9e.png)
for all real 
.![\[\lfloor na\rfloor = \left\lfloor a\right\rfloor+\left\lfloor a+\frac{1}{n}\right\rfloor+\ldots+\left\lfloor a+\frac{n-1}{n}\right\rfloor\]](http://latex.artofproblemsolving.com/8/4/d/84ddeb9332a5aedd6606f0b8711d40bd60fecc9e.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 .
Problems
Introductory Problems
- Let
![$[x]$](//latex.artofproblemsolving.com/b/c/e/bceb7b14e55d33a8bca29b7863ad3cdae95afce4.png)
denote the largest integer not exceeding 
. For example, ![$[2.1]=2$](//latex.artofproblemsolving.com/8/4/5/845a60595be566ae18cc6ab4335a3229209eec59.png)
, ![$[4]=4$](//latex.artofproblemsolving.com/3/b/c/3bcdeec719a406f28bd765d6cb61d4b6af47f7bf.png)
and ![$[5.7]=5$](//latex.artofproblemsolving.com/2/4/d/24dc8bc3d862f61f4b7f4955a2553dd72c752ff1.png)
. How many positive integers 
satisfy the equation ![$\left[\frac{n}{5}\right]=\frac{n}{6}$](//latex.artofproblemsolving.com/5/6/1/561c423e60a1a773205ba852a4c3d74f297bd5a3.png)
.
![$[2.1]=2$](http://latex.artofproblemsolving.com/8/4/5/845a60595be566ae18cc6ab4335a3229209eec59.png)
, ![$[4]=4$](http://latex.artofproblemsolving.com/3/b/c/3bcdeec719a406f28bd765d6cb61d4b6af47f7bf.png)
and ![$[5.7]=5$](http://latex.artofproblemsolving.com/2/4/d/24dc8bc3d862f61f4b7f4955a2553dd72c752ff1.png)
. How many positive integers 
satisfy the equation ![$\left[\frac{n}{5}\right]=\frac{n}{6}$](http://latex.artofproblemsolving.com/5/6/1/561c423e60a1a773205ba852a4c3d74f297bd5a3.png)
.(2017 PCIMC)
Intermediate Problems
- Find the integer satisfying
![$\left[\frac{n}{1!}\right]+\left[\frac{n}{2!}\right]+...+\left[\frac{n}{10!}\right]=1999$](//latex.artofproblemsolving.com/c/c/d/ccd9d2e757785d313225dddf2953e096aace4141.png)
. Here denotes the greatest integer less than or equal to .
![$\left[\frac{n}{1!}\right]+\left[\frac{n}{2!}\right]+...+\left[\frac{n}{10!}\right]=1999$](http://latex.artofproblemsolving.com/c/c/d/ccd9d2e757785d313225dddf2953e096aace4141.png)
. Here (1999-2000 Hong Kong IMO Prelim)
- What is the units (i.e., rightmost) digit of
![\[\left\lfloor \frac{10^{20000}}{10^{100}+3}\right\rfloor\]](http://latex.artofproblemsolving.com/5/7/7/5772238264c864988b56a785810ea6b0934e6b4f.png)
(1986 Putnam Exam, A-2)
- How many of the first 1000 positive integers can be expressed in the form
,
where is a real number, and 
denotes the greatest integer less than or equal to 
?
Olympiad Problems
- If is a positive real number, and is a positive integer, prove that
![\[[nx] \geq \frac{[x]}{1} + \frac{[2x]}{2} + \frac{[3x]}{3} + ... + \frac{[nx]}{n},\]](http://latex.artofproblemsolving.com/5/2/c/52c05af83d2354182afba4ce3f78434072f5944d.png)
where ![$[t]$](http://latex.artofproblemsolving.com/8/a/8/8a86702dc60b9db916798b1115a6b6822bf828b9.png)
denotes the greatest integer less than or equal to 
.
(1981 USAMO, #5) (Discussion 1) (Discussion 2)
- Let 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)
(1968 IMO, #6)
