CS1800 Discrete Structures Profs. Fell & Sundaram Fall 2012 November 02, 2012 Written Homework 03 Assigned: Fri 02 Nov 2012 Due: Fri 09 Nov 2012 Instructions: The assignment is due at the beginning of class on the due date specied. Late assignments will be penalized 50%, as stated in the course information sheet. Late assignments will not be accepted after the solutions have been distributed. We expect that you will study with friends and often work out problem solutions together; however, you must write up you own solutions, in your own words. Cheating will not be tolerated.
CS1800 Discrete StructuresProfs. Fell & SundaramFall 2012November 02, 2012Written Homework 03Assigned:Fri 02 Nov 2012Due:Fri 09 Nov 2012Instructions:•The assignment is due at thebeginningof class on the due date specified. Late assignments will bepenalized 50%, as stated in the course information sheet. Late assignmentswill not be acceptedafterthe solutions have been distributed.•We expect that you will study with friends and often work out problem solutions together; however,you must write up you own solutions, in your own words. Cheating will not be tolerated.•We expect your homework to be neat, organized, and legible. If your handwriting is unreadable, pleasetype your solutions. Use 8.5in by 11in loose-leaf or printer paper, and please do not hand in sheetsthat have been ripped from spiral bound notebooks.Problem 1[30 pts;, (2,4,4,4,4,4,4,4)]: DivisibilityConsider the set of positive even integersS={2,4, . . . ,3000}.i.What is the cardinality of this set?ii.How many of these integers are divisible by 3?iii.How many of these integers are divisible by 5?iv.How many of these integers are divisible by 3 AND by 5?v.How many of these integers are not divisible by 3 OR by 5?vi.What is the least number of distinct integers that must be chosen fromSso that at least oneof them is divisible by 3?vii.What is the least number of distinct integers that must be chosen fromSso that at least oneof them is divisible by 5?viii.What is the least number of distinct integers that must be chosen fromSso that at least oneof them is divisible by 3 or 5?Problem 2[30 pts, (5,5,5,5,10)]: The Elections of 2012On November 6, 2012, America goes to the polls to elect a president, 33 members of the Senate,and 435 members of the House of Representatives. Assume that for each seat up for election, wehave exactly one Republican and one Democratic candidate, and there are no other candidates.Show all your work for each of the following parts. For the first four parts, you need not completeall the calculations to yield a single number, but simplify each answer to the extent possible.1
i.Taking into account all of the elections (1 President seat, 33 Senate seats, and 435 Houseseats), how many possible outcomes are there?ii.Focusing only on the elections for the House, how many possible outcomes will lead to amajority for the Republicans in the House?iii.The Senate has a total of 100 seats, of which 67 will be held by continuing members. Of these67, 30 are Democrats and 37 are Republicans. One concern among Republican supportersis that the Democrats may end up with at least 60 seats, potentially ruling out filibuster inSenate debates. How many possible outcomes are there for the Democrats to end up with atleast 60 seats in the Senate after the elections? Is this more than half of the possible outcomesfor the Senate elections?iv.According to the electoral college system for presidential elections, all the electoral votesallocated to a state are won by the candidate who gets the most votes in the state.1Howmany different ways can the 50 states be distributed between two presidential candidates?v.A pollster surveys 10000 voters at Northeastern University. Of the 10000 voters, 5000 areRepublicans (the rest are Democrats), 9000 are students (the rest are faculty/staff members),and 5500 are women. The pollster further finds that there are 4500 Republican students,1900 male Democrats, 3700 male students, and 2300 female Republican students. Whatis the number of male Democrat faculty/staff members? What is the number of studentDemocrats? Show all your work, including any Venn diagrams that clearly specify the countsof relevant sets.Problem 3[20 pts, (4,4,6,6)]: Pseudorandom number generatorsPseudorandom number generators are programs that generate sequences of 0s and 1s that “look”random. These sequences have a wide range of applications, including in cryptography, cellular net-works, and simulations of large physical systems. Many pseudorandom generators used in practicegenerate sequences with some specific properties, as discussed below.Consider a pseudorandom number generator that generates 20-bit sequences; i.e., each sequenceis of length 20 and consists of 0s and 1s. For each of the following questions, complete all thecalculations and show all your work.i.What is the total number of different 20-bit sequences?ii.One criterion that a sequence generator may desire is to have an equal number of 1s and 0s.What number of 20-bit sequences contain an equal number of 0s and 1s?iii.Another commonly-used criterion is limiting the length ofruns. A run is a maximal contiguoussequence of identical bits. That is, a run of 0s is a contiguous sequence of 0s, which is precededby a 1 or is at the start of the sequence, and succeeded by a 1 or at the end of the sequence.Similarly, a run of 1s is a contiguous sequence of 1s, which is preceded by a 0 or is at thestart of the sequence, and succeeded by a 0 or is at the end of the sequence. For example,1This is not really true, but we will assume this for our problem. Do you know which states do not follow thisrule?2
CS1800 Discrete StructuresProfs. Fell & SundaramFall 2012November 02, 2012Written Homework 03Assigned:Fri 02 Nov 2012Due:Fri 09 Nov 2012Instructions:•The assignment is due at thebeginningof class on the due date specified. Late assignments will bepenalized 50%, as stated in the course information sheet. Late assignmentswill not be acceptedafterthe solutions have been distributed.•We expect that you will study with friends and often work out problem solutions together; however,you must write up you own solutions, in your own words. Cheating will not be tolerated.•We expect your homework to be neat, organized, and legible. If your handwriting is unreadable, pleasetype your solutions. Use 8.5in by 11in loose-leaf or printer paper, and please do not hand in sheetsthat have been ripped from spiral bound notebooks.Problem 1[30 pts;, (2,4,4,4,4,4,4,4)]: DivisibilityConsider the set of positive even integersS={2,4, . . . ,3000}.i.What is the cardinality of this set?ii.How many of these integers are divisible by 3?iii.How many of these integers are divisible by 5?iv.How many of these integers are divisible by 3 AND by 5?v.How many of these integers are not divisible by 3 OR by 5?vi.What is the least number of distinct integers that must be chosen fromSso that at least oneof them is divisible by 3?vii.What is the least number of distinct integers that must be chosen fromSso that at least oneof them is divisible by 5?viii.What is the least number of distinct integers that must be chosen fromSso that at least oneof them is divisible by 3 or 5?Problem 2[30 pts, (5,5,5,5,10)]: The Elections of 2012On November 6, 2012, America goes to the polls to elect a president, 33 members of the Senate,and 435 members of the House of Representatives. Assume that for each seat up for election, wehave exactly one Republican and one Democratic candidate, and there are no other candidates.Show all your work for each of the following parts. For the first four parts, you need not completeall the calculations to yield a single number, but simplify each answer to the extent possible.1
i.Taking into account all of the elections (1 President seat, 33 Senate seats, and 435 Houseseats), how many possible outcomes are there?ii.Focusing only on the elections for the House, how many possible outcomes will lead to amajority for the Republicans in the House?iii.The Senate has a total of 100 seats, of which 67 will be held by continuing members. Of these67, 30 are Democrats and 37 are Republicans. One concern among Republican supportersis that the Democrats may end up with at least 60 seats, potentially ruling out filibuster inSenate debates. How many possible outcomes are there for the Democrats to end up with atleast 60 seats in the Senate after the elections? Is this more than half of the possible outcomesfor the Senate elections?iv.According to the electoral college system for presidential elections, all the electoral votesallocated to a state are won by the candidate who gets the most votes in the state.1Howmany different ways can the 50 states be distributed between two presidential candidates?v.A pollster surveys 10000 voters at Northeastern University. Of the 10000 voters, 5000 areRepublicans (the rest are Democrats), 9000 are students (the rest are faculty/staff members),and 5500 are women. The pollster further finds that there are 4500 Republican students,1900 male Democrats, 3700 male students, and 2300 female Republican students. Whatis the number of male Democrat faculty/staff members? What is the number of studentDemocrats? Show all your work, including any Venn diagrams that clearly specify the countsof relevant sets.Problem 3[20 pts, (4,4,6,6)]: Pseudorandom number generatorsPseudorandom number generators are programs that generate sequences of 0s and 1s that “look”random. These sequences have a wide range of applications, including in cryptography, cellular net-works, and simulations of large physical systems. Many pseudorandom generators used in practicegenerate sequences with some specific properties, as discussed below.Consider a pseudorandom number generator that generates 20-bit sequences; i.e., each sequenceis of length 20 and consists of 0s and 1s. For each of the following questions, complete all thecalculations and show all your work.i.What is the total number of different 20-bit sequences?ii.One criterion that a sequence generator may desire is to have an equal number of 1s and 0s.What number of 20-bit sequences contain an equal number of 0s and 1s?iii.Another commonly-used criterion is limiting the length ofruns. A run is a maximal contiguoussequence of identical bits. That is, a run of 0s is a contiguous sequence of 0s, which is precededby a 1 or is at the start of the sequence, and succeeded by a 1 or at the end of the sequence.Similarly, a run of 1s is a contiguous sequence of 1s, which is preceded by a 0 or is at thestart of the sequence, and succeeded by a 0 or is at the end of the sequence. For example,1This is not really true, but we will assume this for our problem. Do you know which states do not follow thisrule?2