Puzzle time - adding, multiplying, grouping

[jon-nyc]

Forty-two positive integers (not necessarily distinct) are written in a row.  Show that you can put plus signs, times signs, and parentheses between the integers in such a way that the value of the resulting expression is evenly divisible by one million.

[Klaus]

Hm, interesting. My first idea was that the number of combinations is greater than a million, but that doesn't imply that one of those yields a number that is divisible by a million.

[Klaus]

Just an example, but I wondered how to do this when all numbers are 1.

I think you can form 2s as (1+1) and 5s as (1+1+1+1+1). If you do multiplication for the rest, you need 7*6=42 ones.

I also wondered what the biggest number is one can produce that way when all numbers are 1.

At first I thought this would be 2^21. But it turns out that 3^14 is bigger.

[Klaus]

Ah. So here’s my theory. With two numbers, you can always produce a number that is divisible by 2. With five numbers, you can always produce a number divisible by 5. Then the product of all these numbers (6 numbers divisible by 2 and 6 numbers divisible by 5) must be divisible by 1000000.

Getting a number divisible by 2 with two numbers is easy. If both have the same parity, add them. Otherwise, multiply.

For five numbers, it's not so obvious. But it is sufficient to consider only the last digit of each number, and the order of numbers doesn't matter, so it's not that many combinations. I can't be bothered to figure it out right now, though. I guess I could write a computer program to try them all out.

If that doesn't work, the next strategy would be to get a number divisible by 10 with 7 numbers.

[jon-nyc]

I finally have a proof that you can always get a multiple of 5 by summing a subset (or the entire set) of 5 numbers.

Hint: Look at cumulative sums, (x1, x1+x2, x1+x2+x3, …) think mod 5 and the pigeonhole principle.