Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 70

Discrete Mathematics and Probability Theory

Summer 2022

HW 4

1   Lagrange? More like Lamegrange.

In this problem, we walk you through an alternative to Lagrange interpolation.

(a) Let’s say we wanted to interpolate a polynomial through a single point, (x0 ,y0 ). What would be the polynomial that we would get? (This is not a trick question.)

(b) Call the polynomial from the previous part f0 (x). Now say we wanted to define the polynomial f 1 (x) that passes through the points (x0 ,y0 ) and (x1 ,y1 ). If we write f 1 (x) = f0 (x)+a1 (xx0 ), what value of a1 causes f1 (x) to pass through the desired points?

(c) Now say we want a polynomial f2 (x) that passes through (x0 ,y0 ), (x1 ,y1 ), and (x2 ,y2 ). If we write f2 (x) = f1 (x)+a2 (xx0 )(xx1 ), what value of a2 gives us the desired polynomial?

(d) Suppose we have a polynomial fi(x) that passes through the points (x0 ,y0 ), ..., (xi ,yi) and we want to find a polynomial fi+1(x) that passes through all those points and also (xi+1 ,yi+1). If we define fi+1(x) = fi(x)+ai+1j(i)=0 (xxj), what value must ai+1 take on?

2   How Many Polynomials?

Let P(x) be a polynomial of degree at most 2 over GF(5). As we saw in lecture, we need d + 1 distinct points to determine a unique d-degree polynomial, so knowing the values for say, P(0), P(1), and P(2) would be enough to recover P. (For this problem, we consider two polynomials to be distinct if they return different values for any input.)

(a) Assume that we know P(0) = 1, and P(1) = 2. Now consider P(2). How many values can P(2) have? How many distinct possibilities for P do we have?

(b) Now assume that we only know P(0) = 1. We consider P(1) and P(2). How many different (P(1), P(2)) pairs are there? How many distinct possibilities for P do we have?

(c) Now, let P be a polynomial of degree at most d on GF(p) for some prime p with p > d. Assume we only know P evaluated at k ≤ d + 1 different values. How many different possibilities do we have for P?

(d) A polynomial with integer coefficients that cannot be factored into polynomials of lower degree on a finite field, is called an irreducible or prime polynomial.

Show that P( ) =x x2 + x +1 is a prime polynomial on GF(5).

3   Monke

In the Monke Kingdom, there are seven bald uakaris, four black howlers, two mandrills, two gelada and one baboon. The Monke King has told the five species about an uncountably large supply of bananas; however, Monke doesn’t want to reveal where the bananas are unless at least two species can cooexist in harmony.

(a) Help Monke create a scheme that allows the monkeys to find the key only if all members of one species in addition to at least one member from a different specie agree to work together.

For example, if all seven bald uakaris and one mandrill agree, they can find the key. However, if six bald uakaris and one mandrill agree, or if only seven bald uakaris agree, then the key cannot be found.

(b) Seeing that all the uakaris and all howlers have teamed up, Monke wants to encourage even more monkey friendship.  He wants to set up an additional scheme so that, if at least one mandrill, one gelada and one baboon agree, the five parties can uncover exactly two more supplies of bananas, one countably infinite and one finite. How can Monke implement part 2 of their scheme?

4   Thats Numberwang!

Congratulations! You’ve earned a spot on the game show "Numberwang".

(a) How many permutations of NUMBERWANG contain "GAMER" as a substring? How about

as a subsequence (meaning the letters of "GAMER" have to appear in that order, but not nec- essarily next to each other)?

(b) In round 1 of Numberwang, each player chooses an ordered sequence of 5 digits.  A valid sequence must have the property that it is non-increasing when read from left to right.  For example, 99621 is a valid sequence, but 43212 is not. How many choices of valid sequences are there? (Hint:  Relate the problem to balls and bins.)

(c) To win round 2 of Numberwang, a contestant must choose five nonnegative integers x0 ,x1 ,x2 ,x3 ,x4 such that x0 +x1 +x2 +x3 +x4 = 100, and xi ≡ i  (mod 5). How many ways are there to pick    a winning set of integers?

5   M, Mi, Mic, Mich, Micha, Michae, Michael!

In the vowel substring problem, we are tasked to find the number of vowels in every substring of an input string S. A substring is defined as any contingious set of characters in the original order of

S. For example, S = ”aba”, the substrings of S would be "a", "ab", "aba", "b", "ba", "a", counting a total of 6 vowels. We will make a combinatorial argument to count the number of vowels in all substrings.

• How many substrings are there in a string of length n?

• Suppose there is a vowel at 1st position of S (the beginning). Given that S has length n, how many substrings contain that vowel at the beginning of S?

• Suppose there is a vowel at the kth  position of S.  How many substrings of S contain that vowel at the kth position?

• Given that there are vowels in positions i1 , i2 , ..., ik what are the total number of vowels in all substrings of S?

6   Maze

Let’s assume that Tom is located at the bottom left corner of the 9 × 9 maze below, and Jerry is located at the top right corner. Tom of course wants to get to Jerry by the shortest path possible.

 

(a) What is the length of the shortest path from Tom to Jerry?

(b) How many such shortest paths exist?

(c) How many shortest paths pass through the edge labeled X?  The edge labeled Y?  Both the edges X and Y? Neither edge X nor edge Y ?

7   Count It!

For each of the following collections, determine and briefly explain whether it is finite, countably infinite (like the natural numbers), or uncountably infinite (like the reals):

(a) The integers which divide 8.

(b) The integers which 8 divides.

(c) The functions from N to N.

(d) The set of strings over the English alphabet. (Note that the strings may be arbitrarily long, but each string has finite length. Also the strings need not be real English words.)

(e) The set of finite-length strings drawn from a countably infinite alphabet, A. (f) The set of infinite-length strings over the English alphabet.