$n$ is perfect!

Number Theory Level 4

What is the largest positive integer $n$ , that is not a multiple of 10, such that

$\Large \left \lfloor \frac{n^2}{100}\right \rfloor$

is a perfect square?

Notation : $\lfloor \cdot \rfloor$ denotes the floor function .

The answer is 41.

4 solutions

Hana Wehbi
Mar 7, 2017

Suppose that removing the last two digits of $n^2$ leaves the perfect square $s^2$ .

Then $0 < n^2- (10s)^2 < 100$ . Thus $n^2-(10s)^2= (n+10s)(n-10s) ≥ n+10s > 10s+10s = 20s$ , so $20s < 100$

Therefore $s ≤ 4$ and hence $n^2< 100+(10s)^2 ≤ 1700$ .

Therefore $n ≤ 41,$ and $41^2 = 1681$ , so $n = 41$ works.

Moderator note:

That's a very efficient way to obtain a bound on $s$ , and hence $n$ .

Thank you.

Hana Wehbi - 4 years, 3 months ago

Very nicely done :) I love how you have used the facts that $n^2 - (10s)^2$ is a two digit number and $n > 10s$ to find an upper bound on $s$ .

Pranshu Gaba - 4 years, 3 months ago

Thank you, but what is nice, how we can have for one problem several solutions. It shows how we think differently but on the right track.

Hana Wehbi - 4 years, 3 months ago

I agree, it is amazing to see that a problem can be solved in a variety of ways, and yet they all lead to the same result.

Pranshu Gaba - 4 years, 3 months ago

@Hana Nakkache - very elegant! Well done. -

Wesley Zumino - 3 years, 11 months ago

# -*- coding: utf-8 -*-
"""
Created on Fri Nov 24 14:43:24 2017

@author: Michael Fitzgerald
"""

#https://brilliant.org/weekly-problems/2017-03-06/advanced/

# What is the largest positive integer ,  is not a multiple of 10, such 
# that floor(n^2/100) is a perfect square

from math import floor, sqrt

def is_square(integer):
    root = sqrt(integer)
    if int(root + 0.5) ** 2 == integer:
        x = True
        return x
    else:
        x = False
        return x

i = 10
limit_i = 1000000
denominator = 100

while i > 0:
    i += 1
    if i%10 != 0:
        n = int(floor(i**2/denominator))
        t_f = is_square(n)
        if t_f == True:
            print 'The value n is: %d   The perfect square of floor(n**2/100) is:  %d' % ( i, n)
            z = i

    if i == limit_i: 
        print 'The largest n that satifies floor(n**2/100) being a perfect square is:  %d' % z

The value n is: 11   The perfect square of floor(n**2/100) is:  1
The value n is: 12   The perfect square of floor(n**2/100) is:  1
The value n is: 13   The perfect square of floor(n**2/100) is:  1
The value n is: 14   The perfect square of floor(n**2/100) is:  1
The value n is: 21   The perfect square of floor(n**2/100) is:  4
The value n is: 22   The perfect square of floor(n**2/100) is:  4
The value n is: 31   The perfect square of floor(n**2/100) is:  9
The value n is: 41   The perfect square of floor(n**2/100) is:  16
The largest n that satisfies floor(n**2/100) being a perfect square is:  41

Michael Fitzgerald - 3 years, 6 months ago

This is great!

Adhiraj Dutta - 1 year, 4 months ago

Tom Capizzi
Mar 5, 2017

Let us assume a number of the form $n = 10 j + k$ , both $j$ and $k$ positive, and $k$ is a single digit from $1$ to $9$ .
Then $n^2 = 100 j^2 + 20 j k + k^2$ , and $\frac{n^2}{ 100} = j^2 + \frac{j k}{ 5} + \frac{k^2}{ 100}$ .
The next larger perfect square to this is $(j + 1)^2 = j^2 + 2 j + 1$ .
The difference between these two values is $2 j + 1 - \frac{j k}{ 5} - \frac{k^2}{ 100}$ .
Since the largest value of $k$ is $9$ , the smallest this difference can be is $0.2 j + 0.19$ , for any value of $j$ .
So, there is no value of $k$ that can increase the argument of the floor function to the next perfect square.
So we are limited to values of $j$ and $k$ which yield the same perfect square as $j^2$ .
For this to be true, $\frac{j k}{ 5} + \frac{k^2} {100}$ must be less than $1$ .
For the smallest value of $k$ (since we are asked for the largest $n$ ), $\frac{j}{ 5} + 0.01 < 1$ .
Then $j < 4.95$ , and since $j$ is a whole number, $j = 4$ . As $k = 1$ , $n = 41$ .

Wow, great solution! The steps are laid out clearly, and each step follows naturally from the previous one.

An alternate way to show that the floor function does not increase to the next perfect square is by showing that $10 j \le 10j + k < 10(j+1)$ , therefore $j^2 \le \frac{(10j + k)^2}{100} < (j + 1)^2$ and hence $\lfloor \frac{(10j + k)^2}{100} \rfloor = j^2$ .

For completeness, after we show that $j = 4$ is the maximum value for $j$ , we should also show that $k = 1$ is the maximum for $k$ . In other words, once we know that $n < 50$ , and we have shown that $n = 41$ works, we should also show that any $n \ge 42$ does not work.

Pranshu Gaba - 4 years, 3 months ago

If I try any no. Say 241 Then it also satisfy the condition Let (n²/100)=A²
Put n =241 , A²=(241²/100) A=24.1

And if I use 41 then A comes out to be 4.1

So please explain

ansh bindlish - 4 years, 3 months ago

You are missing the floor function , which is denoted by the special brackets $\lfloor \, \, \rfloor$ . If $n =241$ , then we want $\lfloor \frac{241^2}{100} \rfloor$ to be a perfect square

$\left \lfloor \frac{241^2}{100} \right \rfloor = \left \lfloor \frac{58081}{100} \right \rfloor = \lfloor 580.81 \rfloor = 580$ . Since $580$ is not a perfect square, it does not work.

Pranshu Gaba - 4 years, 3 months ago

Louis W
Mar 10, 2017

Any perfect square can be derived from $\lfloor \frac{p^{2}}{100} \rfloor$ if p is a positive integer and multiple of 10 (or negative integer, but the question wants a positive integer). So the answer to this question is an integer $n:\space p+1 \leq n \leq p+9$ , or an integer $n:\space n=p+1 \geq p+10$ . I'm not sure there exists a number realm where that second option makes sense, so the first option is where the answer exists.

This question asks for the greatest n. The greatest n would be as few units greater than p as possible (i.e. $n=p+1$ ) while also being as much greater than $p^{2}$ as possible without being so greater that it changes anything greater than the tens digit, i.e. not 100 or more greater. Thus you get something like so:

$(p+1)^{2} < p^{2}+100$

Solve that and you get $p<49.5$ . p is an integer and multiple of 10, so Price Is Right that answer and you get $p=40$ and $n=40+1=\color{#3D99F6}41 \color{#333333}\quad\Box$

How is it 41

Aniyah Scrutchen - 4 years, 3 months ago

Solve $(p+1)^{2}<p^{2}+100$ and you get $p<49.5$ (is that where you don't understand things?). Since $p$ is an integer and multiple of $10$ , at maximum $p=40$ . Due to the question asking for a maximum, I deduce that for the maximum $p$ , $n=p+1$ . So $n=40+1=41$ .

Did that help?

Louis W - 4 years, 3 months ago

Let me try to summarize this solution:

If $\left \lfloor \frac{n^2}{100}\right \rfloor = m^2$ , then there is an integer $k$ such that $\frac{(10k)^2}{100} = m^2$
Because the floor function changes values at integers, we must have $\left \lfloor \frac{n^2}{100}\right \rfloor < \left \lfloor \frac{n^2+100}{100}\right \rfloor$ all have the same value.
We want an $n$ that is not a multiple of 10 which satisfies $\left \lfloor \frac{n^2}{100}\right \rfloor = m^2$ . By (1), there is a multiple of 10, say $10k$ , which also satisfies this criteria. Because our $n$ is not a multiple of $10$ , we must have $10k < n$ and by (2), we also want that $n^2 < (10k)^2 + 100$ .
Because $n$ is an integer, a necessary (but not sufficient) condition, is that $10k + 1 \leq n$ . And by the second equation in (3), we should have $(10k + 1)^2 < (10k)^2 + 100$ . That gives us $k < 4.95$ , weakening which we could say that $k < 5$

The next step you did is not very clear to me. How do you deduce $n$ is indeed 41?

Agnishom Chattopadhyay - 4 years, 3 months ago

You messed all the variables up, added new ones, and just in general made it more difficult, but I think I get what you're doing here...

If $k<5$ and an integer, then at maximum $k=4$ . At maximum, an increase of 1 to 10k will give a maximal increase from $(10k)^{2}$ to $(10k+1)^{2}$ while that increase remains less than 100. So, $n=10k+1$ . Input $k$ and there you have it.

Did that help? I'm not quite sure I get what you're doing here so maybe that didn't help.

Louis W - 4 years, 3 months ago

Akshat Joshi
Mar 5, 2017

Let $A$ be some integer. Then, $\left \lfloor \frac{n^{2}}{100} \right \rfloor = A^{2}$

$\left \lfloor \frac{n^{2}}{100} \right \rfloor = \frac{n^{2}}{100} - h$ where $0 \leq h < 1$

$n = 10\sqrt{A^{2} + h}$

But it is given that $n$ is not a multiple of $10$ , thus $\sqrt{A^{2} + h}$ should cancel out 10 i.e $A^{2} + h =$ $\frac{n^2}{100}$ Also since $0 \leq h < 1$ , therefore $h$ represents the decimal part of $A^{2} + h$ . Also clearly $A^{2} + h$ should have 2 decimal places with the integral part $A^{2}$ being a perfect square. We can easily find by trial and error that the largest number $n$ satisying this criteria is $41$ , since $41^{2} = 1681$ and thus in this case $A^{2} + h = 16.81$ where 16 is a perfect square and 0.81 is h and the number has 2 decimal places. If we go ahead of 41 we'll observe that we never get the integral part as a perfect square.

Hence $41$ is the answer.

I am trying to understand your solution, but I finding the reasoning to be circular when you introduce $Z$ . Since $A^2 + h = \frac{n^2}{100}$ , isn't $Z$ the same as $n$ ?

Also, in the last paragraph, do you mean to say $h$ represents the decimal part of $A^2 + h$ instead of $\sqrt{A^2 + h}$ , and that $A^2 + h$ should have 2 decimal places instead of $\sqrt{A^2 + h}$ ?

Pranshu Gaba - 4 years, 3 months ago

I am sorry for the error. I have made the changes to the solution. Thanks for pointing out.

Akshat Joshi - 4 years, 3 months ago

It was not at all clear to me that the partial square brackets signified "The Integer of". This should have been made more clear in the problem statement.

Stephen Rasey - 4 years, 3 months ago

I see that the problem has been edited to clarify this :)

Christopher Boo - 4 years, 3 months ago

n n n is perfect!

The answer is 41.

4 solutions

Moderator note:

0 pending reports

$n$ is perfect!