Question

In: Advanced Math

11. (6 Pts.) Show that if we split any 11 numbers in 5 sets, then there...

11. (6 Pts.) Show that if we split any 11 numbers in 5 sets, then there exists one set that contains a subset such

that the sum of its elements is a multiple of 3.

Solutions

Expert Solution

Let be any integers.

Case I: If some divides one of , say , then the set that contains has as its subset, and the sum of all elements in is just , a multiple of .

Case II: Suppose for all : Since sets contains integers, by Pigeon-hole principle, at least one of these sets contains at least of these integers . Say is such a set and . Since for all , we have . Thus, the sum of the elements in the subset is a multiple of .

Case III: Suppose for all : Since sets contains integers, by Pigeon-hole principle, at least one of these sets contains at least of these integers . Say is such a set and . Since for all , we have . Thus, the sum of the elements in the subset is a multiple of .

Case IV: Suppose for at least one of , and for at least one of :

Case IVa If one of the sets contain an and , then it has a two-elements subset whose elements sum is .

Case IVb Since sets contains integers, by Pigeon-hole principle, at least one of these sets contains at least of these integers . Say is such a set and . Either for all , or for all . Thus, we have . Thus, the sum of the elements in the subset is a multiple of .

Since these are all the possible cases, we have proved the required statement.

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

Using the following sample data; 6, 7, 11, 6, 11, 5, 15, 11, 5; Compute the...

Using the following sample data; 6, 7, 11, 6, 11, 5, 15, 11, 5; Compute the sample standard deviation using either the computing formula or the defining formula. A. 3.6 B. 3.5 C. 3.4 D. 3.3

Logic & Sets (Proofs question) Show that complex numbers cannot be ordered in a way that...

Logic & Sets (Proofs question) Show that complex numbers cannot be ordered in a way that satisfies our axioms. Axioms for order: 1. if x is less than/equal to y and w is greater than zero, then wx is less than/equal to wy 2. for w, x, y, z w is less than/equal to x, y is less than/equal to z then w + y = x + z if and only iff w = x and y = z

7. (16 pts) a. Show that 11 is a primitive root of 13. b. What is...

7. (16 pts) a. Show that 11 is a primitive root of 13. b. What is the discrete logarithm of 4 base 11 (with prime modulus 13)?

we have defined open sets in R: for any a ∈ R, there is sigma >...

we have defined open sets in R: for any a ∈ R, there is sigma > 0 such that (a − sigma, a + sigma) ⊆ A. (i) Let A and B be two open sets in R. Show that A ∩ B is open. (ii) Let {Aα}α∈I be a family of open sets in R. Show that ∪(α∈I)Aα is open. Hint: Follow the definition of open sets. Please be specific and rigorous! Thanks!

6) There are 5 boxes. In each box there are 5 tickets labelled with the numbers...

6) There are 5 boxes. In each box there are 5 tickets labelled with the numbers 1,2,3,4,5. An experiment is to draw one number at random from each of the ﬁve boxes. Calculate the following probabilities using a calculator, but show some work. a) P(no two numbers alike). b) P(exactly two alike). (example 11234) c) P(exactly three alike). (example 11123) d) P(exactly four alike). (example 11112) e) P(two pair). (example 11223) f) P(the number 4 comes up at least once)

please show me step by step? Chapter 11 Exercise 11-8 Volume Trade-Off Decisions [LO11-5, LO11-6] Barlow...

please show me step by step? Chapter 11 Exercise 11-8 Volume Trade-Off Decisions [LO11-5, LO11-6] Barlow Company manufactures three products—A, B, and C. The selling price, variable costs, and contribution margin for one unit of each product follow: Product A B C Selling price $ 180 $ 270 $ 240 Variable expenses: Direct materials 24 80 32 Other variable expenses 102 90 148 Total variable expenses 126 170 180 Contribution margin $ 54 $ 100 $ 60 Contribution margin ratio...

Use the pumping lemma to show that the following languages are not regular (c) (5 pts)...

Use the pumping lemma to show that the following languages are not regular (c) (5 pts) Let Σ = {0, 1, −, =} and SUB = {x = y − z | x, y, z are binary integers, and x is the result of the subtraction of z from y}. For example: 1 = 1 − 0, 10 = 11 − 01 are strings in SUB but not 1 = 1 − 1 or 11 = 11 − 10.

For any r, s ∈ N, show how to order the numbers 1, 2, . ....

For any r, s ∈ N, show how to order the numbers 1, 2, . . . , rs so that the resulting sequence has no increasing subsequence of length > r and no decreasing subsequence of length > s.

Make up three different data sets with 5 numbers each that have the following characteristics; the...

Make up three different data sets with 5 numbers each that have the following characteristics; the word "set" means there will be 2 lists of 5 numbers in each set. List the numbers in each dataset. For example in part a) you will have a list of 5 numbers with a mean of X, and the second list of 5 numbers will have the same mean. However, the two lists of 5 numbers need to have different standard deviations. That...

Question 1 (of 11)Question 2 (of 11)Question 3 (of 11)Question 4 (of 11)Questions 5 - 6...

Question 1 (of 11)Question 2 (of 11)Question 3 (of 11)Question 4 (of 11)Questions 5 - 6 (of 11)Questions 7 - 9 (of 11)Questions 10 - 11 (of 11) Save & ExitSubmit Time remaining: 0:51:30 Problem 7-5A Determine depreciation under three methods (LO7-4) [The following information applies to the questions displayed below.] University Car Wash built a deluxe car wash across the street from campus. The new machines cost $270,000 including installation. The company estimates that the equipment will have a residual...

Subjects