Discrete Mathematical Structures
Discrete Mathematical Structures CSCI 2427
Popular in Course
Popular in ComputerScienence
This 8 page Class Notes was uploaded by Else Dooley on Sunday October 11, 2015. The Class Notes belongs to CSCI 2427 at East Carolina University taught by Robert Hochberg in Fall. Since its upload, it has received 263 views. For similar materials see /class/221319/csci-2427-east-carolina-university in ComputerScienence at East Carolina University.
Reviews for Discrete Mathematical Structures
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/11/15
Practice Problems N E 4 V39 0 gt1 9 Complete the tree diagram Use it to make a systematic listing of all possible arrangements of the four letters A B C and D Confirm the number of arrangements using the multiplication rule for counting Six different colored blocks are lined up in a row How many color arrangements are possible A teacher who loves discrete math gives a worlshop which causes 17 other teachers to love discrete math Then each of those teachers teaches discrete math to 22 students who gain such an appreciation of discrete math that they each go home and tell both of their parents an interesting discrete math fact How many parents has the original teacher thereby in uenced with her single workshop CED E3 When Alice sends Bob a card she always adds a string of 5 X s andor O s a er her signature with one restriction she never puts two O s next to each other because Bob turns them into smiley faces and she can t stand that Thus for example OXOXO and XOXXO would be allowed but XOOXX and OOXOO would not Systematically list all the different ways for Alice to add X s and OS to the card How many ways are there How many di erent colorings are possible if each small square in each of these arrangements is either shaded or le blank Support your answers by listing systematically all of the possibilities Start with the letters in the word graphs a How many ways can you select and arrange 2 of the letters 1 letter 1 or 2 letters 3 4 or 5 letters b Explain the counting techniques used in terms of the multiplication and addition rules The Perfect Spy Agent 006 is sealed inside a room with no way to escape With him in the room is a timebomb set to explode in 9 minutes It would take him just 30 seconds to de lse the bomb except that it is locked inside a suitcase that has a combination lock on one of the clasps To open the lock he has to set three dials each containing the digits 09 to the correct positions He is able to check two of these combinations per second thanks to his topnotch manual dexterity Is he guaranteed to be able to open the suitcase with enough time le to de lse the bomb Make a tree diagram showing all arrangements of the letters in the word REED How many are there 0 N LA 4 UI ON l The gure to the right shows 4 rooks placed on a 4X4 chessboar in such a A B C D way that no rook attacks any other rook In chess a rook attacks pieces which lie in the same row or column as itself a List systematically all the ways to place 4 nonattacking rooks on a 4X4 board Use the grids on page EX 4 In the diagram the rooks are at squares A4 B l C3 and D2 b How many ways are there c Is there a way to use the multiplication rule to nd this answer a How many 3digit numbers are there where each digit is odd b How many 3digit numbers are there where each digit is odd and all three digits are diiferent c How many 3digit numbers are there where each digit is odd and the three digits appear in increasing order For example 157 is such a number Can you answer this question using the multiplication rule In this problem we use the word word to mean any sequence involving the indicated letters For example SUSUSU is a siX letter word using only S and U as are SSSSSS and UUUSSS a How many siX letter words can you make using only S and U b How many four letter words can you make using only R E D c How many ve letter words can you make using R E A D d Ifyou wanted to make that many words the answer to part c using only S andor U how long would you have to make the words Make a tree diagram showing all arrangements of the letters in the word REED How many are there How many arrangements are there of the letters in the word SEVEN In how many of these are the E 3 together In how many are the E s separated Two players compete repeatedly until one wins two successive games or three games total How many diiferent sequences are possible What if you change three games tota to four A set of ve regular octahedral dice have eight faces numbered 1 2 3 4 6 8 12 and 20 In how many diiferent ways can these ve dice fall In how many ways will the ve dice show a sum of siX of seven What are the chances of rolling a sum of siX or seven Not long ago there were ve teams in the East and Central and four in the West Division of both the American and National Baseball Leagues How many diiferent standings were possible for the 28 teams when ranked within their divisions within their leagues all together Assume that there are no ties How many World Series team matchups were possible As I was going to St Ives I met a man with 7 wives Each wife had 7 sacls each sack had 7 cats each cat had 7 kittens Kittens cats sacks wives how many were going to St Ives A Tree Diagram for Arranging 4 Letters How would you place the letters A B C and D into these boxes to show all the ways to arrange these four letters How many ways are there altogether to arrange these four letters Can you see how to get that number using the multiplication rule I I I I I I I I I I I II lJ IIIIIIIIIIIII ampampamp Some Practice Counting Problems 1 Print your rst name How many arrangements of the letters are possible if we consider that letters of the same type are indistinguishable For example there are 6 ways for Eva to arrange the letters of her name but only 3 ways for Eve How many ways can you arrange the letters in the word Kentucky In the word Tennessee Ben Franklin has 9 kites and 12 keys at home and wants to select three of each to bring with him when he does his next experiment How many different ways are there for him to do this Ned was sent to Bob 3 Ice Cream Sundaes to get a sundae for Nora but when he arrived he couldn t remember which three avors of ice cream Nora had asked for though he was sure that they were three different avors Looking over the list of 14 available avors didn t help him either so he decided that he would get one sundae for each possible selection of three avors How many sundaes will poor Ned have to buy How many anagrams are there of each of the following words levee teeth monsoon and Mississippi How many routes are there from A to B in each of the following grids A route follows the lines and always goes either north N or east E Ignore the weights in the large grid unless you want to nd the shortest route B B 7 O N You want to see the top six movies a In how many sequences would that be possible b If you have money for only three movies how many different sets of three movies could you choose to see c How many different ways are there to pick three of these movies to see on three consecutive nights a In how many ways can you select a threeletter initial In how many ways can you select a threeletter initial consisting of different letters c In how many ways can you select a set of three different letters from the alphabet 57 King Lewser unjustly condemns eight of his subjects to death and locks them in a prison cell deep beneath his castle Immediately the prisoners start digging an escape tunnel which will take them 65 days to complete According to the rules of the land at sunrise of each day the prisoners may send a delegation from among themselves to plead for their lives but subject to two conditions a The delegation must be the same size each day and b the delegation must never consist of the same set of people as on any previous day When they run out of delegations King Lewser has the option of executing them The prisoners may select the size of delegation they send What size should they choose Can they save themselves How many ways are there for Carol to add X s and O s to her letters to Dave if she uses 7 characters altogether Note that Carol and Dave don t have any problem with two O s appearing next to each other How many ways are there if she uses exactly 2 X s and the rest are O s How many ways are there if she uses exactly 5 X s and the rest are O s A teacher wants to assign 6 students to three teams a red team a green team and a blue team so that each team gets two students How many different ways are there to do this A CD player is programmed to shuf e the order in which it plays the eight pieces on one disk and the 11 pieces on another disk without repeating How many ways is this possible if all pieces on the first disk are played before the second starts if the machine shuffles between disks as well as pieces A hexagon as shown to the right has 9 diagonals Let s determine the number of diagonals that a convex polygon with 75 vertices will have a Since there are 75 vertices there will be 75 choose 2 which equals lines altogether including the sides of the polygon Thus the number of diagonals will be b Eere are 75 vertices and each vertex is the endpoint of diagonals so there will be endpoints of diagonals altogether When we correct for overcounting we discover that there will be diagonals altogether There are some men and 21 women in a room No person shakes hands with someone of the same sex but it is noted that each man shakes hands with 3 women and each woman shakes hands with 5 men How many men are in the room Here are some facts a The integer n is an odd prime number Every odd integer is either congruent to 1 mod 4 or congruent to 3 mod 4 71 is a quadratic residue mod p if and only if p is congruent to 1 mod 4 An odd prime number is the sum of two squares if and only if it is congruent to 1 mod 4 71 is not a quadratic residue mod n Given the above facts prove in words in paragraph form that n is not the sum of two squares b c d e Suppose n is an integer and consider the following predicates a Pn n is prime b Qn n is odd c Rn n is congruent to 1 mod 4 d Sn n is congruent to 3 mod 4 e Tn 71 is a quadratic residue mod n Rewrite each of parts a b and c of problem 1 in terms of the predicates given above a The integer n is an odd prime number b Every odd integer is either congruent to 1 mod 4 or congruent to 3 mod 4 c 71 is a quadrat ic residue mod p if and only if p is congru ent to 1 mod 4 Construct atruth table for the compound proposition p q p r p r Define each of the following terms Tautology Proposition Predicate Contradiction Contingency Conjunction Disjunction Negation Quanti er rp qawrvppp s Here is an implication If you love me you will give me your car keys a What is the contrapositive of that statement b What is the converse of that statement c Which of the two statements you created in parts a and b are equivalent to the original statement Prove that p q q 39 q is atautology What is the dual of the compound proposition up q r Construct a compound proposition that has the truth value indicated in the table to the right witnaequot mamas aamm