# A little puzzle

This came up as sub-problem during Young-Han’s group meeting today and we mulled over it for a few minutes but didn’t come up with a non-ugly answer. I’m sure, given the number of Real Mathematicians ™ who read this, that someone out there knows of an “obvious” explanation.

Suppose I give you p integers in an arbitrary order (where p is prime). While maintaining the order and using only addition, multiplication, and parenthesis, is it always possible to make an expression which evaluates to 0 mod p?

I think it’s true, but I’m sure there’s some special property of $\mathbb{F}_p$ that I have forgotten. I guess further generalizations would include whether or not it’s possible for arbitrary $p$ (not necessarily prime), how many elements of an arbitrary field you would need, and so on. I’d ask this on MathOverflow but… meh. It’s probably a homework problem.

## 8 thoughts on “A little puzzle”

1. Not only is it true, but I don’t think p has to be prime.

If you an find a set of consecutive elements that add to 0 mod p, you can add that, put it in parentheses, and multiply it by everything else. We’ll show such a set always exists.

Consider the sums:
a_1
a_1+a_2
a_1+a_2+a_3

a_1+a_2+…+a_p

If these p sums are all different mod p, one of them must be 0 mod p. If they’re not all different, take any two that are the same, and their difference is a sum of consecutive integers equal to 0 mod p. Either way, we’re done.

(Now why can’t I answer questions related to my research this quickly?)

• Also, p is necessary as well as sufficient (since a sequence of (p-1) 1’s is no good).

• Baba says:

Would (1-1).(1+1+…+1) be acceptable when we have(p-1) 1’s?

• Baba says:

Yes, I just noticed that subtraction is not allowed: sorry about that. But if p is not a prime, say p = 6, then

(1+1).(1+1+1)

is 0 mod 6, and so (p-1) 1’s might still massaged into 0 mod p.

• Well that certainly is simpler than the algorithmic road we were treading down…

This site uses Akismet to reduce spam. Learn how your comment data is processed.