=========================preview======================
(comp170)[2008](f)mid2~PPSpider^sol_10154.pdf
Back to COMP170 Login to download
======================================================

COMP170 C Fall 2008
Midterm 1 Review







Question 2 . n 3 .. n . 3 5 .. n . 8 3 . Note: solution. =

Give a combinatorial proof of the identity, for all n 11.

nn . 3 n . 6
33 5
An algebraic proof of this identity will not be accepted as a

Question 2 The left hand side obviously counts this Consider the problem of how to The right hand side oObviously counts this Notice that both problems are the same. . n 3 .. n . 3 5 .. n . 8 3 . = Note: solution.

Give a combinatorial proof of the identity, for all n 11.

nn . 3 n . 6
33 5
An algebraic proof of this identity will not be accepted as a

Consider the problem of how to color n items so that 3 are red, 5 are green, 3 are blue and the remaining n . 11 are yellow.
color n items so that 3 are red, 3 are blue, 5 are green and the remaining n . 11 are yellow.
We only change the order in which we do the colorings.

Starters (A List) 10 Types, A1,A2,...,A10 Main Courses (B List) 15 Types, B1,B2,...,B15
(a)
How many di.erent menus (3 from A, 2 from B) can you create?


(b)
Suppose the restaurant lets you choose starters as main courses. Note, you can choose 2, 1 or 0 from A as your main courses. If you choose an item from the A list as a main course, then you cannot also choose it as a starter. Now how many di.erent menus are there?


Examples:
{A1,A3,A5,B4,B6} is a legal menu for both questions (a) and (b)
{A1,A3,A5,A7,B6} is a legal menu for question (b) but not for (a).


Starters (A List) 10 Types, A1,A2,...,A10 Main Courses (B List) 15 Types, B1,B2,...,B15
(a) How many di.erent menus (3 from A, 2 from B) can you create?


Starters (A List) 10 Types, A1,A2,...,A10 Main Courses (B List) 15 Types, B1,B2,...,B15
(a) How many di.erent menus (3 from A, 2 from B) can you create?

10 15

32


Starters (A List) 10 Types, A1,A2,...,A10 Main Courses (B List) 15 Types, B1,B2,...,B15
(b) Suppose the restaurant lets you choose starters as main courses. Note, you can choose 0, 1 or 2 from A as your main courses. If you choose an item from the A list as a main course, then you cannot also choose it as a starter. Now how many di.erent menus are there?

Starters (A List) 10 Types, A1,A2,...,A10 Main Courses (B List) 15 Types, B1,B2,...,B15
(b) Suppose the restaurant lets you choose starters as main courses. Note, you can choose 0, 1 or 2 from A as your main courses. If you choose an item from the A list as a main course, then you cannot also choose it as a starter. Now how many di.erent menus are there?
1015 1015 10

++
32 41 5

The solution is split into whether we choose 0, 1 or 2 A items as main courses.

Let n> 2 be an integer and a Zn. For each of the two following statements either
(i)
prove that the statement is correct for all such a and n or

(ii)
give a counterexample. A counterexample would be a pair a, n for which the statement is false.

(a)
If the equation a n x =1 has a solution in Z