Mathematics Appreciation MATH 210G
Popular in Course
Popular in Mathematics (M)
This 0 page Class Notes was uploaded by Florence Blanda on Sunday November 1, 2015. The Class Notes belongs to MATH 210G at New Mexico State University taught by Staff in Fall. Since its upload, it has received 19 views. For similar materials see /class/233198/math-210g-new-mexico-state-university in Mathematics (M) at New Mexico State University.
Reviews for Mathematics Appreciation
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/01/15
RSA Encryption On Tuesday we discussed mod 26 arithmetic There is nothing special about 26 The idea makes sense in more generality For example the binary arithmetic we discussed in relation to the Hamming code is actually mod 2 arithmetic To discuss RSA we will use mod arithmetic with a very large number if n represents a whole number we do mod n arithmetic by first performing the ordinary arithmetic and then dividing the result and keeping the remainder We will illustrate this after we discuss the RSA encryption system The RSA System RSA encryption was publicized in I977 The method was discovered by the authors of the article Ron RivestAdi Shamir and Leonard Adleman However due to security reasons it was not divulged until I997 that Clifford Cocks working for British intelligence had described the method in an internal document in I973 In working with RSA each message to be encrypted will be considered to be a number Larger messages can be thought of as several numbers The system works as follows Choose two prime numbers say called p and q These are whole numbers which cannot be factored into two smaller numbers Examples of primes include 2 3 5 7 and Let n p q and m pl ql We choose two numbers e and d which satisfy the relation that e d l in mod m arithmeticWe actually only need to choose e Once e is selected d can be computed easily by a computer If M is a message eg a number to encrypt it we replace M by Me in mod n arithmetic To decrypt a message N the recipient calculates Nd in mod n The result is the original message For example let p 5 and q l3 Then n 5gtllt l3 65 Also mp lq l4gtllt 248Wechoosee7 and with appropriate calculation we determine that cl 7 This works since 7 7 l in mod 48 If M 3 is a message to encrypt we must calculate 37 in mod 65 We can calculate 37 287 By dividing 2 l 87 by 65 we will see the remainder is 42 Thus 37 42 in mod 65 Thereforewe encrypt M 3 as N 42 To recover the original message we compute Nd in mod 65 In this example we recall that d 7 We must then compute 427 in mod 65 This is already a problem with many scienti c calculators because we need an exact answer With a more sophisticated device we see that 427 230539333248 Dividing by 65 we can see that 427 3 in mod 65 Thus decrypting 42 gave us back our original number The key fact about mod arithmetic is that if M is a number such that it and n have no common factor then MPquotqquot l in mod n This result is known as Euler s theorem after its discoverer Leonard Euler who published it in I736 In practice with today s computers the prime numbers p and q are chosen to have on the order of 200 digits As we will discuss the reason they are chosen so large is to make the system secure We will illustrate the use of this system with a piece of software which does numerical and symbolic calculations An example of the calculations can be found on the course website under the materials link entitled RSA calculations The information n and e are public informationThe number cl is private Since it is easy to nd cl from having p and q those must also be private Similarly m must be private because cl can be found from knowing e and m How Secure is RSA Since n and e are public and since the encryption can be broken by knowing p and q how hard is it to break We just have to factor n in order to break the code Moreover since the method is public knowledge anybody who wishes to break the code knows that they can break it by factoring n The important fact which implies that RSA is secure is that the amount of time it takes to factor a large number is very great For example if n were a 400 digit number then nobody knows how to factor n in a person s lifetime even with using any possible computer FGSOU rces It is unknown whether or not there is a method for factoring which can be done quickly enough to make RSA an inadequate encryption system Simply improving computer speeds to make factoring large numbers plausible is not going to prevent RSA from continuing to be useful Euclid proved over 2000 years ago that there are in nitely many prime numbers Therefore we can choose primes as large as we want By choosing them large enough so that current computers cannot factor in a reasonable time using RSA is then a good encryption method Euclid was also responsible for the method computers use for computing the integer d once e p and q are chosen His method is so easy to use that more ef cient methods haven t been needed in spite of the fact that his method is over 2000 years old Just how long does it take to factor In August I977 Martin Gardner wrote about RSA in Scienti c American He posed the following problem if the following number has two prime factors nd both factors RSA l 29 l I438 l 625757888867669235779976 I466 l 20 l 02 l 82 9672 24236256256 l84293570693524573389783059 7 23563958705058989075 l4759929002687954354 l7 He claimed that it would take a huge amount of time maybe billions of years for the number to be factored Many people found this problem interesting A group of people devised a method to break up the problem into many small parts With the help of around 600 people the group factored the number in I994 about l7 years after the problem was posed See httpwwwmathokstateeduwrightdnumthry rsa29htm for a discussion on the effort put in to nd how to factor this number More Probability Poker Hands and some issues in Counting Data From Thursday Everybody flipped a pair of coins and recorded how many times they got two heads two tails or one of each We saw that the probability of getting two heads is 25 and that the probability of getting one of eachis50 The summary of the data is as follows Outcome Two Tails Number Fraction Everybody also rolled two dice 20 times and determined the sum The tabulation of the data is as follows Sum ofTwo Dice Number Fraction The theoretical probability of getting a sum of l2 eg rolling a double six is 36 since of the 36 outcomes of rolling two clice one of them results in a sum of l2 ln decimal form this is about 028 or very close to what the class data was Poker Hands 7 39 iS39 Iquot xx I Poker is played with a deck of 52 cards Each card has a suit and a value a 900 9 D 9 09 GMD 9l no gt O F I i39 990 64 are as O 99 o ov 3 5 4 0 No 334 M 2 CC Q C c The suits are spades 0 hearts V diamonds Q and clubs 0 0 There are I3 values 2 through OJaclt Queen King and Ace A poker hand is made up of 5 cards The different poker hands are from best to worst are Royal Flush Straight Flush 6 Q Q Q 00 40 Four of a Kind 22124 a 4 QVQVO K K 3 3 3 Full House 9 1 112619 vvvv VV VV Straight Vi 3ofak39nd 5388 39 mol 4 Hand Example Royal Flush A4 KQQQJQ I04 Straight Flush J6 IOQ9Q8 7Q 4 ofa kind 848V8 8IJV Full House 4V4 4IJ JI Flush K Io 8 7 3 Straight QQJO Io 9 84 3 ofa kind 8398 8 0J396Q 2 pair 8398J YOJ39AQ pair 8398 IOIOJ39KOIO l4 Royal flush A K 2 IO in the same suit Straight flush 5 consecutive cards in the same suit 4 of a kind 4 cards of the same value Full house 3 cards of the same value and a pair Flush 5 cards in the same suit Straight 5 consecutive cards of any suit An ace can be low or high 3 of a kind 3 cards of the same value I pair 2 cards of the same value How many poker hands are there The number is how many ways you can choose 5 cards out of 52 This number is usually denoted 52C5 or 52C5 or 552 It is also called a binomial coef cient How many ways are there to choose I item out of 5There are 5 ways How many ways are there to choose 2 items out of 4 If the items are labeled a b c d we could have ab a c a d b c b d c d so there are 6 ways provided that the order in which we choose them does not matter like in a poker hand l8 There is a formula to compute binomial coef cients for any pair of numbers It is n ngtzlt nI nr nCr r nr rgtzltr 2gtzlt where n means I 2 3 n Many scienti c calculators have n buttons and many have buttons or menu items to calculate nCr Some values of n are As an example of this formula we see that nCl n for any number What this means is that if you choose I item out of nthere are n ways to do this Another example is that nC2 ngtzltnl2 This comes from canceling terms in the formula For example 4C2 4 2 2 24 22 6 Alternatively 4C2 432 6 If you calculate 52C5you will get 52C5 2598960 Thus there are 2598960 possible 5 card poker hands Excel can compute nCr and n It uses the commands combinnr and factn respectively What is the probability of getting a royal flush when dealt 5 cards There are 4 ways to get a royal flush since the only choice is which suit you get So the probability is 4 2598960 which is about I out of 600000 deals 24 In order to compute the probability of other hands one approach is to decide how many things you need to choose in order to write down a hand and then determine how many ways each of the choices can occur For example to count roya flushes we saw that you only have to choose a suit Counting Independent Events If one event does not affect the outcome of another they are called independent To count the number of ways a pair of independent events can occur multiply the number of ways each way can occur Example Rolling two clice is an example of two independent events what you get on one clie does not affect what can happen on the other Since there are 6 outcomes for rolling one clie there are 6 6 36 outcomes for rolling two clice How many ways are there to get a straight flush To choose a given straight flush you must choose a suit and a starting or ending value for the 5 in a row There are 4 choices for the suit What suit you choose does not affect the choice of starting value for the 5 in a row There are IO possible starting values A through IO However if we want a straight flush which is not a royal flush we cannot start at IO so there are 9 choices Therefore there are 4 9 36 total straight flushes The probability of a straight flush which is not a royal flush is then 36 2598960 What is the probability of a 4 of a kind An example is 848V8 8IJV We must count how many 4 of a kinds there areTo get a 4 of a kind you must choose the value of the 4 of a kind and choose the remaining card There are l3 choices for the value of the 4 of a kind The 5th card can be any of the remaining 48 cards So there are 48 choices for it 3 The number of four of a kinds is then 348624 and so the probability of a full house is 624 2598960 A full house consists of a 3 of a kind and a 2 of a kind What is the probability of getting a full houseAn example is 4V4 4IJQJIo To have a full house you must choose the value of a 3 of a kind and the value of a 2 of a kind You must also choose which 3 cards make up the 3 of a kind and which 2 make up the 2 of a kind This is one of the more complicated counts There are 3C 3 ways to choose the value of the 3 of a kind There are then 2C I2 ways to choose the value of the pair There are 4C3 4 ways to choose the three cards for the 3 of a kind There are 4C2 6 ways to choose the 2 cards for the pair So the number of ways to get a full house is 3gtlt 2463744 The probability of a full house is then 3744 2598960 a little worse than I out of 4000 hands Voting Issues Problems and Systems continued Last time we discussed four voting systems plurality voting the Borda count sequential pairwise voting and the Hare system We review each of these systems and recall the problems that each have Plurality Voting With plurality voting voters pick one candidates as their preferred candidate The winner is the one who has the most votes The winner does not necessarilty have a majority of the votes This commonly happens when there are 3 or more candidates With plurality voting it is possible to have a runoff election between the two candidates who receive the most votes A candidate is a Condorcet winner if he or she is the preferred candidate based on head to head competition with each candidate A voting system satis es the Condorcet winner criterion if the Condorcet winner if there is one always wins the election We saw an example last time to show that plurality voting does not satisfy the Condorcet winner criterion The Borda Count In the Borda count voters rank order the candidates If there are n candidates each rst place vote is worth nl points each second place vote is worth n2 points and so on The person who received the most points wins the election Independence of Irrelevant Alternatives it is impossible for a nonwinning candidate B to change to winner unless at least one voter reverses the order in which they listed B and the winner We saw last time that the Borda count does not satisfy this condition Sequential Pairwise Voting In this voting system voters rank candidates as in the Borda count The winner is determined by comparing pairs of candidatesThe loser between a comparison is eliminated and the winner is then compared to the next candidate The last person remaining is then the winner of the election This system requires ordering the candidates to decide the order of comparison Pareto condition if everybody prefers one candidate to another then the latter is not elected An example we considered last time shows that sequential pairwise voting does not satisfy this condition The Hare System In the Hare system candidates are ranked The candidate or candidates with the fewest number of rst place votes is eliminated This process continues until one candidate remains and is then elected Once a candidate is elected we remove that candidate from each ballot For example if B is eliminatedthen a ballot which lists C gt B gtA would then be reinterpreted to have C gt A That is C would be listed rst and A second Monotonicity Criterion if no voter were to switch hisher preference between the winner and another then the outcome of the election would be the same We saw that the Hare system does not satisfy this criterion The four systems we have considered Plurality voting the Borda count Sequential Pairwise voting and the Hare system each violates at least one of the following conditions the Condorcet winner condition independence of irrelevant alternatives the Pareto condition and monotonicity The following table summarizes how each system behaves with respect to each of the conditions A yes means the system satis es the condition CWC Pareto Plurality no yes Borda no yes Sequential no Hare CWC CondorcetWinner Condition A Independence of Irrelevant Alternatives Mono Monotonicity Condition l2 How would the I998 Minnesota gubernatorial election come out with other systems To check this let s suppose the voters would rank the three candidates Coleman Humphreys and Ventura as follows This table is not based on exit polls I made up the table trying to make a reasonable guess as to what would have happened Recall thatVentura received 37 of the rst place votes while Coleman received 35 and Humphreys 28 Borda count With the Borda count since there are three candidates we assign 2 points for rst place votes I point for second place votes and 0 points for third place votes To make it easier we pretend there are IOO votes so the percentage refers to the number of votes second place votes 4O 42 second place votes 35 4O 28 42 V 37 IS We computed Coleman s totals by 35gtllt240gtllt l 25O7040 HQ The other totals were computed similarly Thus with the Borda count Coleman wins the election Sequential pairwise voting 20 25 8 H c H C H V V V C H H C If we use sequential pairwise voting and order them C HV then Coleman is preferred to Humphreys 55 to 45 so Humphreys is eliminated Since Coleman is also preferred 55 to 45 over Ventura so Coleman is elected in this system It turns out that in this election the order in which we list the candidates does not affect the outcome I8 Hare system If we use the Hare systemthen Humphreys is eliminated since he received the fewest rst place votes 28 compared to 35 and 37 for the other two candidates We then reinterpret the ballot by eliminating Humphreys This gives After reinterpreting the ballots Coleman then has 55 rst place votes toVentura s 45 so Coleman would win under the Hare system So in all of the systems other than plurality voting Coleman would win the election The I992 Presidential Election Let s make an estimate of how the voting would have been conducted if voters ranked the three main candidates and determine who would be elected in each of the four systems we have studied I ve made a reasonable attempt to predict how voters would rank the candidates in order to come up with the following table 30 3 2 25 6 l3 Clinton Clinton Bush Bush Perot Perot Bush Perot Clinton Perot Clinton Bush Perot Bush Perot Clinton Bush Clinton Plurality voting Clinton wins since he received more rst place votes than the other two candidates Borda count2We assign 2 points for each rst place vote and I point for each second place vote To make the arithmetic easier we interpret the percentages as votes Clinton 43 rst place votes and IS second place votes Total points43 gtk2 l8gtllt l I04 Bush 37 rst place votes and 43 second place votes Total points 37gtllt243gtllt l II7 Perot l9 rst place votes and 38 second place votes Total points l9 2 38 l 76 Since Bush has the most points he would be elected 23 Rank 30 3 2 25 6 l3 First Clinton Clinton Bush Bush Perot Perot Second Bush Perot Clinton Perot Clinton Bush Third Perot Bush Perot Clinton Bush Clinton Pairwise sequential voting Let us first order the candidates Bush Clinton Perot We compare Clinton and Bush head to head Bush is preferred to Clinton by SI of the voters Therefore Clinton is eliminated Bush is then compared to Perot head to head and Bush is preferred Perot is then eliminated Bush is the one remaining so he is elected 24 Rank 30 3 2 25 6 l3 First Clinton Clinton Bush Bush Perot Perot Second Bush Perot Clinton Perot Clinton Bush Third Perot Bush Perot Clinton Bush Clinton Hare system We rst eliminate the candidate with the fewest rst place votes This is Perot so he is eliminated We next reinterpret each vote to rank only Clinton and Bush This yields the following table Original vote Rank 30 I396 I293 2596 6 I396 FHSt Clinton Clinton Bush Bush Perot Perot Second Bush Perot Clinton Perot Clinton Bush TI rd Perot Bush Perot Clinton Bush Clinton Reinterpreted vote Rank 30 I396 I293 2596 6 I396 FHSt Clinton Clinton Bush Bush Clinton Bush Second Bush Bush Clinton Clinton Bush Clinton 26 In the reinterpreted vote Clinton receives 49 of the rst place votes and Bush 5 Therefore Clinton is eliminated Thus Bush is elected with the Hare system Thinking about the various voting systems we have considered and the fact that all of them violate a reasonable condition leads one to ask the following question Is there a voting system which satis es all four conditions we have introduced Thinking about the various voting systems we have considered and the fact that all of them violate a reasonable condition leads one to ask the following question Is there a voting system which satis es all four conditions we have introduced Kenneth Arrow a Nobel prize winning economist proved in 95 that all voting systems have flaws More precisely he proved that there does not and cannot exist a voting system which satis es both the CondorcetWinner condition and the Independence of Irrelevant Alternatives Arrow s theorem says therefore that no matter what voting system we use there will be flaws with it To determine what voting system to use in a given situation we should then consider what advantages and disadvantages systems have and what are our priorities We can then try to pick a reasonable system that will reflect the priorities ln practicethis is a complicated political problem Graph Theory Graph theory was invented by a mathematician named Euler in the 8th century We will see some of the problems which motivated its study However it wasn t studied too systematically until the latter half of the 20th century Computer Science applications have driven its development since many of its problems are naturally modeled via graphs More speci cally we will focus on three or four problems The rst the historical motivation of the subject is the 7 bridges of Konigsburg problem The second is how to nd your way through a maze The third is how many colors does it take to color a map 7 Bridges of Konigsburg The origin of graph theory was the following problem In the city of Konigsburg in present day Lithuania there are seven bridges passing over the river and connecting various parts of the city The following picture shows the city and its bridges k391f 5 quot quot V 1 vn L a a af rm gt b l 1 7 Fquot quot M 39 39 N in I arm 1quot fishquotm 5 The problem possibly originating from people strolling around the city is this Is it possible to cross each bridge exactly once and end up where you started Alternatively is it possible to cross each bridge exactly once regardless of where you end relative to where you started Euler solved this problem by representing the situation as a structure which we now call a graph This use of the term graph is different than that occurring in algebra We will illustrate how Euler solved the 7 bridges problem We will also address other problems which can be solved by the use of graph theory What is a graph A graph consists of a bunch of points usually called vertices Some of the vertices are connected to each other When a vertex is connected to another that connection is called an edge We can draw edges as straight line segments or curves Here are some examples of graphs 8 The top two graphs look different but they represent the same information Both have the top three vertices connected to each of the three bottom vertices That the edges in the top left gure sometimes are drawn with straight lines and sometimes with curves does not matter Nor does it matter where the vertices are positioned Euler represented the 7 bridges problem as a graph in the following way Each land mass was represented as a vertex Two vertices are connected by an edge if the corresponding land masses are connected by a bridge The graph representing the problem is shown on the next slide As we have indicated the shape of the edges is irrelevant Only what matters are which vertices are connected Since there are 4 land masses there are 4 vertices The 7 bridges correspond to 7 edges Graph of the 7 Bridges of K nigsburg A path on a graph is a journey through various vertices where you can go from one to another as long as there is an edge connecting them A circuit is a path which returns to the starting point This idea comes from the original motivation for graphs A path in the 7 bridges graph can be though of as a walk across various bridges In honor of Euler s work we call a path which crosses each edge exactly once an Euler path If the Euler path starts and ends at the same vertex then it is called an Euler circuit In terms of graph theory the 7 bridges problem is then is there an Euler circuit or Euler path on the graph representing Konigsburg Euler discovered that in order to have an Euler circuit the number of edges connected to each vertex must be even He also saw that in order to have an Euler path every vertex except for at most two must have an even number of edges connected to it If two have an odd number of edges those could be the start and the end of the path The graph to the left has an Euler circuit The one to the right does not but it does have an Euler path when one starts at the top left vertex and nishes at the top right Roughly Euler reasoned that if there was an Euler path or circuit then for any vertex other than the start or nish each time you reached the vertex you need two edges one to get there and one to get away The number of edges connected to the vertex is then twice the number of times you cross the vertex and so is an even number Since the 7 bridges graph has 3 vertices with an odd number of edges connected to them there is no Euler path or Euler circuit Thus it is impossible to walk across each of the 7 bridges exactly once Mazes are often dif cult to solve because it is hard to distinguish dead ends Identifying and then ignoring dead ends will result in a path through the maze Mazes appear to be dif cult in part because they cause one to make lots of turns even when you don t actually have to choose one direction or another By representing a maze as a graph we have a method to be able to ignore the turns which only complicate the look of a maze To represent a maze as a graph we need to focus on what is the important information of a maze The turns which are forced upon us without requiring us to make a decision are not important What we need to consider are the junctions where we have a choice of a turn We represent a maze as a graph by letting the vertices be the junctions those spots where we have a choice of a direction to turn We also include the start and nish of the maze Two vertices are connected with an edge if you can get from one to another without crossing any other junction In other words if you go from one junction to another without having the choice of making a turn then those two junctions are connected with an edge How to draw the graph of a maze First draw all possible paths Those are shown in blue in the gure below to the right i Next erase the boundaries leaving only the paths This is not necessary but can help to do the next step Mark all the junctions including the start and nish Recall that the junctions are the vertices of the graph l l Draw the edges by connecting two vertices only if you can get from one to the other without crossing another junction Drawing the edges as straight lines makes the situation as simple as possible Dead ends can be represented as short paths that don t end at a vertex Alternatively they can be ignored especially if it is clear what are dead ends Once you have the graph nd a path from the start to the nish Comparing the graph and the original drawing of paths will then give you a route through the maze The mazes shown in class today were created at the web site httphereandabovecommaze Apportionment con nued Jefferson s Method modi ed a bit To relate to the other apportionment methods we discuss a modi cation of Jefferson s method which will then use the same mathematical ideas as the methods of Webster and HillHuntington We will illustrate this and the other methods with the following data and an assumption that the house has 00 members State Population A 30000000 B 000000 2000000 0000000 5000000 58000000 We rst calculate the quota of each state Recall that we get this by computing Population of the state H 539 Population of the US X ouse lze We then round the quotas down to get the state s lower quotas which will be the tentative apportionment Tentative POPu39a on Apportionment 30000000 5 000000 2000000 0000000 5000000 58000000 Next we calculate a critical multiplier How this is done varies between the different methods In Jefferson s method the critical multiplier for a state is found by the formula Critical Multiplier tentative apportionment for a state quota Critical Multiplier l tentative apportionment for a state quota For example to get the critical multiplier for State A we calculate I 5572525724 I0053 The critical multipliers for these ve state are as follows Po ulation Tentative Critical P Apportionment Multiplier 30000000 5 0053 000000 600 2000000 600 0000000 0440 5000000 0053 58000000 We then look at the state whose critical multiplier is the closest to We then multiply each state s quota by this number to get the adjusted quota We see that this multiplier is 0053 We then multiply each state s quota by 0053 to get the adjusted quota To get the new tentative apportionment we round down the adjusted quota 9 The multiplier closest to l is in blueThe following table lists the adjust quota and new tentative apportionment Tentative Apportion ment Critical Multiplier Adjusted Quota New Tentative Apportion ment 5 I 0053 52000 600 733 3 600 3467 I7 I 0440 7333 25 0053 26000 97 0 We repeat this process until we have apportioned the right number of seats In this case we have to do this one more time More speci cally we recalulate the critical multipliers to take into account the new tentative apportionment We do this by calculating l new tenative apportionment quota I new tenative apportionment quota For example the new critical multiplier for StateA is I 525724535724 0247 Tentative Apportion ment Critical Multiplier Adjusted Quota New Tentative Apportion ment 52 I 0247 53000 600 767 3 600 3533 I7 I 0440 7667 26 0440 26500 99 02 Now that the tentative apportionment has reached the correct size of I00 house members we have the nal apportionment using Jefferson s method Apportionment using jefferson s Method Population Quota Apportionment 30000000 5 724 53 000000 724 2000000 3448 3 0000000 724 I7 5000000 25862 26 58000000 00 The HillHuntington Method This method has been used to apportion the House of Representatives since I940 and continues to be used today It is similar to Jefferson s and Webster s method The main difference is in the method of rounding the quota to get the tentative apportionment This method is also used to apportion the NMSU Faculty Senate l5 In Jefferson s method one always rounds down In the HillHuntington method the rounding is more complicated Otherwise we follow the same basic steps making a tentative apportionment calculating a critical multiplier adjusting the quota and making a new tentative apportionment Recall that if q is the quota of a state the lower quota is obtained by rounding q down and the upper quota is obtained by rounding up In the HillHuntington method if q is the quota of a state we compute a number qgtllt by rst multiplying the lower quota with the upper quota then taking the square root We round q down if q lt q We round q up if q gt qgtllt or if q q For example if a state has quota q 5 l 72 we calculate the square root of 5 52 This is approximately 5 L49 This means qgtllt 5 L49 Since this is less than q in the HillHuntington method we would round q up to get the tentative apportionment We will go through this method with the same data as we used for the Jefferson method l8 We rst calculate qgt lt for the quota q for each state and then make a tentative apportionment Tentative POPUIatIO Apportionment 30000000 52 000000 2 2000000 4 0000000 8 5000000 26 58000000 Note that this initial apportionment allocated too many seats In this methodthe initial apportionment could be either too large or too small Besides how to round the other difference with the Jefferson method is how we calculate the critical multiplier If n is the tentative apportionment for a state then the critical multiplier for the state is calculated in the HH method by one of the following two ways 20 If the tentative apportionment is too small then nnl Critical Multiplier for a state quota On the other hand if the tentative apportionment is too largethen nnl Critical Multiplier for a state quota Getting back to our example since the tentative apportionment assigns 02 seats which is too large we use the formula xnnl Critical Multiplier for a state quota to determine the critical multipliers For example to compute the critical multiplier for State A we calculate 52 52 I 5 l 724 Once we nd all the critical multipliers we identify the one that is closest to We then multiply that times each quota to obtain the adjusted quotas Since the closest multiplier to l is 0996 we multiply that number with each quota to get the adjusted quota For example 724 996 77 Tentative Critical Adjusted Apportionment Multiplier Quota 52 0996 5 l 498 2 0820 7 7 4 07IO 3433 l8 0957 I7 I 66 26 0986 25749 Next we nd q for each of the new quotas We use the same formula as before given q we multiply the lower quota and the upper quota then take the square root For example with the adjusted quota of 77 for State B the lower quota is l and the upper quota is 2 Then qgtllt for this state is the square root of l 2 which is about 44 Adjusted Quota Adjusted Quota New Tentative Apportionment 5 498 5 498 52 77 44 2 3433 3464 3 766 7493 I7 25749 25495 26 IOO 02 Since the tentative apportionment is the right number 00 seats we are nished Apportionment using the HillHuntington Method State Population Quota Apportionment 30000000 5 724 52 000000 724 2 2000000 3448 3 0000000 724 7 5000000 25862 26 58000000 00 Comparison of jefferson ancl HillHuntington Population Quota jefferson Apportionment HillHuntington Apportionment 30000000 5 724 53 52 000000 724 2 2000000 3448 0000000 724 5000000 25862 58000000 00 Comparison of jefferson ancl HillHuntington Pop jefferson Apport Population Seats Hill Huntington Apport Population Seats 30000000 53 566038 52 576923 000000 000000 2 500000 2000000 666667 666667 0000000 588235 588235 5000000 576923 576923 58000000 This example shows one feature ofJefferson s method it is possible for a state to receive more than its upper quota This happened to State A It is an indication thatJefferson s method favors large states It then violates the quota condition each state receives either its lower quota or its upper quota Hamilton s method satis es the quota condition since each state receives either its lower or its upper quota We saw that Hamilton s method produces paradoxes but Jefferson s method violates the quota condition It turns out that the HillHuntington method also violates the quota condition although our example does not show this Maybe there is an apportionment method that does not produce paradoxes and satis es the quota condition Unfortunately not Balinski and Young showed in I982 that any apportionment method that does not violate the quota rule must produce paradoxes and any apportionment method that does not produce paradoxes must violate the quota rule Therefore it is impossible for a method to satisfy the quota rule and have no paradoxes Encoding and Encrypting Information Information is often encoded numerically By using some mathematics to encode information in an appropriate way we can overcome problems encountered in dealing with the information Different situations have different problems We will consider three different ways to encode information to overcome three different types of problems Each type we will introduce with one type of situation How can one give a code such as a bar code to a grocery store item in such a way to eliminate or minimize the chance that the item s price is registered correctly You want to make sure the item is not mistaken for another 2 How can one encode music or video on a cd or dvd in such a way that small imperfections such as scratches do not result in a loss of data 3 How can you encrypt data such as credit cards so that you can transmit the data and have the intended recipient recover the data but anybody else cannot recover it Identi cation Numbers Today we will talk about the rst of the three situations described above We will focus on two examples UPC s and lSBN s UPC stands for universal product code and ISBN stands for international standard book number The UPC 7 1890814447 3 Commercial products such as grocery store items are identi ed with a universal product code This l2 digit numerical code uniquely identi es an item It appears on the item both as a number and as a bar code The rst string of digits after the rst identify the manufacturer and the second string of digits identify the item The last digit is the one we will focus on It is called the check digit Its purpose is to detect errors We shall see that if one single digit in the UPC is misreadthen the resulting sequence will be determined to be invalid To see if a l2 digit sequence of digits is a valid UPC perform the following computation multiply the rst third fth digits by 3 and the others by Add up the resulting numbers If the sum is evenly divisible by ID then the sequence is a valid UPC For example consider the sequence 7 8908 l4447 3 Sum 24908342423O The sum l IO is evenly divisible by IO since its last rightmost digit is a O This shows that the sequence is a valid UPC When an item is scanned the scanner performs this computation If the sequence is determined to be validthen the item s price is retrieved from the store s computer How is the check digit determined When a manufacturer produces an item and assigns a UPC the rst chunk of the sequence is the code for the manufacturer They then select the second chunk to identify the item Finally they have to determine the check digit How do they do this We will see how through an example Suppose O 25 I92 59452 is to be a UPC What should be the check digit We repeat the calculation to check for validity weights 33333 digits 25l9259452 sum 2527259l25694 This sum needs to be divisible by IO and must be a digit The only digit that works is 6 the sum is then IOO So the check digit is 6 and the full UPC is O 25 I92 59452 6 Another way to nd the check digit is to take the sum of 94 divide by IO IO goes into 94 nine times with 4 left over Subtract the left over from IO to get the check digit The numbers 3 and used in the calculation are called weights We shall see other weights in other identi cation number schemes To Find the Check Digit for a UPC To summarize to nd the check digit for a UPC take the rst part of the number multiply each digit by the corresponding weight number 3 or I add up all the terms Either divide the result by ID and subtract the remainder from IO to get the check digit Alternatively nd the digit 0 through 9 which when added to the sum results in a number evenly divisible by ID There is a unique digit which will make the calculation work above
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'