Lec 1
Q1.
How many three-digit integers there are so that the sum of the three digits is 24 where all the digits are distinct?
Simple if we split the number in certain order, say, dictionary order and descending order..,
$$ 24 = 9+8+7 $$and we can’t do anything more,
It should be $3!=6$
Q2.
$$ 18=9+8+1=9+7+2=9+6+3=9+5+4\\ =8+7+3=8+6+4\\ =7+6+5 $$How many three-digit integers there are so that the sum of the three digits is 18 where all the digits are distinct
again they are different, so it is $7*3!=42$
What about if the sum of the three digits is 17, and all the digits are distinct?
Here is something different,
$$ 17=9+8+0=9+7+1=9+6+2=9+5+4\\ =8+7+2=8+6+3=8+5+4\\ =7+6+5 $$0 can’t be placed in the first position. So it is $8*3!-2!=46$
Lec 2
Q1.
$\binom{n}{k}=\binom{n}{n-k}$
In conbinactorial method, it is same to map a subset to its complement.
Proof of injective and subjective,
- For two different subsets, the complements are differnt
- From any complement, you can find the original subset
So it is an one-to-one and onto mapping
Q2.
The restaurant prepared 4 mains and 6 sides. If each lunch box can consist of 2 mains and 3 sides, how many different types of lunch boxes are there? What if each lunch box consists of at most 2 mains and at most 3 sides, and each lunch box should consists of at least one main and at least one side, how many there are? What if in addition each lunch box should have at least one main and at least one side?
1.
$$ \binom{4}{2}\binom{6}{3}=120 $$2.
$$ \left(\binom{4}{2}+\binom{4}{1}\right)\left(\binom{6}{3}+\binom{6}{2}+\binom{6}{1}\right)=16\cdot41 $$3.
$$ \left(2^4-1\right)\left(2^6-1\right)=15\cdot63 $$Q3.
I have 5 math books, 3 history books, and 4 computer science books that I want to arrange on a bookshelf in such a way that all the books dealing with the same subject are together on the shelf. How many different ways can I do this?
3 groups,
$$ 3!\cdot5!\cdot3!\cdot4! $$Q4.
How many permutations are there of 5 E’s, 4 N’s, and 6 U’s?
本质就是binomial coef
$$ \binom{15}{4,5,6} $$HW1
Q1.
Vandermonde’s identity,
$$ \sum_{k=1}^6 \binom{7}{k}\binom{6}{k}=\sum_{k=0}^k\binom{7}{k}\binom{6}{6-k}\,-1=\binom{13}{6}-1 $$Q2.
How many ways are there to choose a k-element subset of {1, 2, . . . , n}such that exactly one pair of the elements has a difference of two, and all other pairs have a difference of at least three?
Let,
$$ d_i = a_{i+1}-a_i \\ d_0 = a_1-1 \ge 0\\ d_{k} = n-a_k \ge 0\\ \sum_{i=0}^k d_i = n-1 $$Notice one of $d_1,d_2,...,d_{k+1}$ is equal to 2, others are greater or equal than 3,
$$ d_0+d_{k}+\sum_{i\neq j,i=1}^{k-1} d_i =n-3 \\ y_0+y_k+\sum_{i\neq j,i=1}^{k-1} y_i = n-3-3(k-2)=n-3k+3 $$So at last, choose one of the $d$ from $d_1,d_2,...,d_{k-1}$
$$ (k-1)\binom{n-3k+3+(k-1)}{k-1} $$Lec3
Q1.
$$ 2^4\cdot(-1)^3\binom{12}{4,5,3} $$What is the coefficient of $x^4y^5z^3$ in $(2x + y− z)^{12}$?
Q2.
How many ways to put 10 identical balls into 4 identical jars? How many ways to put 10 different balls into 4 different jars? How many ways to put 10 identical balls into 4 different jars? Assume in both cases, a jar could be empty
1.
Pure counting,
$$ 10 = 10 + 0 + 0 + 0 \\= 9+1+0+0 \\=8+2+0+0=8+1+1+0 \\=7+3+0+0=7+2+1+0=7+1+1+1 \\=6+4+0+0=6+3+1+0=6+2+2+0=6+2+1+1 \\=5+5+0+0=5+4+1+0=5+3+2+0=5+3+1+1=5+2+2+1 \\=4+4+2+0=4+4+1+1=4+3+3+0=4+3+2+1=4+2+2+2 \\=3+3+3+1=3+3+2+1 $$23.
But It’s better to use another way to coutn again, very easy to drop some of the partition
2.
$$ 4^10 $$3.
$$ \binom{13}{3} $$Q3.
$$ \binom{13}{3} $$How many non-negative integer solutions are there to the equation x1 + x2 + x3 + x4 = 10?
Q4.
$$ \binom{9}{3} $$How many positive integer solutions are there to the equation x1 + x2 + x3 + x4 = 10?
Q5.
How many non-negative integer solutions are there to x1 + x2 ≤ 9
same as
$$ x_1+x_2+x_3 = 9, x_i\ge0 $$$$ \binom{11}{2} $$Q6.
How many positive integer solutions are there to the equation x1 + x2 + x3 + x4 = 100 such that x1 + x2 < 50?
It’s almost symmetric.
$x_1+x_2<50$ is in the same as $x_3+x_4>50$ except for one uncounted $x_1+x_2=50$ . And they form the whole solutions.
Also there is a different one-to-one and onto mapping between $x_1+x_2<50,x_3+x_4>50$ $(x_1,x_2,x_3,x_4)$ and $(x_3,x_4,x_1,x_2)$ except for $x_1=x_3$ and $x_2=x_4$. But you see? This is in our exclusion, because that means $x_1+x_2=50$.
So we can kick off the special case first,
$$ \binom{99}{3}-\binom{49}{1}^2 $$Then divide it by 2.
$$ \frac{\binom{99}{3}-\binom{49}{1}^2}{2} $$Q7.
How many ways to arrange the letters A, B, C, D,E so that A and B are not adjacent?
So we arrange C D E first,
$$ 3!\cdot4\cdot3 $$Q8.
$$ \binom{5}{3} $$How many ways to arrange the letters AAAABBB so no two letters B are adjacent?
Q9.
There are 9 identical candles in a row. Alice wants to blow out three of them, but no two blown-out candles can be adjacent. Additionally, the candles at both ends must remain lit. How many ways can Alice blow out 3 candles?
So it is the same as asking,
$$ x_1+x_2+x_3+x_4=9-3=6 $$where $x_i>0$ and refers to he unblown candles
So it would be,
$$ \binom{2+3}{3}=\binom{5}{3} $$Q10.
You have 10 identical candies. You must eat at least one candy each day until they’re all gone. How many ways can you distribute the candies over the days?
(Bonus: There is a one-line proof for this)
At least one means if you eat in $k$ days, it would be
$$ x_1+x_2+...+x_k=10 \\ \binom{10-k+(k-1)}{k-1}=\binom{9}{k-1} $$In other words, this is the same as picking $k-1$ bit of a binary code with length of 9.
$$ 2^9 $$It can be also said “Put 9 spaces in between 10 candies.”
Lec 4
Q0.
If A and B are finite sets and f : A →B is one-to-one, then |A|≤|B|. Why?
So it is pigeon hole, if |A|>|B|, then $\lceil\frac{|A|}{|B|}\rceil>1$, it means you have at least two elements in A mapped to the same element in B. This is not one-to-one.
Q1.
A box contains 50 balls, including 10 red, 10 green, 10 yellow, and 10 blue balls. The remaining balls are either orange or purple. What is the minimum number of balls that must be drawn from the box to ensure that at least 7 balls of the same color are included? How does your answer change depending on the number of orange and purple balls?
Say less than 7 and more than 3 balls for orange and purple,
$$ 6*4+10+1=35 $$Say more than 7 orange or purple,
$$ 6*5+(10-x)+1 =41-x $$If no specification, 35 is necessary.
Q2.
Need to show upper bound and lower bound.
We can first draw Start to guarantee that we obtain both flavor, then draw Round to have one of the flavor. The crucial point is the least number of drawing to get two different flavors, so it is optimal if we draw Star first. Otherwise you should do $9+1$ to get two different flavor regardless of watermelon if you draw round first.
$$ (4+7+1)+(8+1)=21 $$20 is not enough,
Consider,
$$ \begin{aligned} Round:\,&WWWWWWWAAAAAAAPPPPPPPPP \\ Star:\,\,&WWWWAAAAAAAPPPPPP \end{aligned} $$If you draw only 20 candies, either you can’t get a round peach or you can’t get a star peach
Q3.
In a party of n people, each pair of people either shakes hands once or not at all. Prove that there are at least two people who have shaken hands with the same number of others by the end of the party.
Notice that the number of shaking hands distributes from $0$ to $n-1$
Case1. If somebody gets 0 shakes
Then it is impossible that $n-1$ shakes appears. You put n people in to n-1 holes from 0 to n-2, so at least two people have shaken hands with the same number of others.
Case2. If nobody gets 0 shakes
Still put n people into n-1 holes from 1 to n-1. At least two people have shaken hands with the same number of others.
Q4.
I pick n + 1 integers from {1, 2, 3, . . . , 3n}. Show that at least two of the integers I picked have a difference of at most 2.
Divide it into these groups,
$$ \{1,2,3\},\{4,5,6\},\{7,8,9\}...,\{3n-2,3n-1,3n\} $$You can choose at most one element in each group, while the union of the group cover the whole set.
According to pigeon hole theorem, if you pick up n+1 numbers, there is only n groups(holes), there would be at least one hole with $\lceil\frac{n+1}{n}\rceil=2$ elements.
Bonus
$$ 2024 = 8*153 =8 * 9 * 17 $$Prove there exists an integer where each digit is 8 that is divisible by 2024.
Say the integer can be represented by $8*s_i$ where $s_i$ refers to a $i$-digits integer in which each digit is 1.
So it is the same as saying if we can find $s_i$ that can both divde 9 and 17
Consider this,
$$ s_{i+1}=s_i*10+1 $$$$ s_{i+1}=s_i+1 \pmod 9 $$Since there is a circle of remainder, let’s say $s_k=s_n$ then $17|s_k-s_n$ , we know that $s_k-s_n$ is a integer that all last $n$ digits are 0, so $17|s_{k-n}$, because $(17,10^z)=1$, for any non-negative integer z.
I think as long as a number consists of no prime of 2 or 5, it can divides a integer with all digits of 1.
HW2
Q1.
If you select 11 numbers from the set of integers from 1 to 20, no matter how you choose them, there will inevitably be two numbers such that one is a multiple of the other.
The point is you can do this division,
$$ \{2^km\} $$where, $m$ is an odd number, and we can guarantee that if you choose more than one number in this set, one become multiple of another. And we can say that the union of these sets covers the whole original set.
Lec5
Q1.
(Ramsey theory for n = 6). Assume that among 6 persons that each pair of persons are either friends or enemies. Then either there are (at least) 3 persons who are mutual friends or (at least) 3 persons who are mutual enemies.
If we want to construct a counter case, no such triangle. Consider A has at least 3 enemy or 3 friends. They are symmetry so we consider A has 3 friends, then these three person can’t be friends to each other, otherwise there is triangle of friends. So they form a triangle of enemies.
Notice
Be carefule that “all” and “either A or B but not both” is different,
$$ |A\cup B|= |A|+|B|-|A\cap B| $$not both means you should dig out $|A \cap B|$ again
Too lazy to make arrangements, just interesting problems
1.
Given some points in 2-d space. Guarantee that they are not co-linear, you always can find a straight line pass through exactly two points.
Make a set of these kind of elements,
$$ (a,b,c) $$Where, c is the closest point to the line passing though a,b but not on it. There should be this kind element, because they are not co-linear.
The set is finite, so there is an element with smallest distance, then you can claim there won’t be a third point on the line passing through a and b. Draw a graph and do case study, and you can see why.
The nature of minimum you can take on this problem is that you should leverage the information that they are not co-linear, and finding the closest point actually reflects this condition.
2.
Say $(ab+1)|(a^2+b^2)$, then $\frac{a^2+b^2}{ab+1}$is a perfect sqaure.
Trick we play here is also about infinite descent.
$$ (a^2+b^2)=k(ab+1) \\ a^2-kba+b^2-k=0 $$Notice that it has two solutions if we regard $a$ as variables. Then we can try to use some trick to see if another root has something special than the root we gonna pick.
Let assume we now find the minimum tuple $(a_0,b_0)$ such that $a_0$ is the minimum.
The point is, look at another root $a$
$$ a_0a=b_0^2-k\\ a_0+a=kb_0 $$$a$ should be integer and we can tell it can’t be negative. Otherwise $a^2-kba+b^2-k>0$.
Also, the crucial point is that, $a$ or $a_0$ is smaller than $b_0$ if $a$ is not 0. This is impossible! We can claim the tuple we choose has $a_0>b_0$, then we find $a_0>b_0>a$, and we find a positive integer $a$ such that is smaller than $a_0$! So the only possible case is that $k$ is $b_0^2$ and $a$ is 0, which means $k$ should be a perfect sqaure!
3.
We have positive integer solutions for $y^3=x_1^3+x_2^3+...+x_n^3$ for $n\ge3$
Easy to make the construction once you see the trick, 这个叫原汤化原食
4.
Too lazy to write by myself.
Check d>1 becaues 0 jars is invalid. 你总能找到组合数各种拆分的真实意义，即使看起来非常离谱—–鲁迅
