Skip to content
Textbook Guides

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual is an essential tool for mastering your textbook, offering detailed solutions and helpful explanations.

Preview 16 of 500 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    Guide with Full Solutions for COMAP’ s For All Practical Purposes Tenth Edition Lauren Fern University of Montana

  2. Page 2
  3. Page 3
    Read page 3 as text

    Table of Contents Part I: Management Science Chapter 1: Urban Services 1 Chapter 2: Business Efficiency 21 Chapter 3: Planning and Scheduling 41 Chapter 4: Linear Programming and the Transportation Problem 69 Part II: Statistics: The Science of Data Chapter 5: Exploring Data: Distributions 147 Chapter 6: Exploring Data: Relationships 176 Chapter 7: Data for Decisions 206 Chapter 8: Probability: The Mathematics of Chance 223 Part III: Voting and Social Choice Chapter 9: Social Choice: The Impossible Dream 247 Chapter 10: The Manipulability of Voting Systems 275 Chapter 11: Weighted Voting Systems 301 Chapter 12: Electing the President 323 Part IV: Fairness and Game Theory Chapter 13: Fair Division 334 Chapter 14: Apportionment 348 Chapter 15: Game Theory: The Mathematics of Competition 373 Part V: The Digital Revolution Chapter 16: Identification Numbers 389 Chapter 17: Encoding Information 399 Part VI: On Size and Growth Chapter 18: Growth and Form 418 Chapter 19: Symmetry and Pattern 432 Chapter 20: Tilings 444 Part VII: Your Money and Resources Chapter 21: Savings Models 454 Chapter 22: Borrowing Models 469 Chapter 23: The Economics of Resources 483

  4. Page 4
    Read page 4 as text

    1 Chapter 1 Urban Services Chapter Outline Introduction Section 1.1 Euler Circuits Section 1.2 Finding Euler Circuits Section 1.3 Beyond Euler Circuits Section 1.4 Urban Graph Traversal Problems Chapter Summary Management science, or operations research, is a branch of mathematics that uses mathematical methods to find optimal solutions to management problems. Some of these problems involve finding efficient routes for services such as collecting coins from parking meters, collecting garbage, and delivering mail. The mathematical structure known as a graph is useful in analyzing routes. A graph consists of a finite set of vertices together with edges connecting (some, all, or no) pairs of vertices. A path in a graph is a connected sequence of edges that begins and ends at a vertex. A path is called a circuit if it begins and ends at the same vertex. In many routing applications (e.g., mail delivery or garbage collection), the best solution would be a circuit that uses each edge (e.g., sidewalk or street) of an appropriate graph exactly once. Such circuits are called Euler circuits , in honor of the Swiss mathematician Leonhard Euler. In order to have an Euler circuit, a graph must satisfy two conditions: It must be connected (i.e., it must have a path between any pair of its vertices); and each of its vertices must have even valences (the number of edges meeting at that vertex). If the graph for a particular routing application does not have an Euler circuit, the best we can hope to do is find a circuit of minimum length. The problem of finding such a circuit is known as the Chinese postman problem . The solution process relies on “ eulerizing ” a graph, judiciously duplicating edges of the graph to produce a connected graph with even valences so that the total length of the duplicated edges (total number if all edges of the graph have the same length) is as small as possible. The Euler tour in the “new” graph can be traced on the original by interpreting the use of a duplicated edge as a reuse of the original edge it duplicates. There are efficient procedures for finding good eulerizations and for solving the Chinese postman problem. The “ edge-walker ” method in the text is good for rectangular networks. More sophisticated procedures are needed in general.

  5. Page 5
    Read page 5 as text

    2 Chapter 1 Urban Services Skill Objectives 1. Determine by observation if a graph is connected. 2. Identify vertices and edges of a given graph. 3. Construct the graph of a given street network. 4. Determine by observation the valence of each vertex of a graph. 5. Define an Euler circuit. 6. List the two conditions for the existence of an Euler circuit. 7. Determine whether a graph contains an Euler circuit. 8. If a graph contains an Euler circuit, list one such circuit by identifying the order in which the vertices are used by the circuit, or by identifying the order in which the edges are to be used. 9. If a graph does not contain an Euler circuit, add a minimum number of edges to “euler i ze” the graph. 10. Find an Euler circuit in an eulerized graph and “squeeze” it onto the original graph. Be able to interpret, in terms of the original graph, the use of duplicated edges in the eulerization. 11. Identify management science problems whose solutions involve Euler circuits. Teaching Tips 1. The concept of connectedness could be explored further by considering trees as opposed to circuits. This could begin to prepare the student for the work on trees in connectedness. 2. In preparation for assigning Exercise 12, you may want to explore in class whether the placement of the vertices representing the cities affects the graph. In particular, consider three cities whose positions are collinear. 3. Figure 1.13 demonstrates the process of adding an edge in order to eulerize a graph. Students are sometimes confused by the fact that this added edge is curved rather than straight and attempt to attach unwarranted significance to this. A helpful explanation is that it is curved only so that it won ’t be confused with the original segment. In addition, you may want to emphasize that the curve could be drawn on either side of the original edge and that it indicates a retracing of that edge. 4 . Ask students to construct a graph of a several-block area of their neighborhood and then look for an Euler circuit for the letter carrier to use. If an Euler circuit does not exist, ask students to produce optimal eulerizations. 5. An underlying principle of this chapter is the fact that a mathematical model, in this case a graph, is an abstraction of reality. The solution suggested by the model need not imply that streets would be added to an existing street network simply for the purpose of creating an Euler circuit. 6. Emphasize the differences between Skills Check Exercises 27 and 29. The two exercises are asking two different questions for the same graph.

  6. Page 6
    Read page 6 as text

    Guide with Solutions 3 Research Papers Exercise 48 indicates that the problem situation resembles the one that inspired Euler. This refers to the historical Königsberg Bridge Problem (mentioned in Spotlight 1.1). You may choose to ask students to research the history of this town (once the capital of East Prussia) and this problem. Websites can be found that contain a map of the area, including the bridges. Also, you may choose to ask students to further investigate Euler’s 1 736 paper on the problem, which was divided into 21 paragraphs. Students also can research the life and contributions of the French mathematician Louis Poinsot (1777 – 1859). Other problems posed by Euler, such as the Thirty-Six Officers Problem, may also be of interest to students. In 2007, UPS implemented an idea to save the company money resulting from rising gas prices. The idea was to minimize the number of left-hand turns. In the first year, this initiative saved the company about 30 million miles and about 3.3 million gallons of fuel. Have students research “t urn pena lties.” They may wish to include in their discussion the biography of J. Edgar Hoover entitled No Left Turns , by Joseph L. Schott. With the rising cost of gas, have students write about how such a plan saves money and reduces emissions. Students may choose to make a map of the city/town in which they live and determine routes that implement this policy and see how they compare to routes that do n’t. An extension to this paper can be researching the impact of roundabouts on time and cost of traveling. Collaborative Learning Euler Circuits As an introduction to this chapter, duplicate the following exercise on Euler circuits and ask your students to answer the questions after discussing them in groups. (Do not introduce technical terms such as graph, edge, vertex, valence, or Euler circuit yet.) You will find that most of the students are successful in answering questions (a) and (b), but perhaps not question (c). If in fact they do have difficulty answering part (c), call their attention to the number of edges meeting at each of the vertices. (Resist using the word valence .) Ask them to count these numbers for each of the graphs and then try again to answer part (c) by looking for a pattern. Eulerization a. Which of the following diagrams can be drawn without lifting your pencil from the paper and without retracing any lines? b. Which can be drawn as in part (a), but with the additional requirement that you end the drawing at the starting point? c. What do the diagrams that could be drawn in part (a) have in common? What about the diagrams that could be drawn in part (b)? In other words, try to determine simple conditions on a diagram that enable you to predict, in advance, whether or not it can be drawn according to the requirements in parts (a) or (b).

  7. Page 7
    Read page 7 as text

    4 Chapter 1 Urban Services In each of the graphs below, an Euler circuit does not exist because there are vertices with odd valences. It is possible to convert such graphs to graphs having all vertices of even valence by duplicating one or more edges. For example, in the graph vertices A and C each have valence 3. Hence, if we duplicate edge AC, we obtain a modified graph in which each vertex has an even valence. Do the same for each of the following graphs and then answer the questions that follow.

  8. Page 8
    Read page 8 as text

    Guide with Solutions 5 1. If a graph has 4 vertices with odd valences, what is the minimum number of duplications necessary to convert the graph to one in which all of the vertices are of even valence? Can this minimum number always be achieved? 2. Take a campus map (often found in the university catalog or directory) and pick out several key locations (library, dormitories, computer center, bookstore, etc.) and the streets or paths that connect them. Then ask the students whether an Euler circuit exists for this network. If not, how many edges have to be duplicated? By changing landmarks, you can obtain several new problems.

  9. Page 9
    Read page 9 as text

    6 Chapter 1 Urban Services Solutions Skills Check: 1. c 2. 7; 8 3. b 4. 3 5. a 6. 16 7. a 8. B ; E 9. c 10. 7; 7 11. b 12. 1; 2; 4; 5; 10 13. c 14. 6 15. a 16. 9; 22 17. c 18. 8 19. c 20. a 21. 4 22. 12 23. a 24. 4 25. a 26. graph; digraph; graph 27. b 28. 9; 15 29. a 30. 13 Collaborative Learning: Euler Circuits: a. Diagrams (2), (3), (4), (5), (7), and (8) can be drawn without lifting the pencil from the paper. b. In (4) and (5) you can return to the starting point. c. In part (a), there are at most 2 vertices with odd valences, while in part (b) there are no vertices with odd valences. Eulerization: (1) Duplicate 1 edge. (2) Duplicate 2 edges. (3) Duplicate 3 edges. (4) Duplicate 9 edges. If there are 4 vertices with odd valences, then there will be a minimum of two duplications. However, this minimum can’t always be achieved, as we see from number (3) . Exercises: 1. (a) There are 6 vertices, each marked with a capital letter. (b) There are 9 edges. 2. (a) Three ways to get from C to A by traversing 4 edges are: CDBEA and CDFEA and CDEBA (b) Three ways to get from C to A by traversing three edges are: CDBA and CBEA and CDEA

  10. Page 10
    Read page 10 as text

    Guide with Solutions 7 (c) Three ways to start and end at B traversing four edges are: BDFEB and BCDEB and BAEDB 3. (a) (b) ADGIJHKLMLKHG (using other edges) HEDEBA is such a path. Four of the edges are deadheaded. 4. (a) There are 9 vertices and 8 edges. (b) You would need to add two edges. One possibility is as follows: (c) There are seven vertices of valence 2 and two vertices of valence 1. 5. (a) This diagram fails to be a graph because a line segment joins a single vertex to itself. The definition being used does not allow this. (b) The edge EC crosses edges AD and BD at points that are not vertices; edge AC crosses BD at a point that is not a vertex. (c) This graph has 5 vertices and 6 edges. 6. (a) 7 stores (b) 10 roads (c) CBF is a path. (d) EDFB is a path. 7. (a) 8 vertices (b) 13 edges (c) A : 4; B : 2; C : 3; D : 3; E : 4; F : 4; G : 3; H : 3 (d) A , D , and F (e) E , G , and H

  11. Page 11
    Read page 11 as text

    8 Chapter 1 Urban Services 8. (a) (b) Assuming that no cities are revisited and that one goes directly from an American city to a European one the routes are: NL , NLR, NLB , NLBR , NLRB , ML , MR , MB , MLR , MLB , MRL , MRB , MBL , MBR , MLRB , MLBR , MRLB , MRBL , MBLR, MBRL 9. E has valence 0; A has valence 1; H , D , and G have valence 2; B and F have valence 3; C has valence 5. E is “isolated.” E might have valence 0 because it is on an island with no road access. 10. (a) Yes. (b) No. There is no way to get from A to C , E , or H . (c) No. There is no way to get from A to F , H , or E . 11. (a) There are 4 vertices and 4 edges. (b) There are 7 vertices and 6 edges. (c) There are 10 vertices and 14 edges. 12. (a) There are five paths to choose from if you assume that no cities are revisited and that one goes directly from an American city to a European city. These are MLB , MLRB , MRB , MRLB , and MB . If you assume that you can travel between Miami and New York prior to going to Europe then you would consider the paths MNLB and MNLRB . If revisiting a city is allowed, then there are infinitely many paths. (b) There are five paths if domestic travel is not considered and seven paths to choose from if domestic travel is allowed. (c) In such a route, time and probably cost would be greater if you repeat a city prior to getting to the destination. 13. (a) Answers will vary. Possible answers include CGDBC. (b) (i) BD ; BFD (ii) CBF ; CGDF ; CGDBF (iii) GDBCG 14. In any of these graphs, two edges can be removed and the graph will become disconnected. One of the disconnected pieces will be a single vertex. 15. (a) (b)

  12. Page 12
    Read page 12 as text

    Guide with Solutions 9 (c) Note: Drawing and renderings can vary. The text answer for part (c) offers another drawing. Some other graphs for parts (b) and (c) could be as follows: (b) (c) (d) Yes. The sum of the valences of a graph with 8 vertices, each of valence 2, is 16. Thus, all such graphs have 8 edges. 16. (a) 2 + 3 + 3 + 0 = 8 (b) 2 + 2 + 2 + 2 + 2 + 1 + 1 = 12 (c) 28 (d) The number we obtain is twice the number of edges in the graph. (e) The fact that the sum of the valences of the vertices of a graph is always twice the number of edges in the graph follows from noticing that each vertex of an edge contributes a total of two to the sum because the edge has two endpoints. 17. Remove the two edges dotted in the figure below, and the remaining graph will be disconnected. Note: Other pairs of edges will also disconnect the graph. 18. (a) Yes, it is possible. (b)

  13. Page 13
    Read page 13 as text

    10 Chapter 1 Urban Services 19. (a) Yes, it is possible. (b) No. To have an Euler circuit, a graph cannot have odd-valent vertices. 20. (a) There are 8 vertices and 16 edges. (b) DGEDHGFAEFBACBHCD 21 . Drawings can vary. Possible renderings include the following: 22. (a) Yes, a disconnected graph can arise. One possible example is shown below: This gives rise to the disconnected graph: (b) (c) The edge might represent a bridge or tunnel. Recently, when a bridge collapsed because it was hit by a barge, there was a major disruption to the communities near the bridge on opposite sides of the river.

  14. Page 14
    Read page 14 as text

    Guide with Solutions 11 23. Drawings can vary. Possible renderings include the following: 24. The street direction will matter for a problem involving how long it will take to get between two street intersections and for routing a street sweeper that follows traffic rules. The street direction may not matter for an inspector checking manholes located in the middle of streets or a service that involves walking along either side of the street, such as inspecting sidewalks. 25. (a) The supervisor is not satisfied because all of the edges are not traveled upon by the postal worker. (b) The worker is unhappy because the end of the worker’s route wasn’t the same point as where the worker began. The original job description is unrealistic because there is no Euler circuit in the graph. 26. 27. There is such an efficient route. The appropriate graph model has an additional edge joining the same pair of vertices for each of the edges shown in the graph of Exercise 25. Adding those edges gives you the graph for Exercise 26. Since this graph is connected and even-valent, it has an Euler circuit, any one of which will provide a route for the snowplow. Routes without 180-degree turns are better choices. One possible route is indicated by the numbered routes. 28. (a) Pothole inspection or inspecting the centerline for possible repainting because it had faded. (b) Street sweeping, snow removal, and curb inspections in urban areas.

  15. Page 15
    Read page 15 as text

    12 Chapter 1 Urban Services 29. 30. (a) The graph is a rectangular network with two rows and three columns No extra edges need to be added. (b) 31. (a) The largest number of such paths is 3. One set of such paths is AGC , AHFC , and ABEIJC . (b) This task is simplified by noticing there are many symmetries in this graph. You may notice that starting with A , there are only three directions to go. Any number of paths greater than three would involve repeating an edge starting from A . (c) In a communication system such a graph offers redundant ways to get messages between pairs of points even when the failure of some of the communication links (edges removed) occurs. 32. Both are circuits; however, only graph (b) is an Euler circuit. 33. (a) No. It is not possible. There are odd-valent vertices. (b) The minimum number is four. (c) Answers will vary. One solution would involve duplicating edges CD , DE , FG , and AB . Another possible Euler circuit starting and ending at C is CDEFGHBKGKBAKJFEIJAICAC. The duplicated edges are shown below: 34. Do not choose edge 3, but edges 9 or 10 could be chosen. 35. Do not choose edge 2, but edges 1 or 10 could be chosen.

  16. Page 16
    Read page 16 as text

    Guide with Solutions 13 36. The following diagram shows one of many solutions for Figure 1.17a: The following diagram shows one of many solutions for Figure 1.17b: 37. 38. If one was outlining garden plots with a sprinkler hose, this tour would allow having the hoses as flat as possible because one hose would not have to cross another hose. 39. (a) A , C , E , and H are odd-valent. (b) Two edges, AH and CE , need to be dropped to produce a graph with an Euler circuit. Persons who parked along these stretches of sidewalk without putting coins in the meters would not need to fear that they would get tickets. 40. The curved edges on the first graph become double-traversals on the straight edges of the second graph.

484 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Mathematics study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.