Math CentralQuandaries & Queries


Question from Shankar, a teacher:
The boxes of an n * (n+1) table ( n rows and n+1 columns) are filled with integers.
Prove that one can cross out several columns ( not all of them !) so that after this operation
all the sums of the numbers in each row will be even.

Nice! I'm certainly not going to spoil this for you by just giving you the answer. The clues you get are:

  1. Dirichlet's pigeonhole principle states that if N things map to fewer than N targets, some target gets hit at least twice.

  2. Use this to show that some pattern of odd/even sums is reached for more than one pattern of left/crossed-out columns.

  3. Use this to get the answer.

Once you have solved your original problem, use the same idea to solve:

Given any set of 10 numbers, all under 1000, there exist two disjoint subsets with the same sum.

Good Hunting!

About Math Central


Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.
Quandaries & Queries page Home page University of Regina PIMS