If \(x\) is a positive integer, is the number of its divisors smaller than \(2* \lceil \sqrt{x} \rceil - 1\) ?

\(\lceil a \rceil\) is defined as the smallest integer that is not less than \(a\) .

1. \(x\) is not a square of an integer
2. \(x\) is prime


Source: GMAT Club Tests - hardest GMAT questions

Sufficiency of S2 is easier to prove, and is a good starting point. A prime number only has 2 divisors. For the smallest prime \(x=2\) , the equation gives \(2*2-1=3\) and \(2 < 3\) is satisfied. For larger primes, it will also be satisfied, as the right hand side grows, but the left hand side (the number of divisors) remains 2.

Proving the sufficiency of S1 is a lot more difficult and may not be worth the time. If you attempt it and see the time running out, consider doing a guess. It will be a good educated guess with a 50% chance of being right, as the sufficiency of S2 eliminates the choices A, C, E.

To prove that S1 is sufficient, group all divisors of \(x\) into \((a, \frac{x}{a})\) pairs. You have to count the pairs for which \(a \lt \frac{x}{a}\) (S1 says that \(a \ne \frac{x}{a}\) ) and double the result to get the number of divisors.

Consider the worst possible case when \(x\) is divisible by 2, and 3, and 4, and 5, and so on, then the pairs will be \((1, x)\) , \((2, \frac{x}{2})\) , \((3, \frac{x}{3})\) and up until \((s, \frac{x}{s})\) where \(s\) is the greatest integer less than \(\sqrt{x}\) . We can express it as \(s = \lceil \sqrt{x} \rceil - 1\) . Then, if the number of divisors of \(x\) is \(N(x)\) , we obtain \(N(x) \le 2s = 2\lceil\sqrt{x}\rceil - 2 \lt 2\lceil\sqrt{x}\rceil - 1\) .
The correct answer is D.



Would someone feeling up to it please explain the explanation of statement 1 in plain English?

You put big effort to explain it. But I am wondering whether the question really needs any statement to answer it.

Just wanted to say that, for me, if a = 5, \(\lceil 5 \rceil\) should be 6. If this not true what exactly meant by \(\lceil a \rceil\)?

This is not very important but I think you're wrong. It's said that

So if you have \(\lceil 5 \rceil\), it equals 5, not 6 as you said. It has to be the SMALLEST integer which is not less than. In your example 5 is not less than 5. It is the smallest integer from all possible integers that are not less than 5. This might be easier to explain as rounding but in a special way. Even if the number is slightly greater than some integer (say, 6.05), \(\lceil 6.05 \rceil\) will equal 7. Whereas rounding 6.05 to units results into 6, \(\lceil 6.05 \rceil\) results into 7. In other words, the number after this operation is the next greater integer on the number line. I know it's confusing. Just wanted to check that you're not mistaken.

As to the confusing explanation for this problem, I'm not sure I'll be able to explain better. These concepts won't be tested in the real GMAT.

I tested a few numbers.

1 -> \(2* \lceil \sqrt{x} \rceil - 1\) = 1 -> factors of 1 = 1
4 -> \(2* \lceil \sqrt{x} \rceil - 1\) = 3 -> factors of 4 = 3
9 -> \(2* \lceil \sqrt{x} \rceil - 1\) = 5 -> factors of 9 = 3
16 -> \(2* \lceil \sqrt{x} \rceil - 1\) = 7 -> factors of 16 = 4

2 -> \(2* \lceil \sqrt{x} \rceil - 1\) = 3 -> factors of 2 = 2
3 -> \(2* \lceil \sqrt{x} \rceil - 1\) = 3 -> factors of 3 = 2
5 -> \(2* \lceil \sqrt{x} \rceil - 1\) = 5 -> factors of 5 = 2
6 -> \(2* \lceil \sqrt{x} \rceil - 1\) = 5 -> factors of 6 = 4

It seems that number of divisors is smaller for all positive integers with the exceptions of 1 and 4.

mmm, I understood the answer but takes a lot of time. Couldn't do it myself.

I think the best starting point for this q could be to start with option 2.

We can answer the query considering the prime nos.

then comes statement 1.I did the question by taking some examples like 12,36 which has lot of divisors.

My take would be option D

The second statement is easy to test as prime numbers will have only two divisors and \(2*[sqrt[x] - 1\) is always greater than or equal to 3 for prime numbers.

For the first statement I put in some smart numbers to (10, 25) to see that it holds true

So my best guess would be (D)

--------------------------------
http://pyarapopat.wordpress.com

Seeking kudos

(1) x = 2,3,6, 8

2 * [root(2)] - 1 = 2 * [1.41] - 1 = 2 *2 - 1 = 3

2 * [root(8)] - 1 = 2 * [2.somthing] - 1 = 2 *3 - 1 = 5

Sufficient

(2)

x = 11 (One more prime example)

2 * [root(11)] - 1 = 2 * [3.something] - 1 = 2 *4 - 1 = 7

Sufficient

Answer - D
_________________

I did it by plugging in the number for both the statements and found out that D is the answer.
_________________

Plugging number was useful and easy way to solve it..
Answer is D.

1. Sufficient.

plugging in numbers we can see this is sufficient

2. Sufficient.

prime number will only have 2 divisors - 1 and the number itself

min value of 2 *[sqrt(x}] -1 is 3

hence this is always true.

Answer is D.

Extremely difficult one

Statement 1: x isnt a square of an integer.

I thought of attempting this statement this way.
Since x is a positive integer, it can take values 1,2,3,4....so on. If x were 1, it will have to be a square of an integer, which is 1 itself. Therefore x cannot be 1. Let's say x were 2. This is possible since 2 isnt a square of an integer. So the minimum value x can take is 2. Lets put 2 in the given equation now.

2 x [sqrt2] - 1 = 2 x 2 - 1 = 4 - 1 = 3 > No. of factors of 2. Thus sufficient. I am assuming that all integers that are not a square of any integer and are on the right side of 2 on the number line would follow the same. I ain't very sure about this though. please comment.

I like the first advice as the best...do the s-2 part, and then guess with 50% chances..

Seriously, in a timed environment as a GMAT, do we get these kinda questions? and if we do, does'nt make any sense solve it through.

Just came across this thread. Let me try

I dont think anyone has problem with the statement 2.

For statement 1:

The maximum no. of factors any integer can have is 2*\sqrt{x} -1.
This is because any integer x can be expressed a the product of 2 factors in the following ways: (1,x), (2,x/2), (3, x/3)........ (\sqrt{x},\sqrt{x}) all of which add up to 2\sqrt{x} -1 no of factors. (Note that this is the best possible case, we cannot have more factors than this)
(-1 because in case of the last term, \sqrt{x} will be counted twice, if it exists)

For eg: 36: No. of factors = (1,36), (2,18),(3,12),(4,9),(6,6) === add up to 9 factors which is less than 11 (2\sqrt{36}-1)
Note that we counted 6 only once.

From statement 1: is x is not a square of an integer, than the ceiling function of x is greater than square root of x
Is is equal only iff x is a perfect square.
for eg: ceiling function of 12 is 4, which is greater than \sqrt{12}.

From this it follows that the no. of factors is necessarily less than 2*(celing fn of x)-1

PS: Sorry i dont know how to post the image of the step function, it is also known as the ceiling function of x.

If you know this concept, it wont take you more than 20 secs to solve the problem. Now I know, how easy it is to understand a concept but how difficult to teach the same to some one else.I'm probably not the best person to explain this concept.

Unless I cant find a way to solve a question algebraically, I normally avoid substituting values, for there are numerous cases & you miss one, chances are that you might zero down on the wrong answer.

I believe that in a timed & a stressful environment, whatever method suits you to zero in on the right answer is the best way to solve the problem. So, if you cannot find a way to solve the question under 2 mins, go ahead with substitution/calculated guessing. To each his own.

Maybe bb can come up with a better explanation to this problem ( maybe??......of course he will )

Also, pls note that I was just trying to explain how to understand/solve the problem, and not show the most optimum & fastest way to get to the correct answer. Of course, the latter is what you should aim during the gmat, but it is always beneficial, especially during your preps to understand how to approach each question, rather than just mark the correct answer without understanding the concept underlying the question.

PS:
I didn't get your question you asked. What i mean by the celing function is:
the smallest integer not less than a, i.e, ceiling function of 5.2 == 6, ceiling function of 6 == 6.

Hope that helps.

Excited to see Bunuel's response to this question.

If x is a positive integer, is the number of its divisors smaller than 2*<sqrt{x}> - 1 ?

<a> is defined as the smallest integer that is not less than a .

1. x is not a square of an integer
2. x is prime

Source: m12-72874.html

Bunuel any help on this - how to go about solving this question

We know that \(2*<sqrt{x}> - 1\) will always take on odd-values. Let x be a perfect square and \(x = a^{2k}\), where a is a prime number. For any value of k, x will have an odd number of factors. It is for this very reason that we are given x is not a square of an integer, so that the number of factors of x and any value of \(2*<sqrt{x}> - 1\) don't equal each other, as the latter can only take on odd values. By design from F.S 1, x can not have any even powers and thus, we will always get even no of factors for x. If they had not mentioned this point, we would not be able to give a definitive answer from F.S 1.

So we know that if not anything, \(2*<sqrt{x}> - 1\) and no of divisors for x WILL never be equal.Thus, if we can prove that there is a general rule where either the no of divisors are ALWAYS less than \(2*<sqrt{x}> - 1\) OR are ALWAYS more than \(2*<sqrt{x}> - 1\) , we will get a definitive answer.

No of factors for x can only be even:

Minimum x with 2 factors = 2 Value of \(2*<sqrt{2}> - 1\)= 3.
Minimum x with 4 factors = 6 Value of \(2*<sqrt{6}> - 1\) = 5.
Minimum x with 6 factors = 12 Value of \(2*<sqrt{12}> - 1\) = 7.
Minimum x with 8 factors = 24 Value of \(2*<sqrt{24}> - 1\) = 9. And so on..

What we get is that if for 12, the value of \(2*<sqrt{12}> - 1\) is 9, then for numbers that have 6 factors and are bigger than 12 say 28, the value of \(2*<sqrt{28}> - 1\) will be even more than 9(11). Thus, we can say that the no of factors will always be less than the value of \(2*<sqrt{x}> - 1\) .

If anyone has a doubt as to whether this pattern is uniform, notice that the no of divisors and the value of \(2*<sqrt{x}> - 1\) are even and odd respectively. Thus, assuming that some value of x with say 8 factors has \(2*<sqrt{x}> - 1\) as 7 or 5 or 3,it won't be possible because we have proved that the MINIMUM value of\(2*<sqrt{x}> - 1\) for any x with 8 factors is 9.

From F.S 2, it is very clear that the no of factors is only 2 for any prime value of x and the minimum value for \(2*<sqrt{2}> - 1\) is 3.Sufficient.
_________________