Tags:
1. May 17, 2005

### tongos

i have 69 distinct positive whole numbers between 1 and 100. i pick out 4 integers a,b,c,d. prove that i can always pick out 4 integers such that a+b+c=d. can this always hold true with 68 positive integers?

2. May 17, 2005

### neurocomp2003

i'm assuming that you don't have to pick out a+b+c=d all the time but there exists a quadruple in your set of 69.

The proof relies on teh pigeon hole principle:
[1]let a and d be the smallest and largest of your set of 69 respectively.
[2]find the number of pairs taht b & c can be within 1-100 and the set of 69.
[3]Compare these two values.

3. May 18, 2005

### tongos

thanks! I seem to know what to do now. The fun part about this problem is the pigeon hole principle. I love math problems like this one.
one of my favorite math problems (though simple) is this:
Prove that at any party, two friends at that party must have the same amount of friends present there (given ofcourse that if someone is a friend to you, you are friend to that someone).

4. May 18, 2005

### neurocomp2003

if you need a good book to further your proving skillz pick up
"problem solving" by Larson.