Editorialist: Anubhav Dhar
Problem Link: ZIO 2020 Problem 4
Prerequisites: Basic-mathematics
Problem Statement in short :
Find the number of distinct integers in \{floor (N/1), floor (N/2), floor (N/3), \dots, floor(N/N)\}, for N = 38, 146 and 2808.
Quick Explanation:
In the sequence \{floor (N/1), floor (N/2), floor (N/3), \dots , floor (N/N)\}, there will be a point before which all values are distinct and after which repetition might occur, in which case, all the values occurring after that position will just be a decreasing sequence of consecutive integers ending at 1 with some possible repetitions. In other words for any N, in the set \{floor (N/1), floor (N/2), floor (N/3), \dots , floor (N/N)\}, we can always find an integer i, 1 < i ≤ N, such that all elements in set \{floor (N/1), floor (N/2), floor (N/3), \dots , floor (N/(i-1))\} are distinct, whereas in the set \{floor (N/i),\dots, floor (N/N)\} it is guaranteed that ALL the natural numbers in \{1, 2, 3, \dots floor(N/i)\} occur at least once, i.e. the number of distinct elements in \{floor (N/i),\dots , floor (N/N)\} is the size of the set \{1, 2, 3, … , floor(N/i)\}, which is floor(N/i). We solve for such i, and finally calculate the required answer.
Explanation:
In many problems, like this one, it is often a good idea to just try out some examples for small enough values of N. So for this, we may choose N = 10, and write down all the relevant fractions before taking their floor. Creating the set for N = 10, we get
\{(10/1), (10/2), (10/3), (10/4), (10/5), (10/6), (10/7), (10/8), (10/9), (10/10)\}
= \{10, 5, 3.33, 2.5, 2, 1.67, 1.43, 1.25, 1.11, 1\}
These values are obviously in a decreasing order. Now one might observe that the values at the beginning of the set are all far apart and they tend to “fall” at a much higher rate. In other words, two consecutive values somewhere in the beginning differ by a lot, whereas the values near the end of the set are somewhat closer and “fall” slowly.
Now we should try to come up with a rigorous proof of what we observed.
So we want to prove that two consecutive values differ more in the beginning than in the end. Precisely we just want to prove that \frac Ni- \frac N{i+1}> \frac Nj- \frac N{j+1}, if i < j.
The proof:-
i < j
\implies i+1 < j+1
\implies i(i+1) < j(j+1)
\implies \frac 1{i(i+1)}> \frac 1{j(j+1)}
\implies \frac {(i+1) - i}{i(i+1)}> \frac {(j+1) - j}{j(j+1)}
\implies \frac 1i - \frac 1{i + 1}> \frac 1j- \frac 1{j +1}
\implies \frac Ni- \frac N{i + 1}> \frac Nj- \frac N{j + 1} (Proved)
Sidenote: It is almost intuitive from the graph of 1/x.
Now, we know that apart from the fact that the values in this set in a decreasing order, the difference of two consecutive values also decreases.
Now, we will get to the three main observations:-
- Observation 1 : If \frac Ni- \frac N{i + 1}< 1 then we either have floor(N/i) = floor (N/(i+1)) or floor(N/i) = floor(N/(i+1)) + 1. Since \frac Ni- \frac N{i + 1}< 1, the difference between floor(N/i) and floor(N/(i+1)) can never exceed 1. Also if \frac Ni- \frac N{i + 1} \ge 1, it is guaranteed that floor(N/i) \ne floor(N/(i+1)), precisely floor(N/i) > floor(N/(i+1)).
- Observation 2 : If we increase i from 2 to N-1, at some point \frac Ni- \frac N{i + 1} will be less than 1, whereas \frac N{i-1}- \frac Ni will be greater than or equal to 1 (Since difference of consecutive fractions decreases) . So, only “after” a certain point, there is a possibility of repetition in the sequence \{floor (N/1), floor (N/2), floor (N/3),\dots , floor (N/N)\}.
- Observation 3 :Now if we denote the value of i for which \frac Ni- \frac N{i + 1} < 1, whereas \frac N{i-1}- \frac Ni \ge 1 by k, then all the values in \{floor (N/1), floor (N/2), floor (N/3),\dots , floor (N/(k-1))\} are distinct (because the difference between any two consecutive fractions is greater than or equal to 1, so they cannot have the same floor) and all the values in \{floor(N/k), floor (N/(k+1)), floor (N/(k+2)),\dots , floor(N/N)\} belong to the set of integers \{1, 2, \dots , floor(N/k)\}, with each value in \{1, 2,\dots, floor(N/k)\} guaranteed to occur at least once, i.e. the sequence \{floor(N/k), floor(N/(k+1)), floor(N/(k+2)),\dots ,floor(N/N)\} is just \{floor(N/k), … , 2, 1\} with some repetitions (since from Observation 1 we know that floor(N/i) - floor(N/(i+1)) can be at most 1, for i \ge k, so there cannot possibly be any integer h, with floor(N/i) > h > floor(N/(i+1)). Now for the sake of contraction we assume h to be a value in \{1, 2,\dots, floor(N/k)\} which didn’t occur in \{floor(N/k), floor(N/(k+1)), floor (N/(k+2)), \dots , floor(N/N)\} then we must be having floor(N/j) > h > floor(N/(j+1)) for some j > k, which we just proved to be impossible). In other words the set \{floor(N/k), floor (N/(k+1)), floor (N/(k+2)), …, floor(N/N)\} contain all consecutive integers from floor(N/k) to 1.
Now we need to solve for k, which was defined to be the value of i for which \frac Ni- \frac N{i + 1} < 1, and \frac N{i-1}- \frac Ni \ge 1. Rewriting \frac Ni-\frac N{i + 1} < 1, we get
\frac {N \{ (i+1)-i \} }{i (i + 1)} < 1
\implies \frac N{i(i+1)} < 1
\implies N < i (i+1)
\implies N < (i+1)^2
\implies \sqrt N -1 < i
Again rewriting \frac N{i-1}- \frac Ni \ge 1 we get
\frac {N \{i - (i-1) \} } {i (i - 1)} \ge 1
\implies \frac N{i(i-1)} \ge 1
\implies N \ge i (i-1)
\implies N > (i-1)^2
\implies \sqrt N +1 > i
So we get, k is the a number satisfying \sqrt N +1 > k > \sqrt N - 1.
So k is an integer between \sqrt N +1 and \sqrt N - 1. Since there is at most two integers between \sqrt N +1 and \sqrt N - 1, we can simply check, which of these two integers satisfy the condition \frac Nk- \frac N{k + 1} < 1 and \frac N{k-1} - \frac Nk \ge 1 and choose k accordingly.
Now we know that all the values in \{floor (N/1), floor (N/2), floor (N/3),\dots, floor (N/(k-1))\} are distinct (k - 1 distinct values) and all the values in \{floor (N/k), floor (N/(k+1)), \dots, floor(N/N)\} belong to \{1, 2, … , floor(N/k)\}, with each value in \{1, 2, \dots , floor(N/k)\} guaranteed to occur at least once (so there are exactly floor(N/k) distinct values). Also the smallest element in \{floor (N/1), floor (N/2), floor (N/3), \dots , floor(N/(k-1))\}, i.e. floor(N/(k-1)) must be strictly greater from the greatest element in \{floor(N/k), floor(N/(k+1)), \dots , floor(N/N)\}, i.e. floor(N/k), since \frac N{k-1}- \frac Nk \ge 1, which means \{floor (N/1), floor (N/2), floor (N/3), \dots , floor (N/(k-1))\} and \{floor (N/k), floor (N/(k+1)) , \dots , floor(N/N)\} are disjoint (since the smallest element in one set is “strictly greater” than the greatest element in the other). So the answer simply is (k - 1 + floor(N/k)).
Subtask (a) : N = 38
First of all we need to calculate k for N = 38. We know that \sqrt N +1 > k > \sqrt N - 1, and k is an integer, so we have
\sqrt {38} +1 > k > \sqrt {38} - 1
6.16 +1 > k > 6.16 - 1
7.16 > k > 5.16
So k must be either 6, or 7.
Now we have
\frac {38}5 - \frac {38}6 = 1.267 > 1
\frac {38}6- \frac {38}7= 0.905 < 1
\frac {38}7- \frac {38}8 = 0.678 < 1
So as \frac Nk- \frac N{k + 1} < 1 and \frac N{k-1}- \frac Nk \ge 1, we see that k = 6 and k \ne 7.
So the final answer is (k - 1 + floor(N/k) )
= 6 - 1 + floor(38/6)
= 5 + floor(6.33)
= 11
Subtask (b) : N = 146
First of all we need to calculate k for N = 146. We know that \sqrt N +1 > k > \sqrt N - 1 and k is an integer, so we have
\sqrt {146} +1 > k > \sqrt{146} - 1
12.08 +1 > k > 12.08 - 1
13.08 > k > 11.08
So k must be either 12, or 13.
Now we have
\frac{146}{11}- \frac{146}{12}= 1.106 > 1
\frac{146}{12}- \frac{146}{13} = 0.935 < 1
\frac {146}{13}- \frac{146}{14}= 0.802 < 1
So as \frac Nk- \frac N{k + 1} < 1 and \frac N{k-1}- \frac Nk \ge 1, we see that k = 12 and k \ne 13.
So the final answer is (k - 1 + floor(N/k) )
= 12 - 1 + floor(146/12)
= 11 + floor(12.127)
= 23
Subtask (a) : N = 2808
First of all we need to calculate k for N = 2808. We know that \sqrt N +1 > k > \sqrt N - 1, and k is an integer, so we have
\sqrt {2808} +1 > k > \sqrt{2808} - 1
52.99 +1 > k > 52.99 - 1
53.99 > k > 51.99
So k must be either 52, or 53.
Now we have
\frac{2808}{51}- \frac{2808}{52}= 1.059 > 1
\frac {2808}{52}- \frac{2808}{53}= 1.018 > 1
\frac {2808}{53} - \frac{2808}{54}= 0.981 < 1
So as \frac Nk- \frac N{k + 1} < 1 and \frac N{k-1} - \frac Nk\ge 1, we see that k =53 and k \ne 52.
So the final answer is (k - 1 + floor(N/k) )
= 53 - 1 + floor(2808/53)
= 52 + floor(52.98)
= 104