Challenge of the Week 02/23/2010

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s