Squares and Square-Roots, Galore!

Algebra Level 5

Suppose we have two sequences $a_1,a_2,\ldots a_{2014}$ and $b_1,b_2,\ldots b_{2014}$ such that all terms in both sequences are in the range $[0,1]$ . Let $M$ be the maximum value of $\left(\sum_{i=1}^{2014}\sqrt{a_i^2+b_i^2}\right)-\sqrt{\left(\sum_{i=1}^{2014}a_i\right)^2+\left(\sum_{i=1}^{2014}b_i\right)^2}$ What is $\lfloor M\rfloor$ ?

The answer is 589.

2 solutions

Daniel Liu
Apr 9, 2014

I will refer to the left term as the LHS, and the right term as the RHS.

Seeing the squares inside square roots, we can approach this geometrically. Note that the LHS states the sum of the hypotenuses of the right triangles with sides $a_1,b_1$ , $a_2,b_2,$ , and so on, to $a_{2014},b_{2014}$ . The LHS, on the other hand, asks us to take the hypotenuse of a right triangle with side lengths $a_1+a_2+\cdots +a_{2014}$ and $b_1+b_2+\cdots +b_{2014}$ .

We can draw this figure out: Consider the coordinates $(a_1,b_1)$ . The distance from the origin to this point is the first part of the LHS. Now, consider the point $(a_1+a_2,b_1+b_2)$ . The distance from the first point to this point is the second part of the LHS. We can continue plotting points like this, until we arrive at $(a_1+a_2+\cdots +a_{2014},b_1+b_2+\cdots +b_{2014})$ . Thus, the LHS is the length of the path taken from $(0,0)$ to $(a_1+a_2+\cdots +a_{2014},b_1+b_2+\cdots +b_{2014})$ , going through the points assigned along the way.

The RHS, on the other hand, is simply the straight-line distance between $(0,0)$ and $(a_1+a_2+\cdots +a_{2014},b_1+b_2+\cdots +b_{2014})$ . Therefore, we want to minimize this straight-line distance and maximize the length of the path taken.

Note that no matter what $a_i$ or $b_i$ is, we always walk towards our final point, never away. This is because $a_i,b_i\ge 0$ . Therefore, the farthest path we can take to the final point (which will maximize $M$ ) is along the border of a rectangle with $(0,0)$ and $(a_1+a_2+\cdots +a_{2014},b_1+b_2+\cdots +b_{2014})$ as its opposite corners.

We can achieve this by setting $a_i=1$ and $b_i=0$ for $i=1\to 1007$ , then setting $a_i=0$ and $b_i=1$ for $i=1008\to 2014$ . Therefore, our LHS is $2014(1)=2014$ , and our RHS is $\sqrt{1007^2+1007^2}=1007\sqrt{2}$ . The difference is therefore $M=2014-1007\sqrt{2}\approx 589.89$ , so $\lfloor M\rfloor = \boxed{589}$ .

I don't feel like this is a complete proof.

You need to be careful with the technicalities of your proof. You can't separate out the two terms and try and deal with them separately, as they influence each other. For example, we cannot minimize this straight-line distance and separately maximize the length of the path taken.

Even though the perimeter of the box would yield the maximum perimeter, you need to take into consideration that you are also limited to having 2014 points along the way. For example, we could reach the point $(2014, 2014)$ by choosing $a_i = b_i = 1$ , but we can't reach there with 2014 points taken along the border of a rectangle. You have not provided any justification for why we must have one of $a_i$ or $b_i$ to be 0.

Calvin Lin Staff - 7 years, 2 months ago

Yea, I feared that that was the case when writing my solution. However, I know 99% sure that the answer is still correct. I have no idea how to patch up the hole in my proof though... :(

Could you possibly give a hint, if you have figured it out?

Daniel Liu - 7 years, 2 months ago

While the geometric interpretation is useful, we do not gain much intuition about the problem as it is slightly harder to compare how the change in difference of lengths.

I would approach the problem in the following way. You should see several of your ideas, though exploited in different ways.

Step 1: Assume that all variables other than $a_k, b_k$ are fixed. Let $A_k = \sum_{i\neq k} a_i$ and $B_k = \sum_{i \neq k} b_i$ . We wish to maximize $\sqrt{ a_k ^2 + b_k^2 } - \sqrt{ (A_k+a_k)^2 + (B_k+b_k)^2 }.$ Show that this happens when $a_k, b_k$ are either 0 or 1.

Elaboration of Step 1: This can be interpreted as the difference of lengths from the point $(A_k+a_k, B_k + b_k)$ , to the points $(A_k,B_k)$ and $(0,0)$ . The level curves (i.e. where the difference of lengths is a constant) are the family of hyperbola with focus at $(A_k, B_k)$ and $0, 0$ . Hence, we know that the maximum must occur at one of the corner points of the square $[0 , 1 ]^2$ .

Step 2: We now have $w, x, y$ and $z$ times when $(a_i, b_i) = (0,0), (1,0), (0,1), (1,1)$ respectively. This gives us the 4-variable inequality

$x + y + z \sqrt{2} - \sqrt{ (x+z)^2 + (y+z)^2},$

subject to $w + x + y + z = 2014$ . Show that the maximum occurs when $x = y = 1007, w=z=0$ .

Calvin Lin Staff - 7 years, 2 months ago

@Calvin Lin – I understand step 2, but I'm a little confused about Step 1. Should it be $\sqrt{a_1^2+b_1^2}-\sqrt{(A+a_1)^2+(B+b_1)^2}$ or it is right as it is? Also, I don't see how the hyperbolas link to the maximum occurring at $[0,1]^2$ . Can you please explain it a bit more clearly?

EDIT: I think I understand what you mean in the first part of step 1. We let $a_1,a_2,\cdots a_{k-1},a_{k+1},\cdots a_{2014}$ be constants, and let $a_k$ be the variable. Similar for $b_k$ . Then, we define $A=\displaystyle\sum_{i\ne k}^{2014}a_i$ and similar for $B$ . Then, we wish to maximize $\sqrt{a_k^2+b_k^2}-\sqrt{(A+a_k)^2+(B+b_k)^2}$ . Is that what you meant by the $i$ 's?

Daniel Liu - 7 years, 2 months ago

@Daniel Liu – Yes, I wanting to do it generally, then decided to do it for just 1 value, and thus screwed up my notation. I've fixed it.

I resorted to talking about hyperbolas, as it's the easiest way to convince myself about the truth of step 1, without going into the gritty details of calculus, or inequality comparison. However, I'm not too certain of it's validity.

Calvin Lin Staff - 7 years, 2 months ago

K T
Jun 20, 2019

I do not have a proof, but my consideration was this:

Let $\vec{x_i}=(a_i,b_i) \text{ in } [0,1]^2$ , then $M=\sum_{i=1}^n{|\vec{x_i}|}- |\sum_{i=1}^n{\vec{x_i}}|$ .

For n=2, this reminds of the triangle inequality $|\vec{x_1}|+|\vec{x_2}| \ge |\vec{x_1}+\vec{x_2}|$ . So we try to think of a triangle within the unit square $[0,1]^2$ , having one of the vertices fixed at the origin, and one of the sides shorter than the sum of the other two sides by the largest possible difference. $M=0$ when $\vec{x_1}$ and $\vec{x_2}$ are in the same direction Opposite direction is not allowed, but M is at maximum when the vectors are (1,0) and (0,1).

For n=4 you'd get M= $|\vec{x_1}|+|\vec{x_2}|+|\vec{x_3}|+|\vec{x_4}| -|\vec{x_1}+\vec{x_2}+\vec{x_3}+\vec{x_4}|$ , so that would be like drawing 4 vectors head to tail: travelling in 4 steps and ending up in a point such that the distance traveled minus the final distance to the origin is as large as possible. But you can only travel in directions ranging from north to east, and max. 1 unit N and/or E per step. Because the component straight away from the origin does not add to M, only the component perpendicular, and since your location will always be in the first quadrant, it is no use choosing any direction between north and east, rather choose either north or east for each step. It is like finding the most inefficient path to get to (2,2), given the direction constraint.

For n=2014 it's the same idea, we can have 1007 steps (1,0) and 1007 steps (0,1), so that we get $M=1007(2-\sqrt{2})$ .

Squares and Square-Roots, Galore!

The answer is 589.

2 solutions

0 pending reports