There is a positive integer n. Let's consider all numbers n/k where k is a positive integer. Demonstrate that there are no more than 2√(n + 1) of such numbers that are different from each other.
Note: For a real number x, by ⌊x⌋ we mean the largest integer not greater than x.
There is a positive integer n. Let's consider all numbers n/k where k is a positive integer. Demonstrate that there are no more than 2√(n + 1) of such numbers that are different from each other.
Umm... are you sure you copied down this exercise correctly? Let n=1. According to the problem text, we're to demonstrate that there's less than 2n+1=22≈2.8284. In other words, we have to show that there's less than 3 fractions of the form k1,k∈Z+, but we can't do that because it's not true!
Consider 11, 21, and 31. Would you agree these are all different numbers, that there's three of them, and three is more than two? In fact, we can easily show that, since there are infinitely many positive integers, there's also infinitely many such fractions of the form k1, where k is a positive integer.
At first I thought maybe you'd accidentally omitted a sentence where they told you that it must the case that k≤n... But even then if we let n=5, the premise is still falsified. Consider:
15,25,35,45,55
As before, these are all different numbers, but the modified hypothesis says there should be no more than 25+1≈4.8990 such fractions, which we've clearly proven wrong.
Umm... are you sure you copied down this exercise correctly? Let n=1. According to the problem text, we're to demonstrate that there's less than 2n+1=22≈2.8284. In other words, we have to show that there's less than 3 fractions of the form k1,k∈Z+, but we can't do that because it's not true!
Consider 11, 21, and 31. Would you agree these are all different numbers, that there's three of them, and three is more than two? In fact, we can easily show that, since there are infinitely many positive integers, there's also infinitely many such fractions of the form k1, where k is a positive integer.
At first I thought maybe you'd accidentally omitted a sentence where they told you that it must the case that k≤n... But even then if we let n=5, the premise is still falsified. Consider:
15,25,35,45,55
As before, these are all different numbers, but the modified hypothesis says there should be no more than 25+1≈4.8990 such fractions, which we've clearly proven wrong.
You are right I accidentally made a typo. It should be 2√(n)+1 and when i wrote n/k I meant [n/k]. So considering "Note: For a real number x, by ⌊x⌋ we mean the largest integer not greater than x." 1/2 and 1/3 would be the same integer.
Ahh... okay. That's a much more difficult problem, and unfortunately I've not been able to make much headway on it. Here's some of my thoughts/observations on the matter, maybe they'll lead you somewhere.
If k>n then ⌊kn⌋=0 and thus 0 will always appear in the list of unique fractions.
If k is a factor of n then ⌊kn⌋ must be unique, because factors always come in pairs. Even if n is a perfect square, in which case one of the "pairs" will be the degenerate pair (n,n). Because of this and the previous observation, we can always guarantee that there will be at leastf(n)+1 unique fractions, where f(n) denotes the number of factors of n.
Conversely, it can be seen that there will be at mostn+1 unique fractions because ⌊1n⌋=n and the stipulation that k be a positive integer eliminates the possibility of any ⌊kn⌋ resolving to a value greater than n.
And finally, some numbers that can never appear in the list of unique fractions for a particular n are given by the ranges:
\(
\big \lfloor \frac{n}{2} \big \rfloor < x < n \\
\big \lfloor \frac{n}{3} \big \rfloor < x < \frac{n}{2} \\
\big \lfloor \frac{n}{4} \big \rfloor < x < \frac{n}{3}
\)
and so on.
Ahh... okay. That's a much more difficult problem, and unfortunately I've not been able to make much headway on it. Here's some of my thoughts/observations on the matter, maybe they'll lead you somewhere.
If k>n then ⌊kn⌋=0 and thus 0 will always appear in the list of unique fractions.
If k is a factor of n then ⌊kn⌋ must be unique, because factors always come in pairs. Even if n is a perfect square, in which case one of the "pairs" will be the degenerate pair (n,n). Because of this and the previous observation, we can always guarantee that there will be at leastf(n)+1 unique fractions, where f(n) denotes the number of factors of n.
Conversely, it can be seen that there will be at mostn+1 unique fractions because ⌊1n⌋=n and the stipulation that k be a positive integer eliminates the possibility of any ⌊kn⌋ resolving to a value greater than n.
And finally, some numbers that can never appear in the list of unique fractions for a particular n are given by the ranges:
\(
\big \lfloor \frac{n}{2} \big \rfloor < x < n \\
\big \lfloor \frac{n}{3} \big \rfloor < x < \frac{n}{2} \\
\big \lfloor \frac{n}{4} \big \rfloor < x < \frac{n}{3}
\)
and so on.
Here is what I observed. If n is even then there are n/2 numbers. If n is odd, there are (n+1)/2 numbers. Now you have to think about how we can go from a given n to the first number associated with it or even the last number. It should not be that bad.
This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
By continuing to use this site, you are consenting to our use of cookies.
