A Problem on Square Root

Algebra Level 3

We are going to perform a simple procedure below to a natural number.

[Step 1] Divide the number by $2$ .

[Step 2] Subtract $1$ , $2$ , $3$ , $4$ , $\cdots$ from the number from [Step 1] , until right before the result becomes negative. If the result from [Step 1] doesn't allow us to even subtract $1$ , then leave it untouched, and proceed to the next step.

[Step 3] Multiply $2$ to the number from [Step 2] .

I'll show you some examples to make it clear.

[Example 1] $25(=5^2)$

[Step 1] $25\div2=12.5$ .

[Step 2] $12.5-1-2-3-4=2.5$ .

[Step 3] $2.5\times2=\boxed{5}$ .

Another example.

[Example 2] $1156(=34^2)$

[Step 1] $1156\div2=578$ .

[Step 2] $578-1-2-3-4-5-6-7-8-9-10-\text{ }\cdots\text{ }-31-32-33=17$ .

[Step 3] $17\times2=\boxed{34}$ .

You'll see that the output is the positive square root of the input.

Now, your objective is to:

Find the maximum value of positive integer $n$ that makes this property hold for $n^2$ .

If you think "Every positive integer $n^2$ satisfies the property", submit $999999$ as your answer.

If you think "Even though not every positive integer $n^2$ satisfies the property, there are infinitely many positive integers $n^2$ that satisfy the property", submit $999998$ as your answer.

Source: The inspiration of this problem is from a Chosun (old Korean) mathmatician Hong Gilju.

The answer is 999999.

1 solution

Zach Abueg
Jun 17, 2017

Notice that $\displaystyle x - 1 - 2 - 3 - 4 - 5 ... - n \ = \ x - \frac{n(n + 1)}{2}$ . Now, the crucial step is to realize that every time we subtract $1, 2, 3, 4 \ ...$ "until the right before the result becomes negative" in step 2, we are subtracting only up to $n - 1$ . I will show this in a moment, but first let's generalize the steps to this procedure, which will enable us to see that this does, in fact, hold for every positive integer $n$ :

$\displaystyle \begin{aligned} 1. \ & n^2 \\ 2. \ & \frac{n^2}{2} \\ 3. \ & \frac{n^2}{2} - \frac{(n - 1)n}{2} = \frac{n}{2} \\ 4. \ & \frac n2 \cdot 2 = n \end{aligned}$

Now let's look at step 3. As previously mentioned, we can only subtract up to $n - 1$ , hence the $\displaystyle - \frac{(n - 1)n}{2}$ . That leaves us with the positive number $\displaystyle \frac n2$ . Now let's say we had subtracted up to $n$ :

$\displaystyle \begin{aligned} \frac{n^2}{2} - \frac{n(n + 1)}{2} & = \frac{n^2 - n^2 - n}{2} \\ & = -\frac n2 \end{aligned}$

We see that subtracting up to $n$ would have yielded a negative number. Hence, we only subtract up to $n - 1$ .

We have shown that this property holds for all positive integers $n$ . QED

A Problem on Square Root

Source: The inspiration of this problem is from a Chosun (old Korean) mathmatician Hong Gilju.

The answer is 999999.

1 solution

0 pending reports