Saturday
April 19, 2014

Homework Help: Discrete mathematics

Posted by Lolita on Wednesday, June 22, 2005 at 9:00pm.

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

Answer this Question

First Name:
School Subject:
Answer:

Related Questions

Maths - Pigeon-hole principle - Using the Pigeon-hole principle... 91 five-digit...
geomatry - a sequence begins -4,1,6,11 find the rule that generates the sequence...
math - What strategy did you use in solving this problem? 22. Suppose that you ...
geomatry deductive reasoning - a sequence begins -4,1,6,11 find the rule that ...
geomatry deductive reasoning - a sequence begins -4,1,6,11 find the rule that ...
Discrete math - I need to find the coefficient of x^18 y^32 in (x+y)^50. I ...
Arithmetic Sequence - A child organizes animal blocks in rows on the ground. ...
Discrete Math - Could someone help me with this induction proof. I know its true...
Discrete Math - An arithmetic sequence begins, 116, 109, 102 Find the 300th ...
HELP-PROBLEM SOLVING IN MATHEMATICS - a piece of wire of length 136(pai) is cut ...

Search
Members