MATH3U03 Assignment 3

• This assignment has 6 questions, and is out of 18 marks. Every problem you attempt yields 1 completion mark. Three of the problems will be randomly selected for grading.

• There are two styles of problems: Quick/Computation problems, and proof problems.

– Computation problems are graded on a 2 point scale per subproblem: 1 point for correct answer and 1 point for work.

– Proof problems are graded on a 4 point scale depending on quality of exposition and correctness of the solution.

– In total, there are 12 marks from graded problems.

• Collaboration is encouraged, but academic dishonesty is not. You must write your own work, and present solutions in your own words.

• Mathematical writing is difficult. Here are two documents which give some advice on good writing habits. One by our very own Adam van Tuyl, and another by Kevin P. Lee.

• If you plan on continuing in Mathematics, Physics, or Computer Science, you need to learn to write in LATEX. The easiest way to start is to use Overleaf, which McMaster has a license for. I’ve created a template which you can access here, which has some basic explanations, and a template for your assignments.

– You should be able to login to Overleaf using your MacID.

Question 1. (2.5.6) In chess, a rook is attacking if it is in the same row or column as another piece. Find the number of ways to place k non-attacking rooks on an n × k chessboard, assuming n ≥ k.

Question 2. (2.5.9) The Science club has 20 members and 4 officer positions: President, Vice-President, Secretary, and Treasurer. Two of the members, Alex and Billie, require that at least one of the following holds:

(i) Alex is president.

(ii) Billie is vice-president.

(iii) Alex and Billie are secretary and treasurer in some order.

(iv) Alex and Billie are not officers.

How many ways can we assign positions if their demands are met?

Question 3.

(2.5.8) Each club in the college must select a representative and an alternate to speak for them at the student council. How many possible council meetings are possible if there are five clubs, the i-th club has ni members, and no one is in two clubs?

(2.6.8) In a game of Tic-Tac-Toe lasting nine moves, X has the opportunity to win by completing two lines at once. Count the number of ways to arrange five Xs on a 3 × 3 Tic-Tac-Toe board so that they form. two lines.

Question 4.

(2.6.10) Consider a game of Tic-Tac-Toe played on a 4 × 4 board, where the winner must make a line of 4. Count the number of games that end on the 7th move.

c.f. (2.7.13) Let A be a digit denoting the number 10, and B a digit denoting the number 11 (e.g. as in hexadecimal). Write the permutation

π = ( 1 2 3 4 5 6 7 8 9 A B

         8 4 7 3 1 A 2 B 5 6 9 ) ∈ S11

in disjoint cycle notation. What is the cycle index of π? The cycle type of π?

Question 5. (2.7.18) Suppose that 20 people are to attend a dinner party. The guests are to be seated at one of four circular tables each with unlabeled seats. The first table has seven seats, the second and third tables have five seats, and the fourth table has three seats. Two of the guests, Alex and Billie, cannot be seated at the same table. How many possible settings are there?

Question 6. (2.7.20) Show that n! = P nk=0 s(n, k) using double-counting.