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!
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
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.
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.
rawlens said,
May 23, 2007 at 12:22 am
I like your hint rmjarvis. Indiana even gets a chance to rest.
jason_of_west_oz said,
May 23, 2007 at 9:27 am
Thank you Chaim – I now get it thanks to the above post.
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).