Massachusetts Institute of Technology Handout 15 6.042J/18.062J: Mathematics for Computer Science September 26, 2000 Professors Nancy Lynch and Shlomi Dolev

Problem Set 4

Due: 2:35pm in lecture, October 3, 2000.

Be sure to indicate your TA’s name clearly on the solutions your turn in.

—————————————————————————–

Self-study: Matrices Read: Rosen §2.6 Self-study problems (not to be handed in): Rosen §2.6, Exercises 1, 3, 5, 9, 13, 15, 23, 29, 31

—————————————————————————–

Reading: Rosen 7.1-7.5, 7.8, 8.1, 8.2, 8.4, 8.5

New policy on collaboration Starting from today: If you collaborated with someone on the problem sets, you should mention their names on top of the problem set. If you did not collaborate with anyone, you should explicitly say so. As a reminder, the write-up of your solutions should be entirely your own.

Problem 1 At last count, our 6.042 class contains 180 students. Prove that the class must contain either: (a) A set S of 15 students such that, if they line up in size places, they are also arranged in increasing order of age, or (b) a set T of 13 students such that, if they line up in size places, they are also arranged in decreasing order of age.

Problem 2 Find the number of paths of length 5 from a to e of in the directed graph shown below Problem 3 An Euler path in a digraph G is a path that traverses all the edges of G, each edge exactly once. Unlike an Euler circuit, it need not end up at the same vertex where it started.

Say whether each of the following digraphs has an Euler path, an Euler circuit, both, or neither. Justify your answers by exhibiting the circuits and paths that you say exist, and proving that the others don’t exist.

(a)

(b)

Handout 15: Problem Set 4 3 Problem 4 For each of the following graphs,

• Find the chromatic number

• Say whether it is possible to decrease the chromatic number by removing a single vertex and

all edges incident with it. Justify your answers.

(a) The graph in Rosen Section 7.8, exercise 4.

(b) The graph in Rosen Section 7.8, exercise 8. Problem 5 Rosen section 7.5, exercise 44. Problem 6 Either describe what a full m-ary tree with 76 leaves and height 3, where m is a positive integer, would look like, or show that no such tree exists. Problem 7 Rosen 8.2 exercise 8. How many weighings of a balanced scale are needed in order to find a counterfeit coin among eight coins if the the counterfeit coin is either heavier or lighter than the others? Describe an algorithm to find the counterfeit coin using this number of weighings.