Q1 (10 points)
Give a combinatorial proof of the identity
for such that . No algebraic manipulations are allowed, i.e. you must interpret
both sides directly in the way that they are written.
Q2 (10 points)
You have three red, five green, and eight blue 20-sided dice that you throw randomly on a table. Prove
that there are always three distinct triples of dice, each containing one red, one green, and one blue die,
which have the same sum. For example, in the following configuration, we have three distinct triples,
each summing to 37.
ℕ = {1, 2, 3, …}
[푛] = {1, 2, 3, … , 푛} 푛 ∈ ℕ
( ) − ( ) = ( )
푛
푘
푛 − 푚
푘 ∑
푖=1
푚 푛 − 푖
푘 − 1
푘, 푚, 푛 ∈ ℕ 푘 + 푚 ≤ 푛
Time left Hide
23:43:31
Precisions.
A 20-sided die is a regular icosahedron (a polyhedron of 20 faces) with the numbers 1 to 20 drawn
its faces.
Two triples are considered distinct if they differ by at least one die. In other words, they can have
zero, one, or two dice in common, but not three.
The sum of a triple is the sum of the numbers on the top faces of its dice. Hence, if is
the number on the top face of the red die of the th triple, where , and similarly for
(green) and (blue), the goal of the question is to show that there are triples such that
.
Q3 (10 points)
For all , let be the number of -strings of length such that the difference between any two
consecutive digits is , , or . For example, if , then is valid, but not
because of .
(a) (2 points) Find , , and .
(b) (2 points) Show that for all .
(c) (3 points) Find an explicit expression for using the method of advancement operators.
(d) (3 points) Express the generating function of (i.e. ) as a quotient of two
polynomials.
Q4 (10 points)
Let , . Use the inclusion-exclusion principle to find the number of derangements of
such that .
푟푖 ∈ [20]
푖 푖 ∈ {1, 2, 3} 푔푖
푏푖
푟1 + 푔1 + 푏1 = 푟2 + 푔2 + 푏2 = 푟3 + 푔3 + 푏3
푛 ∈ ℕ 푎푛 [5] 푛
0 1 −1 푛 = 8 32212345 21345443
13
푎1 푎2 푎3
푎푛+3 = 3푎푛+2 − 2푎푛 푛 ∈ ℕ
푎푛
(푎푛 )∞
푛=1 퐹(푥) = ∑∞
푛=1 푎푛푥푛
푛 ∈ ℕ 푛 ≥ 4 휎 [푛]
휎({1, 2}) ∩ {1, 2} = ∅
Q5 (10 points)
Find the number of -strings of length containing an odd number of s, an even
number of s, and at least one .
Q6 (10 points)
Let be a finite graph and an induced subgraph of . Prove that
.
Q7 (10 points)
Consider the following network flow, where the letters on the vertices specify the ordering for the FordFulkerson algorithm. Use the Ford-Fulkerson algorithm to update the given flow until you get a
maximum flow and a minimum cut.
Precisions. Show all your work. For each run of the algorithm, write the list of all the labelings in the
order in which you performed them. For example, the following list taken from the textbook (in a
different example) shows that was labeled first by , then was labeled second by
, then was labeled third by , and so on.
{퐴, 퐵, 퐶, 퐷} 푛 ∈ ℕ 퐴
퐵 퐶
퐆 = (푉 , 퐸) 퐇 = (푊 , 퐹) 퐆
0 ≤ 휒(퐆) − 휒(퐇) ≤ |푉 | − |푊 |
푆 (∗, +, ∞) 퐸
(푆, +, 28) 퐹 (푆, +, 15)
푆
퐸
퐹
퐵
퐷
퐴
퐶
푇
: (∗, +, ∞)
: (푆, +, 28)
: (푆, +, 15)
: (퐸, +, 19)
: (퐸, +, 12)
: (퐹, +, 12)
: (퐵, +, 10)
: (퐴, +, 12).
You must also give the augmenting path and its .
The final answer should show the maximum flow with its value and the minimum cut with its capacity.
훿