   SEARCH HOME Math Central Quandaries & 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!
RD     Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.