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.

Advertisements

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?)

  2. Pingback: Solving Puzzles « Information Ashvins

  3. Pingback: Solving Puzzles « Information Ashvins

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