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.
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)
Or you could just try proving its properties on wikipedia & find any discrete math/number theory books that cover it (Concrete mathematics,Titu's 104 number theory problems, Titu's functional equation book, etc)
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.
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.
@@maddenbanh8033 it's not a case of convergence. The limit's already been taken. Now we're computationally evaluating it to be 10/10. Which is useful, because every finite step of the sequence ⌊9.99...9⌋/10=9/10.
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
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).
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².
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.
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.
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.
number of integers between n and m(including both end-points, n≤m) is n-m+1 because when you susbtract by m, the number "m" is also excluded m=|{1,2,...,m}| n=|{1,2,...,n}| m-n=|{n+1,n+2,...,m}| m-n+1=|{n,n+1,...,m}|
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.
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.
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).
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
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.
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)
Before coming across this channel, I thought the floor function was rather boring ...
I use a lot of floor in graph labelling
Or you could just try proving its properties on wikipedia & find any discrete math/number theory books that cover it (Concrete mathematics,Titu's 104 number theory problems, Titu's functional equation book, etc)
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.
thank you
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.
Titu's 104 number theory problems explored it concisely
18:45 Classic floor function. I rate this video ⌊9.999…⌋ / 10
Naughty.
I mean... Doesn't that technically converge to 10
@@maddenbanh8033 it's not a case of convergence. The limit's already been taken. Now we're computationally evaluating it to be 10/10.
Which is useful, because every finite step of the sequence ⌊9.99...9⌋/10=9/10.
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
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).
Nicely explained, this is more or less how I solved it too.
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².
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.
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.
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.
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
Those aren't the possible values, just the possible number of values. Like between 4 and 9 there is 9-4+1 values, 4,5,6,7,8,9
@@natevanderw Makes much more sense, thank you
number of integers between n and m(including both end-points, n≤m) is n-m+1 because
when you susbtract by m, the number "m" is also excluded
m=|{1,2,...,m}|
n=|{1,2,...,n}|
m-n=|{n+1,n+2,...,m}|
m-n+1=|{n,n+1,...,m}|
Really great exercise
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.
Ywnbaw
See Lambek & Moser: Inverse and complementary sequences of natural numbers, Am. Math Monthly Vol 61, No. 7 (1954), pp 454-458.
Michael, why do you hate the perfect squares?
Always waiting for your videos :)
Jesus. Solving differential equations is easier than this number theory stuff 😵💫
Linear ODE, maybe, but good luck if the diff eq is not linear or not seperable
We can use induction?
No
Wow, long listed. What's long listed mean?
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.
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
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
He's shown that f is increasing, so if he shows that f(n)
Posted this 17s after the video landed.