University of California, Berkeley - CS 70hw7-sol. CS 70 Discrete Mathematics and Probability Theory. Fall 2019. Homework 7 Solutions.

Document Content and Description Below

CS 70 Discrete Mathematics and Probability Theory Fall 2019 Alistair Sinclair and Yun S. Song HW 7 Note: This homework consists of two parts. The first part (questions 1-4) will be graded and will... determine your score for this homework. The second part (questions 5-6) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the first part. You should attempt the problems in the second part only if you are interested and have time to spare. For each problem, justify all your answers unless otherwise specified. Part 1: Required Problems 1 Counting Boot Camp Let’s get some practice with counting! For this problem, you do not need to show work that justifies your answers. You may also leave your answer as an expression (rather than trying to evaluate it to get a specific number). (a) How many sequences of 15 coin-flips are there that contain exactly 4 heads? (b) How many ways are there to arrange n heads and k tails into a sequence? (c) How many 99-coin-flip sequences are there that contain more heads than tails? (d) A poker hand contains 5 cards from a standard 52-card deck. The order of the cards in a poker hand is irrelevant. How many different 5-card poker hands are there? (e) How many different 5-card poker hands are there that contain no aces? (f) How many different 5-card poker hands are there that contain all four aces? (g) How many different 5-card poker hands are there that contain exactly 3 spades? (h) An anagram of HALLOWEEN is any re-ordering of the letters of HALLOWEEN, i.e., any string made up of the letters H, A, L, L, O, W, E, E, N in any order. The anagram does not have to be an English word. How many different anagrams of HALLOWEEN are there? (i) How many solutions does y0 +y1 +•••+yk = n have, if each y must be a non-negative integer? (j) How many solutions does y0 +y1 = n have, if each y must be a positive integer? CS 70, Fall 2019, HW 7 1 (k) How many solutions does y0 +y1 +•••+yk = n have, if each y must be a positive integer? Solution: 2 That’s Numberwang! Congratulations! You’ve earned a spot on the game show "Numberwang". (a) How many permutations of NUMBERWANG contain "GAME" as a substring? How about as a subsequence (meaning the letters of "GAME" have to appear in that order, but not necessarily 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? Solution: 3 Shipping Crates A widget factory has four loading docks for storing crates of ready-to-ship widgets. Any time a loading dock contains at least 5 crates, a truck picks up 5 crates from that dock and ships them away (e.g., if 6 crates are sent to a loading dock, the truck removes 5, leaving 1 leftover crate still in the dock). Suppose the factory produces 8 indistinguishable crates of widgets and sends each crate to one of the four loading docks. After all the shipping has been done, how many possible configurations of leftover crates in loading docks are there? (We consider two configurations to be the same if, for every loading dock, the two configurations have the same number of leftover crates in that dock.) Solution: 4 Picking Teams (a) The 25 students in CS 70 have a strange way of picking a study group. Each person is given a distinct number 1 through 25 based on random chance, and participants may form a group as long of the sum of their numbers is at most 162. (The TAs are afraid of the number 162 for some reason...) How many different study groups are possible? That is, how many different subsets of students are there, which are allowable under the ranking rule? (Hint: 162 = [(∑25 i=1 i)-1]=2)) (b) UC Berkeley is forming a new, n-person robotics team. There are 2n interested students: n mechanical engineers and n programmers. (Assume that no student is both a mechanical engineer and a programmer.) Find the number of distinct n-person teams. (c) Suppose that all robotics teams must also name a team captain who is a mechanical engineer. Find the number of ways to pick an n-person team with a mechanical engineer as the captain. Solution: Note: This concludes the first part of the homework. The problems below are optional, will not affect your score, and should be attempted only if you have time to spare. Part 2: Optional Problems 5 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. CS 70, Fall 2019, HW 7 6 (a) How many such shortest paths exist? (b) How many shortest paths pass through the edge labeled X? (c) The edge labeled Y? Both the edges X and Y? Neither edge X nor edge Y? (d) How many shortest paths pass through the vertex labeled Z? The vertex labeled W? Both the vertices Z and W? Neither vertex Z nor vertex W? Solution: 6 Rubik’s Cube Scrambles We wish to count the number of ways to scramble a 2×2×2 Rubik’s Cube, and take a quick look at the 3×3×3 cube. Leave your answer as an expression (rather than trying to evaluate it to get a specific number). (a) The 2×2×2 Rubik’s Cube is assembled from 8 "corner pieces" arranged in a 2×2×2 cube. How many ways can we assign all the corner pieces a position? CS 70, Fall 2019, HW 7 9 (b) Each corner piece has three distinct colors on it, and so can also be oriented three different ways once it is assigned a position (see figure below). How many ways can we assemble (assign each piece a position and orientation) a 2×2×2 Rubik’s Cube? Three orientations of a corner piece (c) The previous part assumed we can take apart pieces and assemble them as we wish. But certain configurations are unreachable if we restrict ourselves to just turning the sides of the cube. What this means for us is that if the orientations of 7 out of 8 of the corner pieces are determined, there is only 1 valid orientation for the eighth piece. Given this, how many ways are there to scramble (as opposed to assemble) a 2×2×2 Rubik’s Cube? (d) We decide to treat scrambles that differ only in overall positioning (in other words, the entire cube is flipped upside-down or rotated but otherwise unaltered) as the same scramble. Then we overcounted in the previous part! How does this new condition change your answer to the previous part? (e) Now consider the 3 × 3 × 3 Rubik’s Cube. In addition to 8 corner pieces, we now have 12 "edge" pieces, each of which can take 2 orientations. How many ways can we assemble a 3×3×3 Rubik’s Cube? Solution: [Show More]

Last updated: 2 years ago

Preview 1 out of 10 pages