NEW HERE? USE "AFORUM20" TO GET GET 20 % OFF
CLAIM OFFER

NEW HERE? USE "AFORUM20" TO GET GET 20 % OFF
CLAIM OFFER

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.

훿

Our customer support team is here to answer your questions. Ask us anything!

👋 WhatsApp Us Now

Hi, how can I help?