 |
| ||
| |||
|
| Math Central | Quandaries & Queries |
|
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:
- Dirichlet's pigeonhole principle states that if N things map to fewer than N targets, some target gets hit at least twice.
- Use this to show that some pattern of odd/even sums is reached for more than one pattern of left/crossed-out columns.
- 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.