Greatest Integer Function

Contest writers LOVE the greatest integer function (or GIF for short, although I've never seen it written like that, but I'll be calling it that from now on. Also, the problem will denote whether I'm refering to the floor or the ceiling version). Why do they love it so much? It's certainly not as curvy as its related fractional part function, if you know what I mean. But mostly because it's an odd function, and if you aren't familiar with it / have the creativity to know how to mess around with it to get an idea on how it is used in the problem, then you won't have much luck with that problem.

How many of the first 1000 positive integers can be expressed in the form:



where x is a non-negative real number?


Hm, where to begin? First off, you should note a few things about gif. For when the expression inside of the function is an integer, then it's equivalent to there being no floor function at all. Also, if it is in the form where n is an integer, then it is equivalent to . I'm not sure how to formally prove it, but its basically because the "floor" of the number cuts off the fractional part, so if you think of the number geometrically, you can cut off an integral length from the number, floor it, then reattach it. By no means a rigorous proof. =)

Another interesting thing about the floor function is the way it suddenly jumps from one integer to the next. In other words, if we call it f(x), and n is an integer, then



Anyway, back to the problem, we have multiplication inside of the function. All that means is that specific function advances quicker than the others, if you know what I mean (you can relate this to your study of the trig functions, such as the graph of sin(2x)). However, it turns out to be an important part of the problem, since we are adding several of these together.

For the sake of the problem, define a new function f(x) := that whole expression the problem gives (I'm not retyping it, latex needs to invent an easier way to do the floor function). f(0) = 0, and f(1) = 20 . We need to figure out what values it can take on inbetween x=0 and x=1. Once we do that, we can generalize up to f(50) = 1000.

To determine when f(x) jumps values, you have to consider when each individual part jumps values. Since I know you wont, I'll do it for you (I'm not doing latex for the fractions, it's too tedious):



1/2, 1


1/4 , 1/2 , 3/4 , 1


1/6, 1/3, 1/2, 2/3, 5/6, 1


1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8, 1

Now we can analyze how f(x) behaves. Consider f(1/8). Clearly, the last part of the function jumps up to 1, but the rest dont, so f(1/8) = 1. But what about 1/4? The floor of 8x jumps up, but so does the floor of 4x!, meaning we get 0 + 1 + 0 + 2 = 3. Likewise, when these "jumps" are shared by multiple parts, the function skips integers. For example, when a value is shared by n of them, then from the previous attainable value, it goes up by n, skipping n-1 of the integers in between

1/4 - shared by 2, 1 integer is skipped
1/2 - shared by 4, 3 integers are skipped
3/4 - shared by 2, 1 integer is skipped
1 - shared by 4, 3 integers are skipped

From this, we can conclude that for positive numbers not greater than 1, f(x) takes on 12 distinct values, seeing as there are 20 possible values, and 8 of them are skipped. We can generalize this for all values of x, using the property previously mentioned, to determine what values are skipped. In other words, for every 20 integers, only 12 of them are representable in the desired form. It's not coincidence that 1000 is a multiple of 20. Our final answer is thus:



Oomph. So how are you doing? Yesterday I stayed up till 6, and still couldn't sleep, so became reduced to watching reality tv shows of retired musicians on MTV. It was a good time. Tonight I'll try to go to bed earlier though.