## CM. Crossing the Bridge

Save Indiana, his girlfriend, his father and his father’s sidekick from certain doom! They must cross a bridge across a gorge in no more than one hour!

This wonderful puzzle is from The Art and Craft of Problem Solving, by Paul Zeitz. Unfortunately, we don’t know the answer!

1. ### strauss said,

May 21, 2007 at 12:01 am

I wonder if I changed last week’s problem as I answered it?

The puzzle, originally, was if you have N numbers, to show that some sum of some of them has total to a multiple of N.

I think I might have changed this, in midstream, to

If you have N numbers, show that some sum of them has to total to a multiple of N-1.

This is even easier, and in fact generalizes. For any M less than or equal to N, the pigeonhole principle gives us the proof, though we need a slight twist when M=N (i.e. for the original problem):

For the N numbers a,b,c,… we first list the sums a, a+b, a+b+c, etc.

Now then, if we consider M less than N, these sums can only total to 0, 1, 2, …, (M-1) (mod M) As there are N pigeons (namely a, a+b, etc) and M holes (0,1,.., M-1) at least two pigeons have to go in the same hole.

Suppose a+b+c and a+b+c+d+e are the same mod M. Then their difference, d+e, is 0 mod M, and so is a multiple of M.

If M actually equals N, as in the original problem the argument doesn’t necessarily work and we need a slight variation on the proof — the proof above will work, unless the N pigeons exactly fill up the N holes 0,1, 2, … (N-1). But then some pigeon has to fill up hole 0; that is, some sum has to total 0 mod N, and again we are done.

2. ### rmjarvis said,

May 22, 2007 at 7:56 am

I won’t give the answer just yet, but I’ll give a hint. You need to get dad and his sidekick to go across together.

3. ### rawlens said,

May 23, 2007 at 12:22 am

I like your hint rmjarvis. Indiana even gets a chance to rest.

4. ### jason_of_west_oz said,

May 23, 2007 at 9:27 am

Thank you Chaim – I now get it thanks to the above post.

5. ### Shawn said,

November 19, 2011 at 9:54 pm

I think I have a counterexample to the some sum of some rule. Consider the following set: {e}. The only number in this set is e, so n = 1. The only possible sum of x numbers, where 0 < x <= 1 and x ? N, in that set is e. Neither -e nor 0 is a member of the set, so that sum cannot equal 0 (n-1).