College Math 1102: Mathematical Thinking - HELP NEEDED Using Pidgeon Hole Principal.?

Question

Here is the problem:
You are suppose to use the Pidgeon hole principal for both:

#1) Prove that among any set of 51 positive integers less than 100, theres a pair whose sum is equal to 100.

#2) 289 Points are selected inside a square wth a sdide of one foot. Prove that some subset of 3 of these points can be covered by a square w/ side 1 inch.

If you can help me with on or both of these it would be much appreciated!!! thanks!

Answer 1

100 can be represented in a+b in 50 ways(a+b=b+a) are equal that is 50 pairs
(1+99),(2+98), (3+97),......(49+51),(50+50)
we can chose 50 numbers for 50 pairs such that the sum of any 2 is not 100.
then 51st number has to come from one of the above 50 pairs. We have already chosen a mumber ffrom that pair. Sum of those 2 numbers shall be 100
I hope that clarifies

Answer 2

For #1, pair integers that add up to 100, like 1 with 99, 2 with 98, etc. When done, you have the number 50, and 49 pairs of such integers. If you select a number from a pair, you can't pick the other number without totalling 100. So you can pick a maximum of 50 numbers (one from each pair, and the number 50.) The 51st number forces two of your numbers to add up to 100.

I think #2 is along those same lines. Pair the numbers off so only two points are in every possible square of 1 inch side, and then there's no way to avoid it with 289. 289 feels weird though...I think 145 is sufficient, but I'm not sure. But the same way of thinking should get you started, at least.

Answer 3

(1).
Consider the numbers 1 to 99 inclusive.
Now arrange the numbers so that when two numbers are added together you get a total of 100.

Row 1: 1 + 99 = 100
Row 2: 2 + 98 = 100
Row 3: 3 + 97 = 100
↓ ↓ ↓ ↓ ↓
Row 48: 48 + 52 = 100
Row 49: 49 + 51 = 100
Row 50: 50 + 50 = 100


Let n1 be any number and n2 be any other number (of the 51 positive integers).
So n1 + n2 = Result.
But R = 50.
And Z = 51.
Since Z > R
→ n1 + n2 = 100 (for at least one of the 50 rows).

Notice, with each row two numbers are added together to give 100. There is only a maximum of 50 rows. If you have 51 numbers, then at least one row must have two numbers in it to give 100.

Answer 4

About the second problem. A square with a side of 1 ft consists of 12*12 = 144 squares with a side of 1 inch. Put two points in each little square, so you have put 2 * 144 = 288 points. You have one point more so you put it in a square already occupied by two points. So there is at least one square with a side of 1 inch which contains 3 points.

I think that I have a solution for the first problem:

If the 51 integers are different, lets say that:
a1 < a2 < a3 < . . . < a51 (total 51 integers) with 1 <= a1 <=49 and 51 <= a51 <= 99
Then
a51 + a1 < a51 + a2 < a51 + a3 < . . . < a51 + a50 (total 50 int)
So, we have 51 + 50 = 101 different integers one of them, greater than a51, must be equal to 100.

New message

I thought a better solution for the first problem:

Take 100 boxes. Put in each box the 51 integers in ascending order.
a1 < a2 < . . . < a51
Now take the numbers:
b1 = 100 - a1, b2 = 100 - a2, . . . b51 = 100 - a51
Put every b that not belongs to the set {a1, a2, . . a51} in one of the 49 empty boxes. So you have 2 b's that must belong to the set of a's. Say that bk = ai and bm = an.
But bk = 100 - ak, ai = 100 - ak, ai + ak = 100