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

RSS feed for comments on this post · TrackBack URL

Leave a Comment

You must be logged in to post a comment.

The Math Factor Podcast Website

Quality Math Talk Since 2004, on the web and on KUAF 91.3 FM

A production of the University of Arkansas, Fayetteville, Ark USA

Download a great math factor poster to print and share!

Got an idea? Want to do a guest post? Tell us about it!

Heya! Do us a favor and link here from your site!