a nice floor problem from the IMO long list. 

Before coming across this channel, I thought the floor function was rather boring ...

I solved it by calling the starting expression M, which is an integer. I moved the n over and we can get rid of the floor function by saying M-n+e = sqrt(n)+1/2 for some e in the interval [0,1). Rearranging: e-1/2 = sqrt(n)+n-M, Since e is in [0,1), then e-1/2 is in [-1/2,1/2), and the right hand side must also be in that interval. Assume M has no solution for n, then there should be no integer n which makes sqrt(n)+n-M fall in [-1/2,1/2). In other words we must have some special n=N, such that: sqrt(N)+N-M < -1/2 AND 1/2 ≤ sqrt(N+1)+N+1-M, rearanging: sqrt(N) < M-N-1/2 AND M-N-1/2 ≤ sqrt(N+1), combining the two inequalities and squaring (which is fine since the smallest part of the inequality, sqrt(N), is positive so all the quantities are positive): N < M^2-2MN+N^2-M+N+1/4 ≤ N+1, Subtracting N and 1/4 gives: -1/4 < M^2-2MN+N^2-M ≤ 3/4. Note that the center quantity is an integer, and the only integer satisfying the inequality is 0. Thus: M^2-2MN+N^2-M = (M-N)^2-M = 0 (M-N)^2=M. so M is a perfect square. Thus M having no solution implies M is a perfect square.

18:45 Classic floor function. I rate this video ⌊9.999…⌋ / 10

For anyone else who was confused about why f(n) was strictly less than m^2 in this proof, the reason why this holds is because the argument of the floor function after adding 1 under the radical is exactly an integer. Since this is exactly an integer, any smaller input into the floor function will necessarily lead to a smaller output of the floor function, justifying the strict inequality.

I solved this fairly straight forward suppose floor(sqrt(n)+1/2)=k, k>=0 k+1 > sqrt(n)+1/2 >=k k+1/2 > sqrt(n) >= k-1/2 k^2+k+1/4 > n > k^2-k+1/4 k^2+k > n-1/4 >= k^2-k notice that n, k are natural numbers k^2+k >= n >= k^2-k+1 This means for any natural number k, when k^2+k >=n >= k^2-k+1, floor(sqrt(n)+1/2)=k, so in this range, original expression is n+k , will not skip any number between k^2+1 and k^2+2k (inclusive) put k+1 into the range above to see k^2+2k+1 will not be reached. Notice that k^2+k+1 = (k+1)^2 - (k+1) +1, hence all n are covered. (k+1)^2, k>=0 are all the numbers not in the form of n + floor(sqrt(n)+1/2)

I'm surprised such an easy problem was even considered for the IMO. I'm definitely nowhere near IMO-level in ability, but it's pretty easy to see what to do here. I would go for a much more direct proof. The first thing to notice is that sqrt(n + 1) - sqrt(n) < 1 for all positive integers n. That means that the difference between sqrt(n) + 1/2 and sqrt(n + 1) + 1/2 is less than 1, meaning that the difference of their floors is either 0 or 1. Let K(n) = floor(sqrt(n) + 1/2). Either K(n + 1) = K(n) or K(n + 1) = K(n) + 1. That means that f(n) = n + K(n), and either f(n + 1) = n + 1 + K(n), the next number, or f(n + 1) = n + 1 + K(n) + 1 = n + 2 + K(n), which skips the number n + 1 + K(n). So if we can find the n for which K(n + 1) = K(n) + 1, we can find the skipped values: n + 1 + K(n). For that, we need sqrt(n) + 1/2 to be less than some integer boundary but sqrt(n + 1) + 1/2 to be greater than or equal to that same integer boundary. Let that integer boundary be z. Then sqrt(n) + 1/2 < z while sqrt(n + 1) + 1/2 ≥ z. (Actually, it has to be > z since a half-integer can't be the square root of an integer, but anyway.) From the first inequality, sqrt(n) < z - 1/2, but since everything here is positive, we can square both sides to get n < (z - 1/2)^(2). From the second, we similarly get n ≥ (z - 1/2)^(2) - 1. Combining them, (z - 1/2)^(2) - 1 ≤ n < (z - 1/2)^(2). Since n is an integer, it's inside a range of 1, and (z - 1/2)^2 is not an integer, we can see that n = floor((z - 1/2)^(2)), in other words, n is the squares of the half-integers, rounded down. That would be floor(1.5^(2)) = 2, floor(2.5^(2)) = 6, floor(3.5^(2)) = 12, etc. Remember how we got this, though: we needed sqrt(n) + 1/2 < z but sqrt(n + 1) + 1/2 ≥ z. So K(n + 1) = z and K(n) = z - 1. Therefore, the skipped values are n + 1 + K(n) = floor((z - 1/2)^(2)) + z. All that remains is to simplify that expression. floor((z - 1/2)^(2)) = floor(z^2 - z + 1/4) = z^2 - z, so the skipped values are z^2 - z + z = z^(2).

Great stuff, but there was some guessing/intuition involved, and the following might help to build that intuition: if we examine the floor part only - g(n) = floor(sqrt(n) + 1/2) - and look at it as sequence, we get the following: 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, ... In other words, we get each value n exactly 2n times in a row, and then it increases by 1 (which of course can be proven). From this we can conclude that the increasing always happens directly *after* index m^2 + m, so after index 2, 6, 12, 20, ... Our actual function f adds the linear term n to g, so within those ranges of equal results of g we get all numbers in some intervals, and we now only have to check what happens at the indices m^2 + m and m^2 + m + 1 to find out which numbers we are missing.

Jesus. Solving differential equations is easier than this number theory stuff 😵‍💫

I got there by focusing on when \sqrt{n} < k + 1/2 < \sqrt{n+1} - squaring across, we get n < k^2+k+1/4 < n+1 - which gives the same result - numbers get skipped for f(n) when n goes from k^2 + k to k^2 + k + 1 - and f(k^2+k) = k^2+2k (since \sqrt{k^2+k} < k + 1/2) f(k^2+k+1) = k^2+2k+2 (since \sqrt{k^2+k+1}>k+1/2) - so f(n) skips all values of the form k^2+2k+1 = (k+1)^2

overcomplicated solution. I did this in less than 10 minutes with following reasoning: 1. notice that f is strictly increasing, either increasing by 1 or by 2. Our goal is to find when our function jumps by 2, so we will know what numbers in image will be missing. 2. Each natural number can be written uniquely as n=k^2 +r, where r=0,1,...,2k 3. "Jump" will happen for the smallest r such that sqrt(k^2+r)>=k+1/2 4.Squaring it gives us r>=k+1/4, since r is integer, the smallest r we search for is k+1 5. So jump will happen from n=k^2+k to n=k^2+k+1. We find that f(k^2+k)=k^2+2k, f(k^2+k+1)=k^2+2k+2, so the numers missing in image are in form k^2+2k+1=(k+1)^2.

Always waiting for your videos :)

Really great exercise

Consider f(x)=[√x+½] Clearly this function increases by 1 exactly when x=(k-½)² for k in |N and is otherwise constant. Also, f(n+1) ≤ f(n)+1. Therefore n+[√n+½] increases by 1 when f(n) = f(n-1), and by 2 (leaving a gap) when f(n)=f(n-1)+1, that is, when n-1 < (k-½)² ≤ n for some k, so n = ceil((k-½)²). The gaps are then at n+f(n)-1. Note that f(n) = f((k-½)²) = k, so the gaps are at n+k-1 = ceil((k-½)²)+k-1 = ceil((k-½)² + k - 1) = ceil(k² - k + ¼ + k - 1) = ceil(k² - ¾) = k².

Nice problem! Partition the range of f into non overlapping intervals and prove that in each interval f hits all possible numbers except for one. That exception is exactly the perfect square in that same interval. So it has to hit all the other numbers.

At 14:30 : It's only strictly larger because the square root of (4m^2 + 4m + 1) is always _odd_ for natural values of m. If the square root of (4m^2 + 4m + 1) could be an even number, then floor(0.5*sqrt(4m^2 + 4m) + 0.5) could be _equal_ to floor(0.5*sqrt(4m^2 + 4m + 1) + 0.5) . You skipped this observation to prove that the "strictly less than" holds.

See Lambek & Moser: Inverse and complementary sequences of natural numbers, Am. Math Monthly Vol 61, No. 7 (1954), pp 454-458.

I started by assuming that a number might be skipped if sqrt(n)=m+1/2. because the first case would give n+m, and the second would give n+1+m+1, so the value n+m+1 is skipped. so n would need to be floor((m+1/2)^2)=m^2+m in this case. Then the two value are f(n)=m^2+m+m and f(n+1)=m^2+m+1+m+1 the skipped value is m^2+2m+1=(m+1)^2 Then all that's left is to show that those are the only solutions.

You really just need to find out at what values of n, the value of `sqrt(n) mod 1` crosses 0.5. That is, sqrt(n) = k+0.5 for any non-negative integer k. Therefore n = (k+0.5)^2 = k^2 + k + 0.25 Since k is an integer, the switch happens between n = (k^2 + k) and n+1 = (k^2 + k + 1), i.e. the value jumps from n+k to (n+1)+(k+1) = n+k+2 That is, the values n+k+1 = k^2+k+k+1 = k^2+2k+1 = (k+1)^2 get skipped in the output of the function for any non-negative integer k (i.e. all the perfect squares).

This is beautiful

Michael, why do you hate the perfect squares?

Why are the possible values that a function can take its lower bound minus its upper bound plus one? He introduces this at ~ 9:00

Wow, long listed. What's long listed mean?

We can use induction?

When were other numbers which were not perfect squares shown to be in the image of f(n)? Edit: nvm, it was shown about 6:30, if you evaluate between two perfect squares, you map to entire range of numbers in between except one. And also @12:00.

I don't get why you set n=m(m-1). Yes, you prove that f(n) can't be m^2 in THAT case, but how can you be sure there aren't other possible cases? @MichaelPennMath

💚🤍❤️

Posted this 17s after the video landed.