Comments on: CM. Crossing the Bridge

By: Shawn

Shawn — Sun, 20 Nov 2011 02:54:35 +0000

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

By: jason_of_west_oz

jason_of_west_oz — Wed, 23 May 2007 15:27:56 +0000

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

By: rawlens

rawlens — Wed, 23 May 2007 06:22:36 +0000

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

By: rmjarvis

rmjarvis — Tue, 22 May 2007 13:56:00 +0000

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.

By: strauss

strauss — Mon, 21 May 2007 06:01:56 +0000

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.