1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Neporo4naja [7]
3 years ago
9

Let A be a subset of {1, 2, . . . , 25} with |A| = 9. For any subset B of A, denote by SB, the sum of the elements in B. Prove t

hat, no matter which elements A consists of, we can always find distinct subsets C and D of A such that |C| = |D| = 5 and SC = SD. (Hint: How many 5-element subsets of A are there? What is the largest 5-element sum?)
Mathematics
1 answer:
Shalnov [3]3 years ago
7 0

Answer:

Step-by-step explanation:

To solve this problem, we are going to apply the pigeon hole principle, which is as follows:

If m pigeons occupy n pigeon holes and m>n, then there must be at least one pigeonhole that holds more than one pigeon.

To apply this principle, we'll work the problem out to have a pigeon-pigenhole set up.

Consider the set \{1,\dots, 25\}. We want to define the posible values of SB for any B that is a subset of A. The lowest value of Sb would be considering B = \{1,2,3,4,5\}. In this case, the sum is 15. The highest value of SB would be when we consider the set B = \{21,22,23,24,25\}. In this case SB = 115. So now, consider A as stated and B any subset of A that has 5 elements. Since A has 9 elements and B has 5, we have \binom{9}{5} = \frac{9!}{4!5!}=126 different sets of 5 elements. Also, we have that

15\leq S_b \leq 115.

Note that given a B, SB is necessarily an integer between 15 and 115, and that given a B, we can assign its sum SB directly by summing up. Consider the different values of SB as pigeonholes and each 5-elements set as pigeons. We have in total 101 possible values (115-15 +1 = 101). Since each set B has a SB, then we are in the case in which we have more pigeons than pigeonholes, so it must happen that there is at least one pigeon hole (value of SB) that has more than one pigeon.

You might be interested in
If you bought a stock last year for a price of $77, and it has risen 17.9% since then, how much is the stock worth now
sladkih [1.3K]

Answer:

$90.783

Step-by-step explanation:

4 0
3 years ago
Please please help me
ohaa [14]

Answer:

b) 43 degrees

Step-by-step explanation:

7 0
3 years ago
Read 2 more answers
I will venmo if someone can please help me
shutvik [7]

Answer: 14.967

Step-by-step explanation:

Use Pythagorean Theorem to find the missing length.  

a² + b² = c²        

x² + 10² = 18²      

x² + 100 = 324         [Subtract 100 from both side]  

          x²= 224        

      √x² = √224     [solve the square root from both sides]

        x   ≈  14.967

4 0
3 years ago
A discount voucher offering 15% off is used to pay a bill. After using the voucher, the bill is reduced to £36.72.
Elena-2011 [213]

We can use the is/of=p/100 method for this problem. Since it's 15% off, this would mean that the bill is 85% of what it was initially. Plug the values into the is/of=p/100 formula.

36.72/x = 85/100

Solve  for x.

x=36.72/0.85

x=43.2

So, the bill was $43.20 before applying the voucher discount of 15% off.

3 0
3 years ago
Read 2 more answers
German if each example of positive or negative $25 is it in 0 feet below sea level or 4 degrees below zero​
Mazyrski [523]

Answer:

positive

negative

negative

Step-by-step explanation:

7 0
3 years ago
Other questions:
  • Find the new amount.<br> 8 meters increased by 25% is <br> meters.
    6·2 answers
  • A rod was cut into 3 piece the length of the 3 piece are in the ratio of 5 : 3 :2 if the shortest is 25cm how long was the rod ​
    7·1 answer
  • If carissa dalton has a $234,000 home insured for $175,000, based on the 80 percent coinsurance provision, how much would the in
    7·1 answer
  • PLeAsE hElP<br> ASAPPP<br> :/<br> *Will give 25 points and Brainliest...*
    10·1 answer
  • Triangle A B C is shown. Angle A C B is a right angle. An altitude is drawn from point C to a point on side A B to form a right
    11·2 answers
  • Helpppp pleaseeee , thank you .
    13·1 answer
  • Y=4x+rx+6 solve for x
    9·1 answer
  • Name 3 pairs of adjacent angles and 3 pairs of vertical angles.​
    5·1 answer
  • A teacher asks three different students to draw a triangle with the angles 30o, 70o, and 80o. If they draw the angles correctly,
    5·1 answer
  • Solve for x.
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!