2
$\begingroup$

I'm having difficulty answering (Qb iii)

Question:

(a) Write an expression for the number of sets S which contain 10 elements, each of which is an integer between 1 and 20.

A: There are ${20 \choose 10}$ ways of selecting 10 integers from 1 to 20 where repetition is not allowed and order doesn't matter. If we consider each of these ways a set then the number of set which contain 10 element, each of which is an integer between 1 and 20 is ${20 \choose 10}$.

(b) Let S be a set with the properties described in (a). (i) How many ways are there to order the members of S?

A: There are 10! ways to order the members of S.

(ii) How many subsets of S have size two?

A: There are ${10 \choose 2}$ subsets of size 2.

(iii) For a non-empty subset X ⊆ S, let t(X) denote the sum of the members of X. Prove that there must be distinct subsets A,B ⊆ S, each of size two, such that t(A) = t(B). (Hint: what are the possible values of t(A) and t(B)?)

Where I am at so far

I realised the following:

Consider 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20.

I realised that if you pick any two number say 5 and 13 then

5 + 13 = 18,

6 + 12 = 18,

7 + 11 = 18 etc.

But that's really all I've realised.

$\endgroup$
  • 2
    $\begingroup$ So have you tried using the hint? How many possible values are there for $t(A) $? $\endgroup$ – Jihoon Kang Jul 19 '19 at 13:02
  • 4
    $\begingroup$ The hint is a big help. What's the smallest possible value of $t$? The largest? Do you know the pigeonhole principle? If not, look it up. $\endgroup$ – Ethan Bolker Jul 19 '19 at 13:03
  • 1
    $\begingroup$ Welcome to Stack Exchange! Can you tell us about what you've tried so far and what your thoughts are? This looks like a good question for this site, but you should tell us more about where you're at with this problem. Thank you! $\endgroup$ – Tanner Swett Jul 19 '19 at 13:03
  • $\begingroup$ @EthanBolker I've learnt about the Pigeonhole Principle but I'm not seeing how I can apply it here. $\endgroup$ – CubbyKushi Jul 19 '19 at 13:33
  • $\begingroup$ Be careful, $S$ is meant to be your $\binom{20}{10}$ sets, so the number of 2-subsets of $S$ should be $\binom{\binom{20}{10}}{2}$. $\endgroup$ – vonbrand Jul 19 '19 at 14:17
1
$\begingroup$

Even more explicit hint... the smallest possible value of $t(A)$ would happen when the subset is $\{1,2\}$ since this is the set using the two smallest available elements while the largest possible value of $t(A)$ would happen when the subset is $\{19,20\}$ since this is the set using the two largest available elements.

The possible outcomes of $t(A)$ are then $3,4,5,\dots,37,38,39$

You correctly noted however that there are $\binom{10}{2}=45$ distinct two-element subsets of $S$ however

And if we compare the number of possible two-element subsets of $S$ to the number of possible values of $t(A)$ we see that one is larger than the other which means...

$\endgroup$
  • $\begingroup$ I'm a bit confused by this question. If $A = \{1,2\}$ so that $t(A) = 3$, then what can $B$ be so that $t(B) = 3$ also? $\endgroup$ – battletwink69 Jul 19 '19 at 13:20
  • 1
    $\begingroup$ @battletwink69 There won't be a $B$ different than $A$ such that $t(B)=3$ as well, but noone said that there must be two sets whose sum is both specifically $3$, just that there are two sets who have the same sum. For example $\{4,5\}$ and $\{3,6\}$. Which sets those are and which sum that is will depend upon what $S$ actually is, we won't know what that sum is or which sets those are without knowing $S$, but we will be able to assert that they must exist and have the same sum whatever that happens to be. $\endgroup$ – JMoravitz Jul 19 '19 at 13:28
  • $\begingroup$ Gotcha, thanks. $\endgroup$ – battletwink69 Jul 19 '19 at 13:29
  • $\begingroup$ @JMoravitz I've understood most of what you've said in your response to battlewink69 but I still don't know how to prove this statement. $\endgroup$ – CubbyKushi Jul 19 '19 at 13:47
  • $\begingroup$ @CubbyKushi if I have four pigeons occupying three holes, each pigeon will fit into one hole, can you see why there must be at least one hole with more than one pigeon in it? If I have $n$ numbers $x_1,x_2,\dots,x_n$ each of which are one of $m$ values $\{1,2,3,\dots,m\}$ where $n>m$ do you see why there must be at least two numbers which are the same? This is referred to as the pigeonhole principle. Finally, do you see what this has to do with our question? We saw that there are $45$ subsets we are interested in the value of but less than $39$ possible values they could be, so... $\endgroup$ – JMoravitz Jul 19 '19 at 13:59
0
$\begingroup$

New proof:

Observe that {1, 2} will have the smallest sum which is 3 and {19, 20} will have the largest sum which is 39.

Now any 2-subset of S will be greater than or equal to 3 and less than or equal to 39. Since we have 45 2-subsets of S and only 37 possible sums they will be mapped to, by the Pigeonhole Principle there will be at least two subsets with the same sum.

End of proof.

$\endgroup$
  • $\begingroup$ In the context of finite discrete sets, It should be obvious that the 1-element subset with the smallest sum is the subset containing the minimum. It follows that the 2-element subset with the smallest sum is the subset containing the minimum and the minimum of the set with the original minimum removed. This continues by induction to saying the $n$-element subset with the smallest sum is the one with the $n$-smallest elements from the set. This usually isn't bothered to be proven since it is so intuitive. $\endgroup$ – JMoravitz Jul 19 '19 at 14:56
  • $\begingroup$ Now... it follows that since $\{1,2\}$ is the 2-element subset with the smallest sum from the set $\{1,2,3,\dots,20\}$ that any possible 2-element subset from $S$ must have a sum at least as large as $\{1,2\}$ had since it would also have been a 2-element subset from $\{1,2,3,\dots,20\}$ since $S$ is a subset of that. The same logic applies when talking about subsets with the largest sum., so we have the smallest possible sum is $3$ and the largest possible sum is $39$ $\endgroup$ – JMoravitz Jul 19 '19 at 14:57
  • $\begingroup$ @JMoravitz What do you think of my new proof? $\endgroup$ – CubbyKushi Jul 19 '19 at 15:10
  • $\begingroup$ You don't need to break into cases based on whether or not $S$ includes the extreme values, it is not necessary. Regardless of whether or not $S$ includes the extreme values any $2$-element subset of $S$ will also be a $2$-element subsets of the 20-element set $\{1,2,3,\dots,19,20\}$, and as a result have a sum at least as large as $3$. Similarly any $2$-element subset of $S$ is at most as large as $39$. $\endgroup$ – JMoravitz Jul 19 '19 at 15:13
  • $\begingroup$ Now... it is possible that there are some sums in the range $3,39$ that aren't possible, for example if $S$ does not include $1$ you can't have 3... We don't care! It doesn't matter! We can still say with certainty that every possible value is among $\{3,4,5,\dots,38,39\}$. We are not saying that every value among $\{3,4,5,\dots,38,39\}$ is a possible value, that is a different statement and one that will be false. So, some of the holes aren't used by pigeons because a raccoon happens to be there. So what. We can still say that there is at least one hole that at least two pigeons are in. $\endgroup$ – JMoravitz Jul 19 '19 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.