MAT344H1S Introduction to Combinatorics
Midterm assignment. Due March 1, 10:00 pm
1. In a string, distance between two symbols is the number of symbols between them
plus one. For example, in a string xyyx, y is at distance 1 from another y, and x is
at distance 3 from another x. Find the number of strings of length n using at most k
distinct symbols, such that the minimal distance between any two identical symbols
is k.
2. For a given positive integer k, a quadratic polynomial with bounded integer coefficients
has the form P(x) = ax2+bx+ c, where a, b, c are integers in the range [−k, k]. There
are 2k(2k + 1)2 of these — note that a cannot be 0. Show that there are k(3k + 1) of
these polynomials which have 1 as a root, that is, with P(1) = 0.
3. Show that, if the minimal number of edges that can be removed from an Eulerian
graphG so that it stays Eulerian is k,G has a subgraph isomorphic to the cyclic graph
Ck.
4. Let f(n) denote the number of ways to cover a 2 × n rectangle with n rectangles of
size 2× 1 that are blue or red. Give a combinatorial proof that
f(2k+ 1) = 2f(k)2 + 8f(k)f(k− 1).
5. In the group stage of a tournament, 24 teams are separated into 6 groups of 4. Every
team plays each other team in their group twice, playing 6 games total. Games may
end in a tie. Show that there will be two teams with the same win-loss-tie record.
6. If a 6× 6matrix contains 19 zeros, show that there are 4 zeros which are all in distinct
rows and columns.
7. n people participate in a costumed party with n different costumes. Each person likes
exactly two costumes, and each costume is liked by exactly two people. Prove that it
is possible to match each person with a costume they like.
1

欢迎咨询51作业君