Discrete mathematics

posted by .

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

Respond to this Question

First Name
School Subject
Your Answer

Similar Questions

  1. Algebra

    How do I work this problem, it is not a homework problem but a problem similar to a homework problem. I know i need to factor the left side of the problem. here is what I have so far.. x^2-2x+1=7 x^2-2x+1-7=7-7 x^2-2x-6=0 here is where …
  2. Algenra

    How do I work this problem, it is not a homework problem but a problem similar to a homework problem. I know i need to factor the left side of the problem. here is what I have so far.. x^2-2x+1=7 x^2-2x+1-7=7-7 x^2-2x-6=0 here is where …
  3. Maths - Pigeon-hole principle

    Using the Pigeon-hole principle... 91 five-digit numbers are written on a blackboard. Prove that one can find three numbers on the blackboard such that the sums of their digits are equal.
  4. Calculus

    Show that the function f(x)= x^(3) +3/(x^2) +2 has exactly one zero on the interval (-infinity, 0). So far this is what I have: 0=x^3 + 3/(x^2) +2 -2= (1/x^2)(x^5 + 3) -2x^2= x^5 +3 But now I'm stuck. I also am not sure if this is …
  5. Math Statistics

    An investigational drug study is being conducted. The initial screening phase needs to include enough people so that the final (approved) group has at least 10 patients. The probability of a person being approved for the study is .80. …
  6. math

    What strategy did you use in solving this problem?
  7. Discrete Math

    I have a review problem I am having problems with. This is the problem: Be able to show the function, g(x) is O(f(x)) numerically as we have done in class Use the definition of O-notation to prove that 2x^2+3x+4 is O(x^2) (Do not use …
  8. geomatry

    a sequence begins -4,1,6,11 find the rule that generates the sequence. Then give the 5oth term is the sequence. What type of reasoning inductive or deductive, do you use when solving this problem?
  9. Discrete math

    I need to find the coefficient of x^18 y^32 in (x+y)^50. I understand that we have to use the binomial theorem. I know how to find the coefficient for example x^18 but here we have "x" as well as "y" which I have no idea about.
  10. Mathematics

    if 8; 2x; 2y form an arithmetic sequence and 2x; 2y; 36 form a geometric sequence determine the values of x and y I feel like I am going around in circles on this problem. For the AP i have the following formulas: (1) d=(2y-8)/2 (2) …

More Similar Questions