challenge of the week – Lucky's Notes

Update (7/31/2010): This article has been rewritten, with several more elegant solutions added, rather than the coordinate solution presented originally.

This is the second time I’m attempting a Challenge of the Week problem, after solving this one and winning coupons for Baskin Robbins’ Ice Cream (which by the way I can’t use because I’m in Canada).

Well my solution here is pretty inelegant and is a sort of ‘coordinate bash’ geometric solution. Pretty sure a better solution exists, but this is the best I could do for now.

The problem is originally from here (although I expect it will be somewhere else by the end of this week).

Problem

In equilateral triangle $\triangle ABC$ , M is a point on BC. Let N be the point not on BA such that $\triangle BMN$ is equilateral. P, Q, and R are midpoints of AB, BN, and CM respectively. Prove that $\triangle PQR$ is equilateral.

Solution by coordinate geometry

As with coordinate geometry, I put the figure on a cartesian grid with B as the origin.

Without losing generality, we can let BC be on the x-axis and C be (4,0). Also let M be (4x,0) for some value x between 0 and 1. So 4x is between 0 and 4 and is any point on BC.

Doing this doesn’t lose generality because any instance of this problem can be rotated and scaled so that B is the origin and C is (4,0).

I choose these values for the initial points in order to end up with easier to work with points for PQR.

Noting the coordinates of the points:

$B = (0,0)$

$C = (4,0)$

$M = (4x,0)$

Since we know B and C, we can calculate A and N:

$A = (2,2 \sqrt{3})$

$N = (2x, -2x \sqrt{3})$

It becomes easy to calculate P, Q, and R:

$P = (1, \sqrt{3})$

$Q = (x, -x \sqrt{3})$

$R = (2x+2, 0)$

We now calculate the distances of PQ, QR, and PR using the distance formula:

$\begin{array}{rcl} PQ &=& \sqrt{(x-1)^2 + (x \sqrt{3} + \sqrt{3})^2} \\ &=& 2 \sqrt{x^2 + x + 1} \end{array}$

$\begin{array}{rcl} QR &=& \sqrt{(2x+2-x)^2 + (x \sqrt{3})^2} \\ &=& 2 \sqrt{x^2 + x + 1)} \end{array}$

$\begin{array}{rcl} PR &=& \sqrt{(2x+2-1)^2 + \sqrt{3}^2} \\ &=& 2 \sqrt{x^2 + x + 1)} \end{array}$

We find that the three simplify to the same thing. That means $PQ = QR = PR$ and $\triangle PQR$ is equilateral.

Solution via trigonometry

Rather than a coordinate bash, we can use a similar trigonometry bash. We let $a$ be the larger equilateral side ( $AB$ ), and $b$ be the smaller equilateral side ( $BN$ ).

Using the law of cosines, with the fact that $\cos 60^\circ = \frac{1}{2}$ and $\cos 120^\circ = -\frac{1}{2}$ , we can get these equations:

$PR^2 = (\frac{a}{2})^2 + (\frac{a+b}{2})^2 - (\frac{a}{2})(\frac{a+b}{2})$

$QR^2 = (\frac{b}{2})^2 + (\frac{a+b}{2})^2 - (\frac{b}{2})(\frac{a+b}{2})$

$PQ^2 = (\frac{a}{2})^2 + (\frac{b}{2})^2 + (\frac{a}{2})(\frac{b}{2})$

If we just simplify these three expressions, we find that they are exactly the same:

$PR^2 = QR^2 = PQ^2 = \frac{a^2+ab+b^2}{4}$

which proves the result.

Solution via homothetic triangles

A more elegant and less ‘bashy’ solution exists via homothety.

We expand triangle $PQR$ by a factor of 2 about the point $B$ , giving the new triangle $ANK$ . That is, $BA$ is twice of $BP$ , and $BK$ is twice of $BR$ , and so on.

It is sufficient to prove that $\triangle ANK$ is equilateral, as it is homothetic to $\triangle PQR$ .

Since $BK = 2BR$ , it follows that $BM=CK$ . It is obvious that $\angle ABN = \angle ACK = 120^\circ$ , and also that $AB = AC$ , thus triangles $ABN$ and $ACK$ are congruent. Thus, $AN = AK$ .

As $\angle BAC = 60^\circ$ , it is also true that $\angle NAK = 60^\circ$ , thus proving triangle $ANK$ to be equilateral by SAS.

The Challenge of the Week is a weekly math challenge site run by the University of Washington. It has a collection of interesting problems. In each week, people are to submit solutions. At the end of the week, the solutions are revealed.

I think I’ve managed to solve this week’s challenge. I’ll reproduce the problem here:

Each of $n$ numbers, $x_1, x_2, \cdots x_n$ is selected from the set $\{-1, 1\}$ . Prove that if

$x_1 x_2 x_3 x_4 + x_2 x_3 x_4 x_5 + \cdots x_n x_1 x_2 x_3 = 0$

then $n$ is a multiple of 4.

My solution

I immediately noticed a few things about this problem.

The list of $x_n$ values wraps around, so there really isn’t a start and end to the list. I thought of it as a circle:

A valid group of four is any element and the three elements after it. So for a circle of $n$ elements, there are $n$ groups of four:

So here $x_5$ , circled in red, is the first element of the group. The next three elements circled in blue are the rest of the group. So this group would be $x_5 x_6 x_1 x_2$ .

Because each of $x_n$ is either 1 or -1, the product of the group of four must be either 1 or -1.

For it to equal zero, the number of groups being 1 (positive) and the number of groups being -1 (negative) must be the same. As well as an individual element being either positive or negative, a group of four is also either positive or negative.

This immediately eliminates all circles of size $n$ where $n$ is odd, because if there are $n$ odd groups, there can be no way to split the groups up into equal amounts of positive and negative groups.

Now here’s my approach of proving that $n$ cannot be of the form $4k + 2$ , or in other words when $n$ is even but not divisible by 4.

Let’s consider the circle as initially all positive:

In the above image, a plus sign beside an element refers to the sign of the group of four starting on that element.

The 16 in the middle refers to the value of the whole circle, or the whole expression. We need that to be zero.

Now let’s make one of the elements negative:

Doing this makes all four groups containing that particular element negative. So we have four less positives, and four more negatives. Instead of 16, the total sum is 8.

Do it again and the sum is 0, which is exactly what we need:

Reading from the topmost clockwise, this list would be [1,1,1,-1,1,1,1,1,1,1,-1,1,1,1,1,1].

Changing one element from positive to negative one does not always negate the four groups containing it. Instead, if flips the signs of the four groups.

This is simply because $-1 * -1 = 1$ .

I’ll make an example from the previous diagram:

Here, negating one element actually increased the overall value! It made several negative groups back into positives.

There are four general cases:

What it means is, by changing an element into -1, we flip its four containing groups. Doing so will take away 8 from the total, take away 4 from the total, or add 4 to the total.

Note that there is no case where (----) becomes (++++) because that would mean the head element is already negative, and cannot be made negative again.

Remember that we start with the total being $n$ , and we want the total to be 0. Each step, you can change the total by -8, -4, or 4, each of which is a multiple of 4.

If the total is initially a multiple of 4, it will still be a multiple of 4 after any iteration.

If it’s not already a multiple of 4, nothing can make it a multiple of 4, and there is no way to make it zero by negating elements.

Lucky's Notes

Notes on math, coding, and other stuff

Tag: challenge of the week

Challenge of the Week 05/11/2010