I need help solving this problem, I have followed the sequence forward and backwards but can't seem to find the solution. I believe it's the pigeon hole theorem. Here's the problem;
Let A be any set of twenty integers chosen from the arithmetic progression 1, 4, 7, ...,100. Prove that there must be two distinct integers in A whose sum is 104.
100 = 1 + 3(n-1) = 3n -2,
n = 34
Totally, there are 34 terms from
1,4,..,100
Among them there are 16 pairs can from 104 are:
1
4, 100
7, 97
10, 94
...
46, 58
49, 55 (=3*16+1, 103-3*16)
52
as (boy girl)
If no two chosen numbers whose sum
is 104, then we only can choose one
from the above pairs.
That is, we can at most choose
16+1+1 = 18 numbers among 34 where
no two whose sum is 104.
However, we choose 20 > 18 numbers
so at least two with sum 104.
This answer may be late, since I saw
this question a short while ago.
Kenny
Well, Kenny, it seems like you've already found the solution to the problem! You've got it all worked out using the pigeonhole principle. However, I have to say, those pigeons sure do make math a little bit stranger. Just remember, when you're dealing with pigeons, holes, and arithmetic progressions, always expect a twist! Keep up the great work, Kenny!
To solve this problem, we can use the pigeonhole principle, as you mentioned. The pigeonhole principle states that if you have more pigeons than pigeonholes, then at least one of the pigeonholes must contain more than one pigeon. In this case, the pigeons are the integers chosen from the arithmetic progression, and the pigeonholes are the possible sums of two distinct integers.
Given that A is a set of twenty integers chosen from the arithmetic progression 1, 4, 7, ..., 100, let's assume that there is no pair of distinct integers in A whose sum is 104. We want to prove that this assumption leads to a contradiction.
First, let's find the value of n, the number of terms in the arithmetic progression. By using the formula for the nth term of an arithmetic sequence, we can write:
100 = 1 + 3(n-1)
99 = 3(n-1)
33 = n-1
n = 34
So we have a total of 34 terms in the arithmetic progression.
Next, let's consider the pairs of distinct integers whose sum is 104. Since the first term in the arithmetic progression is 1, and the common difference is 3, we can generate such pairs by adding the first term to multiples of the common difference. These pairs are:
1 + 3(0), 1 + 3(16)
1 + 3(1), 1 + 3(17)
1 + 3(2), 1 + 3(18)
...
1 + 3(15), 1 + 3(31)
Simplifying these pairs, we get:
1, 100
4, 97
7, 94
...
46, 58
49, 55
There are a total of 16 pairs.
Now, if our assumption is true and there are no two distinct integers in A whose sum is 104, then we can choose at most one integer from each pair. Therefore, the maximum number of integers we can choose from these pairs is 16.
However, our initial assumption states that we have chosen a set of twenty integers from the arithmetic progression, which is more than the maximum number of integers we can choose from the pairs. This leads to a contradiction, as we cannot have more pigeons (in this case, integers chosen from the arithmetic progression) than pigeonholes (in this case, possible sums of two distinct integers).
Therefore, our assumption that there are no two distinct integers in A whose sum is 104 must be false. In other words, there must exist at least two distinct integers in A whose sum is 104.
To solve this problem, we can use the idea behind the pigeonhole principle. The pigeonhole principle states that if there are more pigeons than pigeonholes, then there must be at least one pigeonhole with more than one pigeon.
In this problem, the pigeons are the twenty integers chosen from the arithmetic progression 1, 4, 7, ..., 100, and the pigeonholes are the possible sums of these integers.
To start, we need to find the number of terms in the arithmetic progression 1, 4, 7, ..., 100. We can notice that the difference between consecutive terms is always 3. So, we can use the formula for the nth term of an arithmetic sequence:
nth term = first term + (n - 1) * common difference
In this case, the nth term is 100, the first term is 1, and the common difference is 3. Plugging these values into the formula, we get:
100 = 1 + 3(n - 1)
Simplifying this equation gives:
99 = 3n - 2
Solving for n, we find n = 34.
Therefore, there are 34 terms in the arithmetic progression 1, 4, 7, ..., 100.
Now, let's identify the pairs of integers from this arithmetic progression that can add up to 104. Starting from the first term:
1
4, 100
7, 97
10, 94
...
46, 58
49, 55 (= 3 * 16 + 1, 103 - 3 * 16)
52
As we can see, there are a total of 16 pairs that can add up to 104.
If there were no two chosen numbers whose sum is 104, we would only be able to choose one element from each of the above pairs. So, we would have at most 16 + 1 + 1 = 18 numbers chosen from 34, where no two have a sum of 104.
However, since we have chosen 20 numbers (more than 18), by the pigeonhole principle, there must be at least two chosen numbers whose sum is 104.
In conclusion, the pigeonhole principle guarantees that there must be two distinct integers in the set A, chosen from the arithmetic progression 1, 4, 7, ...,100, whose sum is 104.