ZIO20004 - Editorial

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

3 Likes

Very hard to understand, could you plss tell it in a easier way or another approach
Thanks a lot

4 Likes

Hey @anubhavdhar ,

Didnt understand the editorial , can you explain more easy way
Thanks a lot
:slight_smile:

5 Likes

Yeah, I am also having a hard time to understand this editorial. It will be appreciable if you could explain this problem in a better way…
Thank You @anubhavdhar

2 Likes

Note: all calculations/explanations below are under are under the floor function, i.e., rounded down.

The intuition is that the problem is similar to the problem of finding all the factors of a number, by iterating only till O(sqrt(N)). This is because while iterating over K from 1 to N, the value of N/K keeps decreasing, at a decreasing rate.

This can be easily understood by taking a few examples.

  • We’ll see that when we iterate K from 1 to sqrt(N)-1, we’ll always get distinct values for N/K. Thus we get 2*(sqrt(N)-1) distinct values using this.

  • Finally, for K = sqrt(N), it may happen that N/sqrt(N) = sqrt(N), or is greater than sqrt(N).

  • In case it’s the former, we’ll add one more distinct value to our answer: sqrt(N). For the latter, we’ll add two distinct values: sqrt(N) and N/sqrt(N).

So, if N/sqrt(N)=sqrt(N), then the answer is 2*sqrt(N)-1, else the answer is 2*sqrt(N).

7 Likes

I did not get the solution. Can you explain it In an easy way as most of us naive here…
Thanks a lot

@anubhavdhar

2 Likes

One of the most important things is that if we consider any \floor{\frac{N}{i}} and i\ge \sqrt{n} then \floor{\frac{N}{i}}\le \sqrt{n} so it is one of \{1,2,\cdots, \floor{\sqrt{N}}\}.
\textbf{Claim.}
\exists k such that \floor{\frac{N}{k}}=b if b\le \sqrt{n}.

Now, we can write n=bq+r where r\ge b and r<b. So, \floor{\frac{n}{r}}=b.
\textbf{Claim.}
If x,y\in\{1,2,\cdots \floor{\sqrt{n}}\} and x<y then \floor{\frac{n}{x}}>\floor{\frac{n}{y}}. In particular, both give different values.

Let n=xq_1+r_1=yq_2+r_2. Now, q_1 \ge q_2\ge \floor{\sqrt{n}}\ge y\ge x. Then, if we have q_1=q_2 then q_1\ge xq_1-yq_1=r_2-r_1<y<q_1 which is impossible. Thus, we get \floor{\sqrt{n}} distinct values. Now, we have found two sets of values both with size \floor{\sqrt{n}} but they may have overlap which is only possible if we have \floor{\frac{n}{\floor{\sqrt{n}}}}=\floor{\sqrt{n}}, i.e. if we have that n<\floor{\sqrt{n}}^2+\floor{\sqrt{n}}. Thus, we will have in this case 2\floor{\sqrt{n}}-1 distinct values and otherwise 2\floor{\sqrt{n}} values. Together, we can express this as \floor{\sqrt{4n+1}}-1 values.

Thanks for the @akash_adm explanation
It is very nice and better
I had one doubt :

Why can’t it be sqrt(N) + 2
Like in the third subtask , sqrt(2808) = 52 and 2808/52 = 54 which is sqrt(N)+2

So in that case do we have to add 3 to the answer ?

Please clarify
Thanks a lot :slight_smile:

1 Like

Hi @rg230403 ,
Thanks for explanation
It is very hard to read your explanation because it is not well formatted
Please see what could be done

And also special thanks for the number thoery classes on unacademy :slight_smile:

Could you compile it in LaTeX?
:sweat_smile: :sweat_smile:

Code:
n = int(input()) l = [] for i in range(1,n): l.append(n//i) print (len(set(l)))

1 Like

Thanks, you are right about the example, I have modified the explanation.

But we won’t add three to the answer.

  • For N=2808, and K from 1 to sqrt(N)-1, i.e., 1 to 51, we get 51 distinct values for N/K.

  • For K from N/sqrt(N)+1 to N, i.e., from 55 to 2808, we again get 51 distinct values.

  • Now, for K=52, we get 54, for K=53 , we get 52 and for K=54, we also get 52. So, two more values: 52 and 54.

  • Total =51+51+2=104.

If N/sqrt(N)=sqrt(N), then the answer is 2*sqrt(N)-1, else the answer is 2*sqrt(N).

2 Likes

It woulg be great if you explain in easier terms

Here we go for the best possible easiest solution look all 4 questions were just about noticing patters now
lets take n=10 then you can notice that sq.root of 10 is 3 {taking greatest integer} now divide 10 by 4 we get 2 {same greatest integer} now add 2+3=5 here goes your answer that is 5

now lets try with real questions
N=38 will give sq.root as 6 and now divide by 7 that is 5 so 6+5=11 i.e answer

***same way do it for all take sq.root of number and then divide by next no. of GIF of sq.root and add the answer of division and GIF of sq.root…

HOPE IT IS BEST POSSIBLE AND EASIEST SOLUTION FOR THIS QUESTION

1 Like

Yes
it is

Great Explanation and Easy to Understand. :+1: :+1:

Code in C++:
#include
#include <bits/stdc++.h>
using namespace std;

int main() {
int n; cin >> n;
set a;
for (int i = 1; i <= n; i++) {
a.insert(floor(n / i));
}
cout << a.size() << endl;
}