P U P

Instructional Materials in
GEED 10053
Mathematics in the Modern World

compiled by

DMS Faculty

College of Science
Polytechnic University of the Philippines

2020
 for the sole noncommercial use of the
Faculty of the Department of Mathematics and Statistics
Polytechnic University of the Philippines

2020

Conributors:

Abdul, Alsafat
Atienza, Jacky Boy
Bang-as, Pamela
Bernardino, Rhea
Cabanig, Sarah Jean
Criseno, Regine
Dilla, Perlyn Mae
Duarte, Rafael
Elizon, Katrina
Equiza, Cynthia
Hernandez, Andrew
Isaac, Emelita
Lara, Jose Alejandro Constantino
Longhas, Paul Ryan
Macatangay, Shaina Lyra
Malvar, Rolan
Nuguid, Kenneth James
Saguindan, Ian
Sta. Maria, John Patrick
 Republic of the Philippines
POLYTECHNIC UNIVERSITY OF THE PHILIPPINES
COLLEGE OF SCIENCE
Department of Mathematics and Statistics

Course Title : MATHEMATICS IN THE MODERN WORLD

Course Code : GEED 10053

Course Credit : 3 units

Pre-Requisite : GENERAL MATHEMATICS, STATISTICS AND PROBABILITY (SHS)

Course Description :

The course deals with the nature of mathematics, appreciation of its practical, intellectual and
aesthetic dimensions, and application of mathematical tools in daily life.

COURSE LEARNING PLAN

Week Topics and Subtopics Learning Outcomes

I. The Nature and Language of Mathematics

Week 1 Nature of Mathematics

Sept. 14 1. Patterns and Numbers in Nature

to 2. Fibonacci Sequence
Sept. 20 3. Mathematics for Our World
Week Language of Mathematics
2-3
1. Propositions and Logical
Sept. 21 Connectives
to 2. Sets, Operations and Venn
Oct. 4 Diagrams
Problem Solving
Week
4-5 1. Inductive and Deductive
Reasoning
Oct. 5 2. Polya’s Guidelines for Problem
to Solving
Oct. 18 3. Mathematical Problems involving
Patterns

II. Mathematics as a Tool (Data Management)

Week Data Gathering and Sampling

6-7 Techniques

Oct. 19 1. Random vs. Non-probabilistic

to Sampling
 Oct. 31 2. Level of Measurements
3. Use and Misuse of Statistics

Data Presentation
1. Frequency Distributions
2. Statistical Graphs and Charts
Week Descriptive Statistical Measures
8
1. Measures of Central Tendency
Nov. 3 2. Measures of Dispersion
to 3. Measures of Position (Quantiles)
Nov. 8
SPECIAL TOPICS
*Note: Graphical Solution of LP Models and Mathematics of Graphs and Networks are required special topics
for the programs under the ff. colleges: Architecture and Fine Arts (CAFA), Computer and Information Sciences
(CCIS), Engineering (CE), Science (CS) and Technology (ITECH).
Week Graphical Solution of LP Models
9-11
1. Linear Inequalities and their
Nov. 9 Graphs
to 2. Introduction to Linear
Nov. 29 Programming (LP)
3. Graphical Solution
Week Mathematics of Graphs and
12-14 Networks

Dec. 1 1. Basic Concepts in Graphs and

to Networks
Dec. 20 2. Eulerian Circuits and Hamiltonian
Paths
COURSE GRADING SYSTEM

The final grade will be based on the weighted average of the student’s scores on each test assigned at
the end of each lesson. The final SIS grade equivalent will be based on the following table according to
the approved University Student Handbook.

Final Grade = ( Weighted Average of all the Assigned Tests / 2 ) + 50%

Percentage/Equivalent Description
1.00 97.00 - 100 Excellent
1.25 94.00-96.99 Excellent
1.50 91.00-93.99 Very Good
1.75 88.00-90.99 Very Good
2.00 85.00-87.99 Good
2.25 82.00-84.99 Good
2.50 79.00-81.99 Satisfactory
2.75 77.00-78.99 Satisfactory
3.00 75.00-76.99 Passing
5.00 65.00-74.99 Failure
Inc Incomplete
W Withdrawn
Final grades are rounded off to 2 decimal places.

Reference Materials:

• Smith, Karl J. The Nature of Mathematics. 12ed. Cengage Learning. 2012

• Angel, Abbott, Runde. Survey of Mathematics with Applications. 10ed. Pearson. 2016
• Lippman, David. Mathematics in Society. 2ed. 2017
• Thomas, Christopher. Schaum’s Outline of Mathematics for the Liberal Arts. McGrawHill. 2009

Prepared by: Noted by:

Kenneth James T. Nuguid/ Ian J. Saguindan Edcon B. Baccay

Faculty Members Chairperson
Department of Mathematics and Statistics Department of Mathematics and Statistics

Approved by:

Dr. Lincoln A. Bautista

Dean, College of Science

Dr. Emanuel C. de Guzman

Vice President for Academic Affairs
 Lesson 0 4

6 Mathematics of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.1 Graph Concepts and Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.2 Euler’s Theorems and Fleury’s Algorithms . . . . . . . . . . . . . . . . . . . . . 77
6.3 Hamilton Circuits, Hamilton Paths and the
Traveling-Salesman Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.4 Spanning Trees and Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . 90
6.5 Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Contents

S
DM

DM
1 Mathematics in Our World . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1 Overview: What is mathematics? . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Patterns and Numbers in Nature . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Mathematics for Our World . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Logic and Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Compound Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Problem Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
P

P
3.1 Inductive and Deductive Reasoning . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2 George Polya’s Guidelines for Problem Solving . . . . . . . . . . . . . . . . . . 37
4 Statistics and Data Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
PU

PU
4.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Steps in Statistical Investigation . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3 Sampling and Sampling Techniques . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Sample Size Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.5 Methods of Data Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.6 Levels of Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.7 Presentation of Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.8 Measures of Central Tendency . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.9 Measures of Dispersion or Variability . . . . . . . . . . . . . . . . . . . . . . . 58
5 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.1 Modeling with Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . 64
5.2 Solution Set of Systems of Linear Inequalities in Two Variables . . . . . . . . . 68
5.3 Graphical Solution for a Linear Programming Model . . . . . . . . . . . . . . . 69

All Rights Reserved. 2020 Abdul, Atienza, et. al.

Lesson 1 5 Lesson 1 6

The human mind is programmed to make sense of data or to bring order where there is disorder. It seeks
Lesson 1: Mathematics in Our World
to discover relationships and connections between seemingly unrelated bits of information. In doing so,
it sees patterns.
Learning Outcomes
At the end of the lesson, the students are able to:
According to the National Council of Teachers of Mathematics
1. identify patterns in nature in the world; (1991) defines the nature of mathematics as follows: Mathe-
2. articulate the importance of mathematics in one’s life; matics is a study of patterns and relationship, a way of thinking,
an art, a language, and a tool. It is about patterns and rela-
3. argue about the nature of mathematics, what it is how it is expressed, represented and used; tionships. Numbers are just a way to express those patterns

S
and relationships. patterns
4. enumerate and discuss the role of mathematics in various disciplines;

5. express appreciation for mathematics as a human endeavor.

DM

DM
Patterns are everywhere. They are deeply embedded all around
1.1 Overview: What is mathematics? us. You can observe patterns- things like colors, shapes, ac-
tions, line or curves of building, pathways or even in the gro-
Mathematics can be defined in many ways. For some people, Mathematics is just the study of numbers. cery store where boxes of various items are lined up. Number
For others, it is a set of problem-solving tools, a language, a process of thinking, and a study of patterns patterns such as 2,4,6,8 and 5,10,15,20 are among the first
among others. Whatever point of view is taken, there is no denying the reality that mathematics is patterns encountered in younger years.
everywhere. Individuals from around the world use math in their daily lives. Mathematics has various
applications in the world. However, Mathematics is not only concerned with everyday problems, but also
As we advance, we encounter more patterns and discover that number patterns are not restricted to a few
with using imagination, intuition and reasoning to find new ideas and to solve puzzling problems. Math-
types. They could be ascending, descending, multiples of a certain number. We learned patterns through
P

P
ematics is a branch of science, which deals with numbers and their operations. It involves calculation,
the concept of functions and sequences like arithmetic and geometric sequences. Number patterns, logic
computation, solving of problems etc. Its dictionary meaning states that, ‘Mathematics is the science
patterns, geometric patterns and word patterns are examples of the various patterns we learned in school.
of numbers and space’ or ‘Mathematics is the science of measurement, quantity and magnitude.’ It is
However, patterns are not limited to these types. One can observe patterns in nature, art, architecture,
exact, precise, systematic and a logical subject.
PU

PU
human behavior, anywhere. On this section, we will discuss the different patterns in nature, arts and
architecture.
Mathematics helps us to organize and systemize our ideas about patterns; in so doing, not only can we
admire and enjoy these patterns, we can also use them to infer some of the underlying principles that
Patterns in nature are visible regularities of form found in the natural world. These patterns recur in
govern the world of nature.
different contexts and can sometimes be modeled mathematically. Natural patterns include symmetries,
fractals, spirals, meanders, waves, foams, tessellations, cracks, and stripes. Studying patterns allows one
In this lesson, attention will be focused on the nature of mathematics, patterns and numbers in nature
to watch, guess, create, and discover. The present mathematics is considerably more than arithmetic,
and the world and the uses of mathematics.
algebra, and geometry. The method of doing it has advanced from simply performing computations or
derivations into observing patterns, testing guesses, and evaluating results.
1.2 Patterns and Numbers in Nature
What are patterns anyway? We usually think of it as anything that repeats again and again. A pattern is Let us focus on the different types of symmetric patterns, analyze and observe the similarities as well
an arrangement which helps observers anticipate what they might see or what happens next. A pattern as the differences and give examples of these types of patterns as seen in nature, arts, architecture and
also shows what may have come before. A pattern organizes information so that it becomes more useful. mathematics.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 1 7 Lesson 1 8

Symmetry

When we think of patterns, we usually think of it as something that repeats again and again. The math
of symmetry can describe what this repetition may look like and as well as why some objects seem more
orderly and organized than others. That is why we can say symmetry is the fundamental “language” of
patterns.

What is symmetry? Can you give examples of objects that are symmetric? Why do you consider them
symmetric? Is it because of balanced proportions? Or is it because you can rotate, translate or reflect
and they still look the same?

S
DM

DM
Images Exhibiting Bilateral Symmetry

Radial Symmetry

Radial symmetry is rotational symmetry around a fixed point known as the center. Images with more than
one lines of symmetry meeting at a common point exhibits a radial symmetry. An equilateral triangle
Symmetry can be found everywhere. It can be seen from different viewpoints namely; nature, the arts and
and circles are examples. You can cut along three different axes on the equilateral triangle while a circle
P

P
architecture, mathematics; especially geometry and science. Symmetry occurs when there is congruence
can be cut along an infinite number of axes. Consider the photo below. It has rotational symmetry. How
in dimensions, due proportions and arrangement. It provides a sense of harmony and balance. In fact,
many lines of symmetry are possible?
symmetry is one of the foremost predominant themes in arts, design and architecture all over the world
and throughout human history. Mathematical symmetry can also be explained as the passage of time, a
PU

PU
spatial relationship and an aesthetic element found within abstract objects, theoretic models, language,
music and even knowledge itself.

Reflection or Bilateral Symmetry

Bilateral or reflection symmetry is the simplest kind of symmetry. It is one of the most common
kinds of symmetry that we see in the natural world. It can also be called mirror symmetry because an
object with this symmetry looks unchanged if a mirror passes through its middle. In other words, the
objects have a left side and a right side that are mirror images of each other. If a shape can be folded
in half so that one half fits exactly on top of the other, then we say that the shapes are symmetric. The
fold is called a line of symmetry because it divides the shape into two equal parts. Bilateral-symmetric Radial symmetry can be found both in natural and human made objects. The photos below are examples
objects have at least one line or axis of symmetry. The lines of symmetry may be in any direction. of rotational symmetry that can be found in the world around us.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 1 9 Lesson 1 10

horizontal translation. We can usually find these patterns in unique places like on the walls of buildings,
fabrics, borders of rugs and tiled floor.

Mathematicians have already classified all the different types of frieze patterns. It turns out that there
are only seven types.

1. Hop. The frieze pattern only admits a translational symmetry.

S
Did you know that there are other classifications of symmetric patterns. Patterns in the plane are usually
2. Step. The frieze pattern only admits a translational and glide symmetries.
divided into three groups. These are rosette patterns (those that repeat in no direction), frieze patterns
DM

DM
( those that repeat in exactly one direction) and wallpaper patterns (those that repeat in more than
one direction). Let us define, discuss and identify examples of these patterns from nature and the arts.
Included in the discussion is what we call tessellations which completely cover a plane without gaps or
overlaps, like wallpaper patterns.
3. Sidle. The frieze pattern only admits translations and vertical reflections.
Rosette Patterns

Rosette patterns consist of taking motif or an element and rotating and/or reflecting that element.
There are two types of rosette patterns namely cyclic and dihedral. A rosette pattern is cyclic if it
only admits rotational symmetries. On the other hand, a rosette pattern is dihedral if it admits both
4. Spinning Hop. The frieze pattern only admits translations and 180◦ rotations (half-turns).
P

P
rotational symmetries and bilateral or reflectional symmetries. The figures below exhibit rosette patterns.
Can you identify which of them are cyclic? dihedral?
PU

PU
5. Spinning Siddle. The frieze pattern only admits translations, vertical reflections, rotations, and
glide reflections.

Frieze Patterns

A frieze or border pattern is a pattern in which a basic motif repeats itself over and over in one
direction. It extends to the left and right in a way that the pattern can be mapped onto itself by a

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 1 11 Lesson 1 12

6. Jump. The frieze pattern only admits translations, a horizontal reflection, and glide reflection. in the Wolfram Language using Artlandia, illustrated above. There are 17 different wallpaper patterns.

Using intricate techniques, mathematicians were able to classify every wallpaper patterns possible. It is
shown that there are only 17 distinct types of wallpaper patterns.

7. Spinning Jump. The frieze pattern admits translations, vertical reflections, horizontal reflections,
rotations, and glide reflections.

S
Mathematician John B. Conway invented the names of these frieze patterns.
DM Some Wallpaper Patterns

DM
Wallpaper Patterns Tesselations
A wallpaper pattern is a pattern with translation symmetry in two directions. It is, therefore, essentially A tessellation or tiling is a repeating pattern of figures that covers a plane with no gaps or overlaps.
an arrangement of friezes stacked upon one another to fill the entire plane. Any particular wallpaper It is just like a wallpaper group in which patterns are created by repeating a shape to fill the plane.
pattern is made up of a combination of the following symmetries; reflection, rotation and glide reflection.
According to Nocon (2016), in order for a plane figure to be considered a wallpaper pattern, it must Tessellations can be created with translations, rotations, and reflections. Tessellations can be seen in
have at least the basic unit, one copy by translation, and a copy of these two by translation in the second nature, arts and everyday life. Pavements, snake skin, turtle shell and a honeycomb are just few of many
direction. There must be at least two rows, each one of at least two units long. examples of tessellation we see around us. A honeycomb is a perfect example of a natural tessellation.
It uses regular hexagons to form this natural mosaic around the surface area of the hive. Since these are
P

P
regular hexagons, each interior angle of each hexagon are 120 degrees, and all the angles in one of the
hexagons equal 720 degrees.
PU

Beautiful patterns can be created by repeating geometric and artistic motifs according to the symmetry
of the wallpaper groups, as exemplified in works by M. C. Escher and in the patterns created by I. Bakshee
PU
1.3 Fibonacci Sequence
Examples of Tesselations

We start with 1 and another 1. Add them, we get 2. Add 1 and 2, we get 3. Add 2 and 3, we get 5.
Add 3 and 5, we get 8. If we continue repeating the process, we obtain the sequence

1; 1; 2; 3; 5; 8; 13; : : :

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 1 13 Lesson 1 14

which is known as the Fibonacci sequence. The Fibonacci sequence was invented by the Italian
Leonardo Pisano Bigollo (1180-1250), who is known in mathematical history by several names: Leonardo 2
of Pisa (Pisano means “from Pisa”) and Fibonacci (which means “son of Bonacci”). 3
To formally, define the Fibonacci sequence, we start by defining F1 = 1 and F2 = 1. For n > 2, we
1 1
define
Fn := Fn−1 + Fn−2 :
8
The sequence F1 ; F2 ; F3 ; : : : is then the Fibonacci sequence. Such a definition is called a recursive
definition because it starts by defining some initial values and defines the next term as a function of
5
the previous terms.

S
If we take the ratio of Fn to Fn−1 for n ≥ 1,
DM

DM
n Fn Fn =Fn−1 n Fn Fn =Fn−1 Do you see the Fibonacci Numbers? The red curve is known as the Fibonacci Spiral.

1 1 - 8 21 1:61538 : : :
A rectangle whose side ratio (length:width) equals ’ is called a golden rectangle.
2 1 1 9 34 1:61904 : : :
3 2 2 10 55 1:61764 : : :
George Dvorsky (2013) emphasized that the Fibonacci sequence has captivated mathematicians, scien-
4 3 1.5 11 89 1:61818 : : :
tists, artists and designers for centuries. It is a sequence with many interesting properties. Among these
5 5 1:666 : : : 12 144 1:61797 : : :
is its visibility in nature. Most, if not all, natureâĂŹs most beautiful patterns contain Fibonacci numbers.
6 8 1.6 13 233 1:61805 : : :
7 13 1.625 14 377 1:618025 : : :
The Fibonacci numbers appear in nature in various places. These numbers are evident at the flower
P

P
head of a sunflower or daisy. Spirals are also easier to see and to count on pineapples and pine cones.
we see that as n gets larger and larger, the ratio gets closer and closer to a value denoted by ’. The Fibonacci numbers are there on broccoli florets and flowers and on the arrangement of leaves around
number ’ is called as the golden ratio and can be formally defined as stems on many plants too.
PU

PU
Fn
’ := lim : • Pinecones, Speed Heads, Vegetables and Fruits
n−→∞ Fn−1
Spiral patterns curving from left and right can be seen at the array of seeds in the center of a
The symbol lim means ‘the limit as n approaches infinity’ which is usually studied in a calculus course. sunflower. The sum of these spirals when counted will be a Fibonacci number. You will get two
n−→∞
It can be calculated that the exact value of ’ is consecutive Fibonacci numbers if you divide the spirals into those pointed left and right. The
√ seed pods on a pinecone are also arranged in a spiral pattern. Each cone consists of a pair of
1+ 5
’= ≈ 1:6180339887 : : : : spirals, each one spiraling upwards in opposing directions. Spiral patterns can also be deciphered
2
in cauliflower and pineapples. Fibonacci sequence appears on these fruits and vegetables.
√
1− 5
If we denote by ’ := , we can write the nth Fibonacci number explicitly using the formula • Flowers and Branches
2
Most flowers express the Fibonacci sequence if you count the number of petals on these flowers.
’n − ’n
Fn = √ : For example, lilies and irises have three petals, roses and buttercups have five, delphiniums have
5
eight petals and so on. Some plants also exhibit the Fibonacci sequence in their growth points, on
This is known as the Binet Formula. the places where tree branches form or split. A trunk grows until it produces a branch, resulting

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 1 15 Lesson 1 16

in two growth points. The main trunk then produces another branch, resulting in three growth
points and then the trunk and the first branch produce two more growth points, bringing the total
to five as illustrated on the image below.

S
DM

DM
• Honeybees
The family tree of a honey bee perfectly resembles the Fibonacci sequence. A honeybee colony
consists of a queen, a few drones and lots of workers. The following image below shows how the
family tree relates. The Golden Ratio and/or the Golden Spiral can also be observed in music, art, and designs. Appearing
in many architectural structures, the presence of the golden ratio provided a sense of balance and
equilibrium. Let’s take a look at a couple of examples.

• Architecture. The Great Pyramid of Giza: The Great Pyramid of Giza built around 2560 BC is
one of the earliest examples of the use of the golden ratio. The length of each side of the base
P

P
is 756 feet, and the height is 481 feet. So, we can find that the ratio of the vase to height is
756=481 = [Link]
PU

PU
• The Human Body
The human body has many elements that show the Fibonacci numbers and the golden ratio. Most
of your body parts follow the Fibonacci sequence and the proportions and measurements of the
human body can also be divided up in terms of the golden ratio.
The Greek sculptor Phidias sculpted many things including the bands of sculpture that run above
the columns of the Parthenon. Other architectural structures that exhibits the Golden ratio include
• Geography, Weather and Galaxies Fibonacci numbers and the relationships between these
the ff: Porch of Maidens, Acropolis, Athens; Chartres Cathedral; and Le Corbussier. Can you name
numbers are evident in spiral galaxies, sea wave curves and in the patterns of stream and drainages.
other structures that has the Golden Ratio?
Weather patterns, such as hurricanes and whirlpools sometimes closely resemble the Golden Spiral.
The milky way galaxy and some other galaxies have spiral patterns. Planets of our solar system • Arts. Mona-Lisa by Leonardo Da Vinci: It is believed that Leonardo, as a mathematician tried
and their orbital periods are closely related to the golden ratio. to incorporate of mathematics into art. This painting seems to be made purposefully line up with

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 1 17 Lesson 1 18

golden rectangle.

An Old man by Leonardo Da Vinci: Leonardo Da Vinci explored

the human body involving in the ratios of the lengths of various
body parts. He called this ratio the "divine proportion" and
featured it in many of his paintings. We also have the The
Vetruvian Man (“The Man in Action”) by Leonardo Da Vinci;
Holy Family by Micahelangelo; Crucifixion by Raphael; The
sacrament of the Last Supper by Salvador Dali (1904-1989),
and many more.

S
1.4 Mathematics for Our World DM

DM
Mathematics is everywhere; whether it is on land, sea or air, online or on the front line, mathematics
underpins every nook and cranny of modern life. Far from a quaint subject to be forgotten upon leaving
school, it is the glue that holds our world.
Mathematics helps organize patterns and regularities in the World
Roger Bacon (1214-1294), an English Franciscan friar, philosopher, scientist and scholar of the 13th
century, once stated: “Neglect of mathematics works injury to all knowledge, since he who is ignorant According to Ian Stewart (1995), we live in a universe of patterns. Human mind and culture have de-
of it cannot know the other sciences or the things of the world.” veloped a formal system of thought for recognizing, classifying and understanding patterns. This formal
system of thought is what we know now as mathematics. We use mathematics to organize and system-
Math helps us understand or make sense of the world - and we use the world to understand math. It is atize our thoughts and ideas about patterns and other regularities in this world. The development of
P

P
therefore important that we learn math contents needed to solve complex problems in a complex world; these new mathematical theories helped paved the way to the thorough understanding of the different
learn the mathematical knowledge and skills we need to understand the world and make contributions patterns in nature. Stewart (1995) also mentioned that our newfound understanding of natural order and
to the global community. nature’s secret regularities is being used to steer artificial satellites to new destinations with far less fuel
PU

PU
than anybody had thought possible, to help avoid wear on the wheels of locomotives and other rolling
stock, to improve the effectiveness of heart pacemakers, to manage forests and fisheries, even to make
more efficient dishwashers. But most important of all, it is giving us a deeper vision of the universe in
Applications of Mathematics in Our World
which we live, and of our own place in it. Yes, mathematics has indeed helped organize patterns and
Mathematics has so many uses of applications. consistencies in the world.

• Mathematics helps organize patterns and regularities in the world; Mathematics helps predict the behavior of nature and many phenomena.

• Mathematics helps predict the behavior of nature and many phenomena; Mathematics is used to explain why the Sun set, where it went and why it returned because it was easier
to count these events in numbers than to put them into words. Based on historical patterns, we can make
• Mathematics helps control nature and occurrences in the world for our own good; forecasts or predictions to help us prepare for our daily [Link] and other mathematical meth-
ods became a way of using numbers to show how things in nature happen, where and when it will happen.
• Mathematics has applications in many human endeavors.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 1 19 Lesson 1 20

Earth scientists have relied in the past on statistical methods to forecast natural hazard events. However, a biological or chemical laboratory and the like. Indeed, its application and use are uncountable and the
Benoit Mandelbrot, a professor of mathematical sciences at Yale University described how he has been list of uses it offers is unending.
using fractals to find order within complex systems in nature, such as the natural shape of a coastline.
As a result of his research, earth scientists are taking Mandelbrot’s fractal approach one step further and As it is valuable and integral in the life of man, mathematics as a discipline that Introduces students
are measuring past events and making probability forecasts about the size, location, and timing of future with the wide array of possibilities from honing problem-solving skills to enriching aesthetic judgment.
natural disasters.
Mathematics helps control nature and occurrences in the world for our own good.

Mathematical modelling and control theory can be used. By mathematical modeling we see the inputs
to events and their most likely outcomes. Knowing these inputs and seeing their consequences and

S
establishing their relationship defined quantitatively, we can prepare for calamities or natural disasters,
or better yet, we can probably stop them from happening.
DM

DM
Control theory is defined as a field of applied mathematics that is relevant to the control of certain phys-
ical processes and systems. As long as human culture has existed, control has meant some kind of power
over the environment and control theory may be viewed as the science of modifying that environment,
in the physical, biological, or even social sense. Control theory played a major role in many technological
advances in the second half of the 20th century.

Mathematics has applications in many human endeavors making it indispensable.

Mathematics existed since the beginning of time, written or unwritten. Its unwritten history is carved in
P

P
all things found in cosmos , found in the patterns created in nature, appreciated in the juxtaposition of
the heavens and the earth, contrast between darkness and light , made sense in the harmony created not
just by a well-known orchestra but even by the rain drops falling on offshore wind-turbines. Its language,
PU

PU
though considered by many as abstract is in fact easy to grasp when the logic and formula that govern it
are understood by the inquisitive minds of students, bakers, chemists , carpenters and appreciated by the
receptive hearts of the musicians - drummers, guitarists, pianists and composers; dance choreographers,
gymnasts and marathon runners.

Mathematics permeates every area of man’s life , leaving every man convinced of its value. As a tool,
mathematics is indispensable. It is needed by all people in honing their logical thinking and reasoning,
in making wise financial decisions - in budgeting or making both ends meet when financial resources are
scarce. It is needed in choosing the best interior and outdoor designs of houses , offices and business
sites. It is useful in determining traveling time and calculating the amount of fuel needed to get to the
destination. It is not just needed in the classrooms but also at home when doing the mundane baking
or preparing foods for breakfast , dinner or lunch; calculating steps when performing simple to complex
acrobatic stance; determining speed in a short distance or marathon run, preparing chemical solutions in

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 2 21 Lesson 2 22

Assessment Lesson 2: Logic and Sets

Learning Outcomes
I. Patterns and Numbers in Nature
At the end of the lesson, the students are able to

(1) Give five examples each of nature having reflection symmetry and radial symmetry. 1. identify which are propositions and which are not;

(2) Compare and contrast (a) rotation and reflection; (b) translation and rotation. 2. construct compound propositions using logical connectives;

(3) Which upper case letters of the English alphabet look the same after being rotated 90 ? ◦
3. construct truth tables for propositions;
180◦ ?

S
4. test validity of arguments
(4) Classify the following frieze patterns based on Conway’s classification.
DM

DM
2.1 Propositions
Mathematics is a language. As in any other types of language, we use sentences to communicate thoughts
(c)
(a) and ideas. Mathematics is not an exception. We use propositions to communicate mathematical ideas
precisely.

(d) Definition 1
A proposition is a declarative sentence that can be objectively identified as either true or false,
but not both. If a proposition is true, then its truth value is true and is denoted by T or 1;
(b) (e) otherwise, its truth value is false and is denoted by F or 0.
P

P
II. Fibonacci Sequence Example 1. Consider the following sentences.
PU

PU
(1) Douglas MacArthur arrived in the Philippines in 1521. (5) Is that your laptop?
(1) Enumerate the first twenty Fibonacci numbers.
(2) Are you insane? (6) Basketball players are handsome.
(2) Use F40 = 63; 245; 986 and F38 = 39; 088; 169 to find the value of F39 . Show your reasoning. √
(3) 2 is an irrational number. (7) There is life in other planets.
(3) Using the Binet’s formula, calculate F4 .
(4) Find all x such that xe −x
= 2. (8) Welcome to the Philippines!

III. Beyond the Walls (Performance Task) Immediately, we find that sentences (2), (4), (5), and (8) are not declarative sentences, so they are not
Look for patterns Inside or outside of your house then take pictures of the patterns explored using propositions.
smart phones or digital camera. Explore, take photos, make list and identify what patterns can be
seen in nature inside your house, at the garden or park nearby or any part of the neighborhood. Sentence (1) is a proposition because Douglas MacArthur either arrived in the Philippines in 1521 or
Showcase your drawing skills by creating original paintings or pictures, poster, photo collage or vlogs not. In fact, this proposition is false because historical records shows that Douglas MacArthur arrived in
of the different patterns in nature, Fibonacci, golden ratio or the like that you have encountered the Philippines some time in 1900s.
on your walk.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 2 23 Lesson 2 24

Sentence (3) is clearly a true proposition. Although statement (6) is a declarative sentence, it cannot Definition 3
be considered a proposition because the meaning of the word “handsome” is subjective in nature. Unless Let p and q be given propositions. The conjunction of p and q is the proposition “p and q”,
we could agree on an objective definition of “handsome”, then statement (6) cannot be considered a denoted by p ∧ q, which is true only when both p and q are true.
proposition.
In other words, if one of p or q is false, then p ∧ q is false. We summarize this idea using the following
Finally, statement (7) is a proposition. Whether there is life or not in other planets, it doesn’t really table.
matter. The fact that this sentence is either true or false, and cannot be both true and false, makes it a
p q p∧q
proposition. For this example, we still don’t have enough evidence to claim that proposition (7) is true
yet, and we don’t have a proof that it is false either. Hence, only time will tell when can we assign a 1 1 1
truth value for (7), but certainly, it has a truth value. 1 0 0

S
0 1 0
Symbolically, we denote propositions in this lesson using lower case letters, such as p; q; r; s; etc. 0 0 0
DM

DM
Definition 2 Such a table is called a truth table for p ∧q. The truth table above illustrates the different combinations
of truth values for p and q and the corresponding truth value for the conjunction.
The negation of a proposition p is the proposition which is false when p is true; and true when
p is false. The negation of p is denoted by ¬ p. Example 3. Given the propositions

In the English language, we can simply state the negation of a proposition p by saying “It is not the case p : 3 is odd.
that p.” However, there are many ways to express negations of statements grammatically by replacing q : Elephants are mammals.
“is/are” by “is not/are not”, etc. r : Philippines is a first world country.

Example 2. Given the statements We know that p and q are true and r is false. Therefore,
P

P
p : Everyone in Visayas speaks Cebuano.
p ∧ q : 3 is odd and elephants are mammals.
q : Today is Wednesday.
is true, while
PU

PU
The corresponding negations are
p ∧ r : 3 is odd and Philippines is a first world country.

¬ p : Not everyone in Visayas speaks Cebuano. is false. For a more complicated example, the proposition
¬ q : Today is not Wednesday.
(¬ p) ∧ (¬ q) : Neither 3 is odd nor Philippines is a first world country.

is still false, since ¬ p is false.

2.2 Compound Propositions

Definition 4
A simple proposition is a proposition with only one subject and only one predicate. For example, the Let p and q be given propositions. The disjunction of p and q is the proposition “p or q”,
proposition “Every cat that barks has a PhD.” is a simple proposition. The subject of this proposition denoted by p ∨ q, which is false only when both p and q are false.
is “every cat that barks” and the predicate is “has a PhD.” In logic, we can combine simple propositions
to form compound propositions using logical connectives. Some of the most common connectives In other words, if one of p or q is true (or both), then p ∨ q is true. The truth table for p ∨ q is given
are “or”, “and”, “but”, “unless”, etc. below.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 2 25 Lesson 2 26

p q p∨q The following is the truth table for p −→ q.

1 1 1
p q p −→ q
1 0 1
0 1 1 1 1 1
0 0 0 1 0 0
0 1 1
Example 4. Consider the statements p, q and r in the preceding example. The statement
0 0 1

p ∨ q : Either 3 is odd or elephants are mammals. In the proposition p −→ q, the proposition p is also called as the premise and q is called as the
conclusion. From the truth table, we can see that a conditional statement is trivially true when the

S
is true. Also,
premise is false.
p ∨ r : Either 3 is odd or Philippines is a first world country:

DM Example 7. Suppose that your mother exclaims “If you don’t wash the dishes, then you don’t get

DM
money for a buffet.” In this conditional statement, the premise is “You don’t wash the dishes.” and the
Example 5. The proposition “Either 3 is odd or there is life in other planets.” is technically true since conclusion is “you don’t get money for a buffet.” This statement can only false only when you don’t
the component “3 is odd.” is a true proposition. Whether the proposition “There is life in other planets.” wash the dishes but you still get money for the buffet.
is true or false, the disjunction is always true.
Note that there are many ways to say p −→ q aside from “If p, then q.” Alternatively, we can say “q if
Example 6. Construct a truth table for the compound statement p ∨ (q ∧ (¬ r )).
p” or “p implies q”, “p is sufficient for q” or “q is necessary for p.”

Solution. Since each of p, q, and r may assume two distinct truth values, then there are a total of
Example 8. Given the statements p : “ı is irrational.” and q : “3 is less than 2.”, then
2 · 2 · 2 = 8 combinations, hence the truth table must contain eight rows as shown below.
p −→ q : If ı is irrational, then 3 is less than 2.
p q r ¬ r q ∧ (¬ r ) p ∨ (q ∧ (¬r ))
P

P
1 1 1 0 0 1 the converse of this conditional is
1 1 0 1 1 1
1 0 1 0 0 1 q −→ p : If 3 is less than 2, then ı is irrational.
PU

PU
1 0 0 1 0 1
0 1 1 0 0 0 the inverse is
0 1 0 1 1 1 (¬ p) −→ (¬ q) : If ı is not irrational, then 3 is not less than 2.

0 0 1 0 0 0 and the contrapositive is

0 0 0 1 0 0
(¬ q) −→ (¬ p) : If 3 is not less than 2, then ı is not irrational.

Definition 5 If we assume that p is true and q is false (just like how they really are in mathematics), one verifies that
Let p and q be propositions. The conditional statement p −→ q is the proposition “If p, then both p −→ q and (¬ q) −→ (¬ p) are false, while both q −→ p and (¬ p) −→ (¬ q) are true.
q.” is the proposition which is false only when p is true and q is false. The converse, inverse,
We like to emphasize that we write the negation of “ı is irrational” as “ı is not irrational” to emphasize
and contrapositive of p −→ q are the conditional statements q −→ p, (¬ p) −→ (¬ q), and
the fact that we actually don’t assume that the opposite of being irrational is being rational, unless
(¬ q) −→ (¬ p), respectively.
otherwise stated.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 2 27 Lesson 2 28

Definition 6 In logic, the implication p =⇒ (p∨q) is called as the law of addition and the implication (p∧q) =⇒ p
Let p and q be propositions. The biconditional statement p ↔ q to be read as “p if and only is the law of simplification.
if q” is the proposition which is true only if both p and q are true or both p and q are false.
The following are some of the most common equivalences in logic.

p q p↔q Theorem 1
1 1 1 Let p; q; and r be propositions.
1 0 0
0 1 0 1. p ⇐⇒ q if and only if p ←→ q is a tautology.
0 0 1
2. p ⇐⇒ p.

S
Definition 7 3. p ∨ q ⇐⇒ q ∨ p and p ∧ q ⇐⇒ q ∧ p. (commutative properties)
A compound proposition is a tautology if its truth value remains true regardless of the truth values
DM

DM
4. p ∨ (q ∨ r ) ⇐⇒ (p ∨ q) ∨ r and p ∧ (q ∧ r ) ⇐⇒ (p ∧ q) ∧ r . (associative properties)
of its component propositions. On the other hand, a compound proposition is a contradiction if
its truth value remains false regardless of the truth values of its component propositions. 5. p ∨ (q ∧ r ) ⇐⇒ (p ∨ q) ∧ (p ∨ r ) and p ∧ (q ∨ r ) ⇐⇒ (p ∧ q) ∨ (p ∧ r ). (distributive
properties)

Example 9. The compound statement p ∨ (¬ p) is a tautology and the compound statement p ∧ (¬ p) 6. De Morgan’s Laws
is a contradiction. This can be observed by looking at the truth table below.
(a) ¬(p ∨ q) ⇐⇒ (¬ p) ∧ (¬ q).
p ¬ p p ∨ (¬ p) p ∧ (¬ p)
(b) ¬(p ∧ q) ⇐⇒ (¬ p) ∨ (¬ q)
1 0 1 0
0 1 1 0 7. p −→ q ⇐⇒ (¬ p) ∨ q.
P

P
8. ¬(p −→ q) ⇐⇒ p ∧ (¬ q).
Definition 8
9. p −→ q ⇐⇒ (¬ q) −→ (¬ p).
Let p and q be propositions (possibly compound). We say that p logically implies q, expressed
PU

PU
as p =⇒ q, if the conditional statement p −→ q is a tautology. If p =⇒ q and q =⇒ p, we 10. p ←→ q ⇐⇒ (p −→ q) ∧ (q −→ p):
say that p and q are logically equivalent and we write p ⇐⇒ q. A compound proposition that
is neither a tautology nor a contradiction is called a contingency.
2.3 Sets
Example 10. By constructing truth tables, show that p =⇒ p ∨ q and p ∧ q =⇒ p. One of the basic concepts every student of mathematics must know is that of sets.
Definition 9
Solution.
A set is a well-defined collection of objects called elements.
p q p ∨ q p ∧ q p −→ (p ∨ q) (p ∧ q) −→ p
1 1 1 1 1 1 A collection is well-defined if for any given object we can objectively decide whether it is or is not in the
1 0 1 0 1 1 collection. Any object which belongs to a given set is said to be an element of or a member of the
0 1 1 0 1 1 given set.
0 0 0 0 1 1

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 2 29 Lesson 2 30

Example 11. A set A is said to be finite if it is possible to list down all the elements of A in a list. Otherwise, A is
said to be infinite. If A is finite, the cardinality of A is the number of elements of A, which is denoted
1. The collection of all letters in the English Alphabet is a set.
by n(A).
2. The collection of all handsome guys is not a set, because one cannot objectively identify if a given
Example 15. The set of all letters in the English Alphabet is finite and its cardinality is 26, because
guy is handsome or not, because the word “handsome” is subjective in nature.
there are 26 distinct letters in the English alphabet. On the other hand, the set of all even integers in
infinite.

Upper case letters are usually used to name sets. A set A can be commonly described in three ways, Definition 10
by (a) listing (roster) method, (b) by set-builder notation or(c) by descriptive method. The listing Let A and B be sets. We say that A is a subset of B and write A ⊆ B if every element of A is

S
method describes the set by listing all the elements between braces and separated by commas (note: an element of B. We say that A and B are equal and write A = B if A ⊆ B and B ⊆ A.
in enumerating the elements of a certain set, each element is listed only once and the arrangement of
elements in the list is immaterial). The set-builder notation uses a variable (a symbol, usually a letter, Remarks.
DM

DM
that can represent different elements of a set), braces, and a vertical bar | that is read as "such that".
1. For any set A, A ⊆ A and ? ⊆ A.
This is usually used when the elements are too many to list down. The descriptive method uses a
short verbal statement to describe the set. 2. If A and B are finite sets and A = B, then n(A) = n(B).

Example 12. Using the roster method, the set of months in a year that ends with letter ‘y’ can be Example 16. Let A be the set of all mathematicians 20 feet high and B be the set of all PUP students.
represented by {January, February, May, July}. Then A = ?. By Remark (1) above, A ⊆ B: Therefore, we can conclude that every mathematician 20
feet high is a PUP student.
Example 13. The set {2; 3; 4; 5; 6; 7; 8; 9} in set-builder notation is
Two finite sets A and B are said to be equivalent if and only if n(A) = n(B). Note that equal sets are
{x | x is an integer greater than 1 but less than 10}:
necessarily equivalent bu equivalent sets need not be equal.
P

P
Example 17. Let A = {x | x is a prime number less than 20} and B = {1; 2; 3; 4; 5; 6; 7; 8} are equiv-
alent since n(A) = 8 = n(B), however, A 6= B.
If a is an element of a set A, we write a ∈ A. Otherwise, we write a ∈
= A. There are sets with no
elements. Such a set is said to be empty and we use the symbol ? to denote the empty set. A set
PU

PU
Definition 11
with only one element is called a unit set or a singleton.
Let A and B be sets. The union of A and B is defined as

Example 14. The set of integers between 1 and 2 is empty, while the set of even prime numbers is a A ∪ B = {x | x ∈ A or x ∈ B}:
singleton.
The intersection of A and B is
For future discussion, we will use the following notations:
A ∩ B = {x | x ∈ A and x ∈ B}:
• N for the set of natural or counting numbers (positive integers): {1; 2; 3; 4; :::}
Then relative complement of B in A is the set
• Z for the set of integers: {::: − 4; −3; −2; −1; 0; 1; 2; 3; :::}
a
 ff
• Q for the set of rational numbers: | a; b ∈ Z; b 6= 0 A \ B := {x ∈ A | x ∈
= B}:
b
• R for the set of real numbers We could represent A ∪ B, A ∩ B, and A \ B in terms of Venn Diagrams as shown below.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 2 31 Lesson 2 32

Example 18. Let A = {0; 1; 3; 5; 7} and B = {1; 2; 4; 7; 9}. Then A ∪ B = {0; 1; 2; 3; 4; 5; 7; 9},

S
A ∩ B = {1; 7} and A \ B = {0; 3; 5}.

Since n(E ∩ S ∩ M) = 0, then the number of students who only joined the Mathematics Club is
DM

DM
In most of the interesting instances in mathematics, we normally talk about a particular set of objects n(M) − n(E ∩ M) − n(S ∩ M) = 37 − (7 + 9) = 21:
at a given time. The set of all objects of interest is called as the universal set, generically denoted as
U . If A ⊂ U , the complement of A is defined as the set

A0 = U \ A = {x ∈ U ∈ x ∈
= A}:

Using the De Morgan’s Law of logic, one can readily verify that

(A ∪ B)0 = A0 ∩ B 0 and (A ∩ B)0 = A0 ∪ B 0 :

P

P
We can use our knowledge of sets to solve some word problems.
PU

PU
Example 19. At a certain high school, each student is a member of the English Club, the Science
Club, or the Mathematics Club. Of the 79 students asked, 33 are members of the English Club, 37 are
members of the Math Club, and 37 are members of the of the Science club. Furthermore, 7 are members
of both the English and the Math Clubs, 12 are members of both the English and the Science Clubs,
and 9 are members of the Science and Math Clubs. No high school student is a member of all the three
clubs. How many joined only the Math Club?

Solution Let E, S, and M denote the sets of members of English, Science, and Mathematics Club,
respectively. As given in the problem, the universal set U has cardinality n(U ) = 79, n(E) = 33,
n(M) = 37, and n(S) = 37. Furthermore, n(E ∩ M) = 7, n(E ∩ S) = 12, and n(S ∩ M) = 9. The last
condition imply that E ∩ S ∩ M = ?. This situation can be represented by the following Venn diagram.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 2 33 Lesson 3 34

Assessment Lesson 3: Problem Solving

1. Write each statement in words. Let p: The plane is on time. Let q: The sky is clear.
Learning Outcomes
(a) p ∧ (¬ q) At the end of the lesson, the students are able to
(b) q → (p ∨ ¬p)
1. differentiate between inductive and deductive reasoning;
(c) p ↔ q
2. utilize inductive reasoning to form conjectures;
2. Construct a truth table for each proposition.
3. use deductive reasoning to prove a conjecture;
(a) [(p ∧ q) ∨ r ] ↔ [(p ∧ r ) ∨ (q ∧ r )]

S
4. state the Polya’s four steps in problem solving;
(b) [(p ∧ r ) → (q ∧ ¬r )] → [(p ∧ q) ∨ r )]
5. solve mathematical problems using the Polya’s four steps.
3. Prove the De Morgan’s Laws by constructing truth tables.
DM

DM
4. Let U := Letters in the English Alphabet = {a, b, c, . . . ,x, y, z}
A = {t, r, i, a, n, g, l, e, s} 3.1 Inductive and Deductive Reasoning
B = {s, q, u, a, r, e };
Human beings are said to be rational creatures because we use reasoning to come up with sound decisions
C = {h, e, x, a, g, o, n, s }
that we have to make everyday. Reasoning is our ability to use logical thinking to come up with a
Determine the following: decision. There are two major types of reasoning: inductive and deductive. We first talk about inductive
reasoning.
(a) A ∪ (B ∩ C)
(b) (A ∪ B)0 ∩ C Definition 12
P

P
(c) (A ∩ C) ∪ (B ∩ C) Inductive Reasoning is the process of reasoning that arrives at a general conclusion based on
(d) A ∩ (C ∩ U )0 the observation of specific examples.

(e) n[(A ∪ B) ∩ (B ∪ C)]

Normally, we use inductive reasoning when we need to come up with a general conclusion, known as
PU

PU
5. A survey of 90 customers was taken at Barnes & Noble regarding the types of books purchased. a conjecture, by observing certain events or examples. Generally speaking, our conjectures could be
The survey found that 44 purchased mysteries, 33 purchased science fiction, 29 purchased romance wrong. Examples which can negate our conjectures are called counterexamples.
novels, 13 purchased mysteries and science fiction, 5 purchased science fiction and romance novels,
Example 20. In the past 30 days, we observed that the sun has risen in the east. Using inductive
11 purchased mysteries and romance novels, and 2 purchased all three types of books (mysteries,
reasoning, we may conjecture that the sun will rise in the east tomorrow.
science fiction, romance novels). How many of the customers surveyed purchased
Example 21. Consider the odd numbers 3; 5; 7; and 9. If we take their squares, we see that 32 = 9,
(a) mysteries only?
52 = 25, 72 = 49 and 92 = 81. We can observe that the squares of the given odd numbers are all odd
(b) mysteries and science fiction, but not romance novels? as well. Using inductive reasoning, we may conjecture that the square of an odd integer is also odd.
(c) mysteries or science fiction?
(d) romance novels or mysteries, but not science fiction? Testing Conjectures
(e) exactly two types (mysteries, science fiction, romance novels)? Logically speaking, we cannot prove a general statement from a number of specific examples unless there
are only finitely many examples and we can exhaust them. However, only one counter example can prove

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 3 35 Lesson 3 36

that our conjecture is false. Definition 13

Deductive reasoning is the process of reasoning that arrives at a conclusion based on previously
Example 22. Let n be a positive integer. Select n distinct points at random in the circumference of a
accepted general statements.
circle and connect every pair of points in this collection by a chord. Make a conjecture about the number
of regions in the interior of the circle made by the chords and test your conjecture.
Deductive reasoning does not rely on examples. We make our conclusion based on general statements
whose truth value is known or assumed. Formal mathematics is usually based on this type of reasoning.
For n = 1; 2; 3; 4; 5, we draw actual circles and count the number of regions made by the chords obtained
We first lay down definition of terms, and assume basic true statements called axioms and derive true
by connecting every pair of points.
statements from these axioms called as theorems.

Example 23. The following are examples of deductive reasoning.

S
1. Starfish are invertebrates. Patrick is a starfish. Therefore, Patrick is invertebrate.
√ √
2. Every rational number is a real number. The number −1 is not real. Therefore, −1 is not
DM

DM
rational.

We summarize the number of regions in the following table. Inductive reasoning cannot in general prove general statements as this relies on examples only. In contrast,
we can use deductive reasoning to prove a certain conjecture.
n 1 2 3 4 5
no. of regions 1 2 4 8 16 Example 24. Choose any number. Multiply by 3. Add 6 to the result. Divide the result by 3. Finally,
subtract the original number from the result of the previous step. Use inductive reasoning to make a
If we observe the pattern on the number of regions, they seem to be powers of 2. In fact, for
conjecture about the final result and use deductive reasoning to prove the conjecture.
n = 1; 2; 3; 4; 5, the number of regions in the circle is 2n−1 . It is therefore reasonable for use to
give the following conjecture.
Solution. We first consider few examples.
P

P
Conjecture. The number of regions in the interior of the circle made by connecting every pair of points test number 9 15 28
in a set of n points in the circumference is 2n−1 . multiply by 3: 27 45 84
PU

PU
add 6: 33 51 90
The best way to test the conjecture is to check the example for the next larger n, which is n = 6. divide by 3: 11 17 30
Constructing the circle for n = 6 and counting the regions, subtract the orig. no. 2 2 2

We see that based from the three test numbers, the final results are the same and are all equal to 2.
There is a reason to conjecture that the final result will always be 2 regardless on where we start. To
prove this claim, take an arbitrary number x.
multiply by 3: 3x
add 6: 3x + 6
3x + 6
divide by 3: =x +2
3
subtract the orig. no: (x + 2) − x = 2.
we see that the number of regions is 31 and not 26−1 . This counterexample disproves our conjecture.
Therefore, as claimed, it is now proven that we will always end up with 2.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 3 37 Lesson 3 38

3.2 George Polya’s Guidelines for Problem Solving

In 1945, mathematician George Pólya devised a model for problem solving and published it in his book
How to Solve It. The book contains a collection of mathematical problems and selected strategies on
dealing these. His problem solving model, which he called heuristic (or serving to discover), is as follows.

POLYA’S FOUR STEPS:

A group of 3 persons makes 3 handshakes, a group of 4 persons makes 6 handsakes and a
1. Understand the problem. Ask questions, experiment, or otherwise rephrase the question in
group of 5 persons makes 10 handshakes. Now, for each case with k persons, each of these
your own words.
persons has to have a handshake with the other k − 1 persons. So, the product k(k − 1) is

S
2. Devise a plan. Find the connection between the data and the unknown. Look for patterns, relate the number of all handshakes from individual perspective. Note that if A shakes hands with B,
to a previously solved problem or a known formula, or simplify the given information to give you then B shakes hands with A as well. Thus, only half of k(k − 1) represents the total number of
an easier problem. k(k − 1)
DM handshakes. Hence, a pattern is generalized by will lead to the number of handshakes

DM
2
3. Carry out the plan. Check the steps as you go. that took place in a group of k persons. Therefore, there were a total of

4. Look back. Examine the solution obtained. In other words, check your answer.
k(k − 1) 30(30 − 1)
= = 435 handshakes.
Together with these guidelines, the following are some of his recommended strategies: 2 2

1. Draw a diagram. 5. Guess and check.

Step 4. Look back. Every person will be shaking hands with 29 other. Thus, 870 handshakes are
2. Solve a simpler problem. 6. Find a pattern. noted for individual perperspective. Half of which is 435.

3. Make a table. 7. Use a formula or an equation.

P

P
4. Work backwards. 8. Using logical reasoning.
Example 26. Andrew has some magic cards to trade. Ian has 2 more than 2 times the number of magic
Example 25. In a seminar, 30 attendees were present. During their meet-and-greet activity, they were cards Andrew has. Patrick has 2 less than Ian. Ken has 4 less than 2 times the number of magic cards
PU

PU
asked to have a handshake with everyone in the room. If each one did handshake with everyone, how Patrick has. Patrick has 8 magic cards. How many magic cards does Andrew have to trade?
may handshakes took place?
Solution.
Solution.

Step 1. Understand the Problem. There were 30 attendees present. A simple handshake means Step 1. Understand the Problem. The number of magic cards Ian has depends on the number of
letting a distinct pair be recognized. Moreover, if A shakes hands with B, then B shakes hands magic cards Andrew has. The number of magic cards Patrick has depends on the number of
with A as well. magic cards Ian has. The number of magic cards Ken has depends on the number of magic
cards Patrick has. It is clear that 8 cards are in Patrick’s possession.
Step 2. Devise a plan. We start with solving simpler cases, say 3, 4 and 5 persons. We can draw
a diagram where a person is represented by nodes while handshakes by arcs connecting the
Step 2. Devise a plan. We can settle this by working backwards starting from the number of magic
nodes. From here, we try to find a pattern.
cards Patrick has. Making a table may aid organization.
Step 3. Carry out the plan. The following figures represent the handshakes that took place among
3, 4 and 5 persons. Step 3. Carry out the plan.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 3 39 Lesson 3 40

Statements of Hints Arithmetic Sense Remarks Assessment

Patrick has 8 magic cards. 8 This is the last event.
Ken has 4 less than 2 times Operation is not 1. Explain why you can never be sure that a conclusion you arrived at using inductive reasoning is
the number of magic cards (2 × 8) − 4 = 12 yet revered. true.
Patrick has. Ken has 12 cards.
2. Select any two-digit number. Multiply it by 9. Then add the digits. Keep adding the digits in
Patrick has 2 less Operation is reversed.
the answer until you get a single-digit answer. Using inductive reasoning, what can you conjecture
less than Ian. 8 + 2 = 10 Ian has 10 cards.
about any whole number multiplied by 9? Use deductive reasoning to prove that your conjecture
Ian has 2 more than Operation is reversed.
is true.
2 times the number of (10 − 2)=2 = 4 Andrew has 4 cards.
magic cards Andrew has. 3. Use Polya’s Four Steps to solve the following problems.

S
Step 4. Look back. If Andrew has 4 magic cards, then Ian has 2 more than twice of 4 or 10 magic (a) Susie’s age this year is a multiple of 5. Next year, her age is a multiple of 7. What is her
cards. If Ian has 10 magic cards, then Patrick has 10 - 2 = 8 magic cards. Lastly, if Ken has
DM present age?

DM
4 less than twice of 8 of 12 magic cards. (b) Consider a square whose side is 1 unit. If the measure of its side is doubled, what will be its
new area as compare to the smaller square? How about if the side of the smaller square was
tripled, what will be its new area?
(c) How many perfect squares are there between 1,000,000 and 9,000,000?
(d) Determine the number of different triangles that can be drawn given eight noncollinear points?
(e) There are 25 students asked by their literature instructor regarding with the type of literary
works they prefer to read. He found out that 10 prefer to read novels, 11 prefer to read short
stories, 15 prefer to read poems, 5 for both novels and short stories, 4 both short stories and
P

P
poems, 7 for both novels and poems, and 3 prefer all. How many students prefer none of the
given types of literary works?
PU

PU
All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 4 41 Lesson 4 42

Functions of Statistics
Lesson 4: Statistics and Data Management
1. Condensation. Generally speaking by the verb ‘to condense’, we mean to reduce or to lessen.
Learning Outcomes Condensation is mainly applied at embracing the understanding of a huge mass of data by providing
At the end of the lesson, the students are able to only few observations.

1. demonstrate the ability to apply fundamental concepts in exploratory data analysis; 2. Comparison. Classification and tabulation are the two methods that are used to condense the
data. They help us to compare data collected from different sources. Grand totals, measures
2. define the field of Statistics in terms of its definition and application;
of central tendency measures of dispersion, graphs and diagrams, coefficient of correlation, etc.
3. enumerate the procedures involved in collecting data; provide ample scope for comparison. As statistics is an aggregate of facts and figures, comparison

S
is always possible and in fact comparison helps us to understand the data in a better way.
4. distinguish between the nominal, ordinal, interval and ratio methods of data measurement;
3. Forecasting. By the word forecasting, we mean to predict or to estimate beforehand. Given the
5. recognize the various ways to present data;
DM

DM
data of the last ten years connected to the number of students enrolled in PUP, it is possible to
6. identify the features that describe a data distribution. predict or forecast the number of students that will enroll for the near future. In business also
forecasting plays a dominant role in connection with production, sales, profits etc. The analysis of
Statistics is the study of the collection, organization, analysis, interpretation, and presentation of data. time series and regression analysis plays an important role in forecasting.
It deals with all aspects of data, including the planning of its collection in terms of the design of
surveys and experiments. Some consider statistics a mathematical body of science that pertains to the 4. Estimation. One of the main objectives of statistics is drawn inference about a population from
collection, analysis, interpretation or explanation, and presentation of data, while others consider it a the analysis for the sample drawn from that population.
branch of mathematics concerned with collecting and interpreting data. Because of its empirical roots
and its focus on applications, statistics is usually considered a distinct mathematical science rather than 5. Tests of Hypothesis. A statistical hypothesis is some statement about the probability distri-
a branch of mathematics. bution, characterizing a population on the basis of the information available from the sample
P

P
observations. In the formulation and testing of hypothesis, statistical methods are extremely use-
ful. Whether the grades of students increased because they are motivated or whether the new
4.1 Basic Concepts teaching method is effective in discussing a particular topic are some examples of statements of
hypothesis and these are tested by proper statistical tools.
PU

PU
Statistics is defined as a branch of mathematics which is concerned with facilitating wise decision-
making in the face of uncertainty and that, therefore develops and utilizes techniques for collection,
Scope of Statistics
effective presentation, and proper analysis of data.
1. Statistics and Industry. Statistics is widely used in many industries. In industries, control charts
are widely used to maintain a certain quality level. In production engineering, to find whether the
Branches of Statistics product is conforming to specifications or not, statistical tools, namely inspection plans, control
charts, etc., are of extreme importance. In inspection plans we have to resort to some kind of
1. Descriptive Statistics is concerned with the description and summarization of data, It deals with sampling - a very important aspect of Statistics.
the techniques used in the collection, presentation, organization, and analysis of the data on hand.
2. Statistics and Commerce. Statistics are lifeblood of successful commerce. Any businessman
2. Inferential Statistics is concerned with the drawing of conclusions from data. It deals with the cannot afford to either by under stocking or having overstock of his goods. In the beginning he
techniques used in generalizing from samples to populations, performing estimations and hypothesis estimates the demand for his goods and then takes steps to adjust with his output or purchases.
tests determining relationships among variables, and making predictions. Thus statistics is indispensable in business and commerce.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 4 43 Lesson 4 44

3. Statistics and Economics. Statistical methods are useful in measuring numerical changes in individually do not constitute any statistical data and do not serve any purpose for any statistical
complex groups and interpreting collective phenomenon. Nowadays the uses of statistics are abun- enquiry.
dantly made in any economic study. Both in economic theory and practice, statistical methods
play an important role. 3. Statistical laws are not exact. It is well known that mathematical and physical sciences are
exact. But statistical laws are not exact and statistical laws are only approximations. Statistical
4. Statistics and Education. Statistics is widely used in education. Research has become a
conclusions are not universally true. They are true only on an average.
common feature in all branches of activities. Statistics is necessary for the formulation of policies
to start new course, consideration of facilities available for new courses etc. There are many people 4. Statistics table may be misused. Statistics must be used only by experts; otherwise, statistical
engaged in research work to test the past knowledge and evolve new knowledge. These are possible methods are the most dangerous tools on the hands of the inexpert. The use of statistical tools
only through statistics. by the inexperienced and untraced persons might lead to wrong conclusions.

S
5. Statistics and Planning. Statistics is indispensable in planning. In the modern world, which can
5. Statistics is only one of the methods of studying a problem. Statistical method do
be termed as the “world of planning”, almost all the organizations in the government are seeking
DM not provide complete solution of the problems because problems are to be studied taking the

DM
the help of planning for efficient working, for the formulation of policy decisions and execution of
background of the countries culture, philosophy or religion into consideration. Thus the statistical
the same. In order to achieve the above goals, the statistical data relating to production, consump-
study should be supplemented by other evidences.
tion, demand, supply, prices, investments, income expenditure etc and various advanced statistical
techniques for processing, analyzing and interpreting such complex data are of importance. In
India statistics play an important role in planning, commissioning both at the central and state Population and Sample
government levels.
In statistics, we are often interested in gathering information from a group of objects. If the group
6. Statistics and Medicine. In Medical sciences, statistical tools are widely used. In order to test in consideration consists of large number of objects, we try to obtain information about the group by
the efficiency of a new drug or medicine, t - test is used or to compare the efficiency of two drugs examining its subgroup.
or two medicines, t-test for the two samples is used. More and more applications of statistics are
P

P
at present used in clinical investigation. Definition 14

7. Statistics and Modern Applications. Recent developments in the fields of computer technol- The total collection of all the elements that we are interested in is called a population. A
ogy and information technology have enabled statistics to integrate their models and thus make subgroup of the population that will be studied in detail is called a sample.
PU

PU
statistics a part of decision making procedures of many organizations. There are so many software
packages available for solving design of experiments, forecasting simulation problems etc. In order for the data from the sample is informative about the population, it must be representative
of the population. Being representative of the population does not mean that the characteristic of the
Limitations of Statistics sample is exactly that of the total population, but instead the sample was obtain in such way that every
member of the population had an equal chance to be included in the sample.
1. Statistics is not suitable to the study of qualitative phenomenon. Since statistics is
basically a science and deals with a set of numerical data, it is applicable to the study of only
Definition 15
these subjects of enquiry, which can be expressed in terms of quantitative measurements. As a
A sample of k members of a population is called a random sample, also called a simple random
matter of fact, qualitative phenomenon like honesty, poverty, beauty, intelligence etc, cannot be
sample, if the members are chosen in such a way that all possible choices of the k members are
expressed numerically and any statistical analysis cannot be directly applied on these qualitative
equally likely.
phenomenon.

2. Statistics does not study individuals. Statistics does not give any specific importance to the After a random sample is obtain from the population, we can use statistical inference to draw general-
individual items; in fact it deals with an aggregate of objects. Individual items, when they are taken izations about the population by examining the members of the sample.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 4 45 Lesson 4 46

4.2 Steps in Statistical Investigation Probability Sampling Techniques

1. Defining the problem 1. Simple Random Sampling. A probability sampling technique wherein all possible subsets con-
sisting of n elements selected from the N elements of the population have the same chances of
(a) Identify a specific problem.
selection.
(b) Define the scope and limitations, assumptions to be made, and expected outcomes.
2. Systematic Sampling. This is a probability sampling technique wherein the selection of the
2. Collection of data first element is at random and the selection of other elements in the sample is systematic by
subsequently taking every kth element from the random start where k is the sampling interval.
(a) Make sure to collect the data properly.
(b) Incomplete, fabricated, outdated, and inaccurate data are useless. 3. Stratified Random Sampling. A probability sampling method where we partition the population

S
into non-overlapping strata or group and then a proportional sample is chosen from each strata.
3. Summarization and tabulation of data
The actual sample is the sum of the samples derived from each strata.
(a) This refers to organization of data in text, tables, graphs and charts, so that logical conclusion
DM

DM
4. Cluster Sampling. A probability sampling technique wherein we partition the population into
can be derived from them.
non-overlapping groups or clusters consisting of one or more elements, and then select a sample
(b) Explore the data to obtain additional insight that could contribute to the study.
of clusters. Every member of the selected cluster will be considered as sample.
4. Analysis of data
Non-Probability Sampling Techniques
(a) This pertains to the process of deriving from the given data relevant information from which
numerical descriptions can be formulated. 1. Accidental Sampling. Sample is chosen by the researcher by the obtaining members of the
population in a convenient, often haphazard way.
(b) Summarized data must be examined so that insights and meaningful information ca be pro-
duced to support decision-making or solutions to the question or problem at hand. 2. Quota Sampling. There is specified number of persons of certain types is included in the sample.
The researcher is aware of categories within the population and draws samples from each category.
P

P
5. Interpretation of data and results
The size of each categorical sample is proportional to the proportion of the population that belongs
(a) Refers to the task of drawing conclusions from the analyzed data. in that category.
(b) Results must be able to answer the research problem and give recommendations.
PU

PU
3. Purposive Sampling. The researcher employs his or her judgments on choosing which he or she
6. Presentation of the result believes are representative of the population.

(a) Present all pertinent results in a clear and concise manner. 4. Snowball Sampling. This technique is also called referral sampling. A primary set of samples
(b) Use appropriate form of media to present results. are chosen based on the criteria set by the researcher. Information on where to find succeeding
set of sample having the same criteria will be gathered from this primary set in order to expand
4.3 Sampling and Sampling Techniques the number of samples.

Sampling refers to the process of obtaining samples from the population. Sampling maybe categorized as
4.4 Sample Size Considerations
either probability sampling or non-probability sampling. Probability sampling, also referred to as random
sampling, is the method of sampling in which every member of the population have equal chance of The sample size is typically denoted by n and it is always a positive integer. No exact sample size can be
being selected as sample; otherwise, it is considered as non-probability sampling. We should note that in mentioned here and it can vary in different research settings. However, all else being equal, large sized
able to properly use the techniques of statistical inference, probability sampling must be used to obtain sample leads to increased precision in estimates of various properties of the population.
samples. To determine the sample size we can apply one of the following methods:

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 4 47 Lesson 4 48

1. Slovin’s Formula. Slovin’s formula is used to calculate the sample size n given the population 3. Minimum Sample Size for Estimating a Population Proportion The estimated minimum
size and a margin of error E. It is a formula use to estimate sampling size of a random sample sample size n needed to estimate a population proportion p to within E at 100(1 − ¸)% confidence
from a given population. We can compute is
(z¸=2 )2 p̂(1 − p̂)
n= :
N E2
n= ;
1 + NE 2 This is also called the Cochran Formula.
where N is the population size.

The dilemma here is that the formula for estimating how large a sample to take contains the
Example 27. A researcher plans to conduct a survey about food preference of BS Stat students. If the number p̂, which we know only after we have taken the sample. There are two ways out of this
population of students is 1000, use the Slovin’s formula to find the sample size if the margin of error is 5%. dilemma.

S
Solution. Using the Slovin’s formula, we get
• First, typically the researcher will have some idea as to the value of the population proportion
DM

DM
1000 p, hence of what the sample proportion p̂ is likely to be. For example, if last month 37% of
n= ≈ [Link]
1 + 1000(0:05)2 all voters thought that state taxes are too high, then it is likely that the proportion with that
opinion this month will not be dramatically different, and we would use the value 0.37 for p̂
Therefore, the researcher needs to survey 286 BS Stat Students.
in the formula.

2. Minimum Sample Size for Estimating a Population Mean. The estimated minimum sample • The second approach to resolving the dilemma is simply to replace p̂ in the formula by 0.5.
size n needed to estimate a population mean — to within E units at 100(1 − ¸)% confidence is This is because if p̂ is large then 1 − p̂ is small, and vice versa, which limits their product to
a maximum value of 0.25, which occurs when p̂ = 0:5. This is called the most conservative
(z¸=2 )2 ff 2 estimate, since it gives the largest possible estimate of n.
n= ;
E2
where ff is the known population standard deviation, E is the margin of error and z¸=2 is a value
P

P
which can be obtained in the z-table. Example 29. Suppose we are doing a study on the inhabitants of a large town, and want to find out
how many households serve breakfast in the mornings. We don’t have much information on the subject
Example 28. Suppose we want to know the average age of STEM students. We would like to be 99% to begin with, so we’re going to assume that half of the families serve breakfast: this gives us maximum
PU

PU
confident about our results. From previous study, we know that the standard deviation for the population variability. Here, p̂ = 0:5. We want 95% confidence and at least 5% precision.
is 1.3. How many students should be chosen for a survey if the margin of error is 0.2.
Solution. Find z¸=2 in the z-table. We have
Solution. Find z¸=2 by looking at the z-table.
¸ = (1 − 0:95) =⇒ z¸=2 = z0:025 :
¸ = (1 − 0:99) = 0:01 =⇒ z¸=2 = z0:005 :
The closest z-score for 0:025 in the z-table is 1:96. A 95% confidence level gives us Z values of 1.96,
The closest z-score for 0:005 in the z-table is 2:58. Thus, we get
(1:96)2 (0:5)(1 − 0:5)
(2:58)2 (1:3)2 n= ≈ [Link]
n= ≈ [Link] (0:05)2
(0:2)2
Hence, a random sample of 385 households in our target population should enough to give us the
which we round up to 282, since it is impossible to take a fractional observation. We need a 282 STEM confidence levels we need.
students as a sample for our study.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 4 49 Lesson 4 50

Finite Population Correction for Proportions 3. The interval level of measurement ranks data, and precise differences between units of measure
do exist; however, there is no meaningful zero.
If the population is small then the sample size can be reduced slightly. This is because a given sample size
provides proportionately more information for a small population than a large population. The formula
is Example: Temperature, IQ, SAT score
n0
n= ;
n0 − 1 4. The ratio level of measurement possesses all the characteristics of interval measurement, and
1+
N there exists a true zero. In addition, true ratios exist when the same variable is measured on two
where n0 is the Cochran’s sample size recommendation, N is the population size and n is the new adjusted different members of the population
sample size.

Example: Height, Weight, volume, Time, Salary, Age

S
Example 30. In the preceding example, if there were just 1000 households in the target population, we
would calculate
385
n= ≈ [Link] 4.7 Presentation of Data
DM 385 − 1

DM
1+
1000 After data have been collected, the researcher can now present them in the following logical methods.
All we need are 279 households in our sample, a substantially smaller sample size.
1. Textual Form. Data are presented in paragraph of text. The text highlights the important figures
or results that the researcher wishes to focus on.
4.5 Methods of Data Collection
1. Survey Method. The survey is a method of collecting data on the variable of interest by asking 2. Tabular Form. Data appears in a systematic manner in rows and columns.
people questions. This may be done, by interview or by using questionnaires. The following is an example of a Simple or One-Way Table.

2. Observation. Observation is a method of obtaining data or information by using our primary

Table 1
senses.
Frequency Distribution of the
P

P
3. Experiment. Experiment is a method of collecting data where there is direct human intervention Students Enrolled for the Last 6 Years
on the conditions that may affect the values of the variable of interest. Year Frequency
2012 13,450
PU

PU
4.6 Levels of Measurement 2013 13,200
2014 15,389
1. The nominal level of measurement classifies data into mutually exclusive (non-overlapping)
2015 16,790
categories in which no order or ranking can be imposed on the data.
2016 18,900
2017 19,500
Example: Gender (male, female), Zip Code, Color, Nationality, Political affiliation, Religious Total 97,229
affiliation.

2. The ordinal level of measurement classifies data into categories that can be ranked; however,
precise differences between the ranks do not exist.

Example: Grade(A,B,C,D,F), Rating Scale/Likert scale, Ranking of tennis players, Judging (First
place, second place, etc.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 4 51 Lesson 4 52

The following is an example of a Two-Way Table. Subdivided Column Charts

Table 2
Number of Students Enrolled for the Last 6 Years
When Grouped According to Sex

Year
Sex
2012 2013 2014 2015 2016 2017 Total
Male 5560 6095 7386 8056 7945 6451 41493
Female 7890 7105 8003 8734 10955 13049 55736

S
Total 13450 13200 15389 16790 18900 19500 97229 (b) Histogram is similar to the bar graph but the base of the rectangle has a length exactly
equal to the class width of the corresponding interval. Also, there are no spaces between
3. Graphical Form. Data or relationship among variables could be presented in visual form, thru
DM rectangles.

DM
graph or diagrams. In that manner, the reader can easily perceive what is being meant by the
figure or any trend being portrayed by the data. Histogram

Types of Statistical Charts

(a) Bar Graph (Vertical Bar/Column Charts) is applicable for showing comparison of
amount of a variable of interest collected over time.

Simple Chart
P

P
(c) Pictograph is similar to the bar chart but instead of bars, we use pictures or symbols to
represent a value or an amount.
PU

PU
Pictograph

Grouped Column Charts

(d) Pie Chart is a circular graph partitioned into several section, depicting relative percentage
with respect to the total distribution.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 4 53 Lesson 4 54

Pie Chart 4.8 Measures of Central Tendency

A measure of central tendency or average is a location measure that pinpoints the center or typical
middle value of a data set. A convenient way of describing a set of data with a value that describes
the average characteristic a data set. The three common measures of central tendency are the mean,
median and mode.

Mean

Definition 16

S
(e) Line Graph is a graph used to visualize data that changes continuously over time. Suppose that a variable x assumes values x1 ; x2 ; : : : ; xn . The arithmetic mean x of these values
is defined as
Simple Line Graph 1X n
x1 + x2 + · · · + xn
P
x
DM x=

DM
= xi = :
n n i=1 n

The (arithmetic) mean of x is obtained by adding all its observed values and dividing the sum by the
total number of observations.

Example 31. The scores of 15 students in Mathematics in the Modern World on an exam consisting
of 25 items are 25,20,18,18,17,15,15,15,14,14,13,12,12,10,10. Determine the mean score for this exam.
Multiple Line Graph
Solution. Let x denote the score of a random student from the sample of 15 students in Mathematics in
the Modern World. The sum of these scores is x = 228. Hence, the mean score of the 15 students is
P
P

P
228
P
x
x= = = [Link]
n 15
PU

PU
There are cases when the observations in a data set assume respective weights. In this case where the
(f) Statistical Map is used to show data in geographical areas.
weights are positive integers, we can call these weights as frequencies. The following gives a formula
Statistical Map for the weighted mean of a weighted data set.

Definition 17
Given the x values x1 ; x2 ; : : : ; xn assuming respective weights w1 ; w2 ; : : : ; wn , the weighted mean
is defined as
w1 x1 + w2 x2 + · · · + wn xn
P
wx
x= P = :
x w1 + w2 + · · · + wn

Example 32. Suppose that we are asked to get the mean of the data set 1; 1; 3; 3; 3; 3; 4; 4; 4; 6; 6; 8.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 4 55 Lesson 4 56

Using the original formula for the arithmetic mean we find that Course xi wi wi xi

(1 + 1) + (3 + 3 + 3 + 3) + (4 + 4 + 4) + (6 + 6) + 8 BM 112 1.25 3 3.75

x= BM 101 1.00 3 3.00
12
2·1+4·3+3·4+2·6+1·8 AC 103 1.25 6 7.50
=
1+4+3+2+1 MG 101 1.00 3 3.00
2 + 12 + 12 + 12 + 8
= EC 111 1.50 3 4.50
12
46 MK 101 1.50 3 4.50
=
12 FM 111 1.20 3 3.60
= 3:833 PE 1 1.00 2 2.00

S
Total w = 26 w x = 32:00
P P
We can interpret the mean of the data values as the fulcrum or center of gravity in a balance scale as
shown below. We see from the column totals that w = 26 and w x = 32. Therefore, the weighted mean or the
P P

DM

DM
general weighted average (GWA) of Julius Garde for the first semester of AY 2019-2020 is

32
P
4 wx
x= P = = [Link]
w 26
3

2
Median

1 Definition 18
The median, usually denoted by x̃, is the middle value of a data set if the observations are
P

P
1 2 3 4 5 6 7 8 arranged either in increasing or decreasing order.

mean = 3:8333 Outliers in the data set do not affect the median. Thus, the median is preferred over the mean as a
PU

PU
measure of central tendency when the data contains outliers. To find the median, begin by listing the
data in order from smallest to largest, or largest to smallest.

Example 33.
Calculate the General Weighted Average (GWA) of If the number of data values, N, is odd, then the median is the middle data value. This value can be
Course Grade Units found by rounding N=2 up to the next whole number. If the number of data values is even, there is no
Julius Garde for the first semester of school year
BM 112 1.25 3 one middle value, so we find the mean of the two middle values (values N=2 and N=2 + 1)
2019-2020 as shown in the following table.
BM 101 1.00 3
AC 103 1.25 6 Example 34. Given the scores of 15 students in Mathematics in the Modern World on an exam consisting
Solution. To solve for the GWA, we first consider
MG 101 1.00 3 of 25 items:
the entries on the second column of the table as the
EC 111 1.50 3 25; 20; 18; 18; 17; 15; 15; 15; 14; 14; 13; 12; 12; 10; 10
points xi and the entries in the third column as the
MK 101 1.50 3
corresponding weights wi . By constructing a fourth Since the data is already arranged in decreasing order and there are 15 observations, hence, we round
FM 111 1.20 3 15
column consisting of the products wi xi and finding up = 7:5 to the nearest whole number, which is 8, and take the 8th observation from the left (or
PE 1 1.00 2 2
the column totals, we get the table below. right). Therefore, the median is x̃ = 15: In comparison to example 31, the computed mean is 15:2.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 4 57 Lesson 4 58

Example 36. Suppose that we wanted to know the “average color” of cars used by the residents in a
given village. In our vehicle color survey, we collected the following data.
4
Color Frequency
3 Blue 3
Green 5
2
Red 4
1 White 3
Black 2
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Grey 3

S
Since color of vehicles are measured up to the nominal level, the most appropriate measure for the
mean
“average color” is then the mode. The most frequent color is Green, a total of 5 vehicles. Therefore, the
median
DM “average color” in our survey data must be Green.

DM
It is possible for a given data set to have more than one modes. Such a data set is said to be multimodal.
Remark. In general, the median need not equal the mean.
If a given set has only one mode, the data set is unimodal. If it has two modes, the data set is bimodal,
Example 35. The data given below is the total number of hours lost due to tardiness and absences of and so on.
employees in a company in a given year. Find the median.

Month Hours Lost Solution. If the data are arranged in increasing order, we have 4.9 Measures of Dispersion or Variability
January 55
February 23 Measures of dispersion are descriptive summary measures that helps us characterize the data set in terms
March 24 20; 23; 24; 27; 30; 32; 37; 37; 40; 48; 42; 55:
of how varied the observations are from the center. If its value is small, then this indicates that the
April 37
May 37 observations are not too different from the center. On the other hand, if its value is large, then this
June 48
Since there are 12 observations (even), we take note of the two
indicates that the observations are very different from the center or that they are widely spread out from
P

P
July 42 middle observations then compute
August 27 the center.
September 20
32 + 37
October 40 x̃ = = [Link]
November 30 2 Range
PU

PU
December 32
Definition 20
Therefore, the median number of hours lost due to tardiness and absences of employees in a company The range is the difference between the largest and the smallest observations or items in a set of
in the given year is 34:5 hours. data.

Mode The range of a data set is easy to compute, but it is a limited measure because it depends on only two
of the numbers (the highest and the lowest) in the data set. Hence, the range can easily be affected
Definition 19
by outliers. Also, it does not provide any information regarding the concentration of the data from the
The mode is the most frequent observation in a given data set. center.

Outliers in the data set do not affect the mode. It is possible that the mode of a data set does not Example 37. The following are scores of 20 coming from two different sections, 10 from each section,
exist, and it is not always unique. It is an appropriate measure of average for data measured only in the in a 50-item exam in MMW.
nominal level. We will denote mode using the symbol x̂. section 1 40 38 42 40 39 39 43 40 39 40
section 2 46 37 40 33 42 36 40 47 34 45

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 4 59 Lesson 4 60

For section 1, the highest score is 43, while the lowest score is 38. Thus, the population variance mainly because of the divisor n − 1. The reason behind this is rather technical
and mathematical in nature. Simply taken, the divisor n − 1 removes the “bias” in s 2 when we want it
range = 43 − 38 = 5: to estimate ff 2 for the purposes of making inferences.

On the other hand, for section 2, the highest score is 47, while the lowest score is 33. Thus,
Notice that the variance is a nonnegative quantity because it came from averaging squared quantities.
range = 47 − 33 = 14: We also realize that there is one major drawback to using the variance. If we follow the steps in calcu-
lating the variance, we find that the variance is measured in terms of square units because we took the
Therefore, the scores of students surveyed from section 2 gets a wider range than those of students
squares of the deviation. For example, if our sample data is measured in terms of meters, then the units
surveyed from section 1.
for a variance would be given in square units.

S
Variance and Standard Deviation

Suppose that the center of a population data set {x1 ; x2 ; : : : ; xN } is best described by the arithmetic
DM In order to standardize the units, we can take the square root of the variance to eliminate the problem of

DM
mean — and that our goal is to get the average “distance” of each data point xi form —. Naturally, we squared units, and gives us a measure of the spread that will have the same units as our original sample
would like to compute for or population data.
N
1 X
(xi − —):
N i=1
However, using the properties of summations, and the fact that n— = x1 + x2 + · · · + xN we can check Definition 22
that
N
X N
X N
X The population (sample) standard deviation is the nonnegative square root of the the pop-
(xi − —) = xi − — = N— − N— = 0:
i=1 i=1 i=1
ulation (sample) variance. In symbols,

In other words, the sum of the deviations from the mean is 0, and therefore, we cannot have a meaningful √ √
ff = ff 2 and s = s 2:
measure of variability this way. The reason behind this fact is that some of the deviations from the mean
P

P
are negative (those which are to the left of the mean) and some are positive (those which are to the right
of the mean) and they cancel each other out. However, we can work our way out of this unfortunate
situation if we can ignore the signs of these deviations. One way to do this is to take the square these
PU

PU
deviations from the mean. We then have the following definition.

Definition 21
Example 38. Using the sample data sets in example 37, determine which section exhibits a greater
The variance of a population data set {x1 ; x2 ; : : : ; xN } with population mean — is defined as variability in terms of standard deviations.
N
1 X
ff 2 = (xi − —)2 :
N i=1
Solution. Let x denote the scores of students sampled from section 1 and let y denote the scores of
On the other hand, the variance of a sample data set {x1 ; x2 ; : : : ; xn } with sample mean x is students sampled from section 2. To calculate the standard deviations of each sample, we first take note
defined as that the sample means from each section are
n
1 X
s2 = (xi − —)2 : P
x 400 y 400
P
n − 1 i=1 x= = = 40 and y = = = 40:
n 10 n 10

As we may have noticed, the formula for the sample variance differs significantly from the formula for To calculate the sample standard deviation, we construct the following table.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 4 61 Lesson 4 62

x y x −x y −y (x − x)2 (y − y )2 Assessment
40 46 0 6 0 36
38 37 −2 −3 4 9 1. A research objective is presented. For each,identify the (a)population and (b) sample in the study.
42 40 2 0 4 0
(a) A polling organization contacts 2141 male university graduates who have a white-collar job
40 33 0 −7 0 49
and asks whether or not they had received a raise at work during the past 4 months.
39 42 −1 2 1 4
(b) A quality-control manager randomly selects 70 bottles of ketchup that were filled on July 17
39 36 −1 −4 1 16
to assess the calibration of the filling machine.
43 40 3 0 9 0
40 47 0 7 0 49 (c) Every year the PSA releases the Current Population Report based on a survey of 50,000
39 34 1 36 households. The goal of this report is to learn the demographic characteristics, such as

S
−1 −6
40 45 0 5 0 25 income, of all households within the Philippines.
x = 400 y = 400 (x − x)2 = 20 (y − y )2 = 224
P P P P
DM 2. Determine the level of measurement of each variable.

DM
Therefore, the sample variance for the sample from section 1 is
(a) birth order among siblings in a family
(x − x)2 20
P
s = 2
= = 2:2222; (b) favorite movie
n−1 9
(c) volume consumption of water used by a household in a day
while the sample variance for the sample from section 2 is
(d) eye color
(y − y )2 224
P
2
s = = = [Link] (e) number of siblings
n−1 9
3. Determine the type of sampling used.
Taking square roots, we find that the sample standard deviations of section 1 and section 2 respectively
√ √
are 2:2222 ≈ 1:49 and 24:8888 ≈ 4:99. We can conclude that for these samples, the one from (a) A member of Congress wishes to determine her constituents’ opinion regarding estate taxes.
P

P
section 1 exhibits the lesser variability than that from section 2. We comment that even though the two She divides her constituency into three income classes: low-income households, middle-income
samples have equal means, the standard deviations showed the actual difference between the two data households, and upper-income households. She then takes a simple random sample of house-
sets. holds from each income class.
PU

PU
(b) A college official divides the student population into five classes: freshman, sophomore, junior,
senior, and graduate student. The official takes a simple random sample from each class and
asks the members opinions regarding student services.
(c) The presider of a guest-lecture series at a university stands outside the auditorium before a
lecture begins and hands every fifth person who arrives, beginning with the third, a speaker
evaluation survey to be completed and returned at the end of the program.
(d) To determine his DSL Internet connection speed, Shawn divides up the day into four parts:
morning, midday, evening, and late night. He then measures his Internet connection speed
at 5 randomly selected times during each part of the day.
(e) 24 Hour Fitness wants to administer a satisfaction survey to its current members. Using its
membership roster, the club randomly selects 40 club members and asks them about their
level of satisfaction with the club.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 4 63 Lesson 5 64

4. Patricia categorized her spending for this month into four categories: Rent, Food, Fun, and Other.
Lesson 5: Linear Programming
The percents she spent in each category are pictured here. If she spent a total of PhP 26,000 this
month, how much did she spend on rent?
Learning Outcomes
At the end of the lesson, students should be able to

1. demonstrate understanding of a linear programming model;

2. identify the different components of a linear programming problem;

3. develop a linear programming model that involves maximization and minimization;

S
4. demonstrate understanding of linear inequalities;

5. identify the different steps in solving linear inequalities in two variables;

DM

DM
5. You recorded the time in seconds it took for 8 participants to solve a puzzle. The times were: 6. find a solution space to a system of linear inequalities in two variables;
15.2, 18.8, 19.3, 19.7, 20.2, 21.8, 22.1, 29.4.
7. identify the different steps in solving linear programming problem in two variables using
(a) Calculate the mean and the median time it took for the 8 participants to solve a puzzle. graphical method;
(b) Calculate the range and standard deviation of the time it took for the 8 participants to solve
8. find an optimal solution of a linear programming problem using the concept of corner points.
the puzzle.

6. Make up three data sets with 5 numbers each that have:

(a) the same mean but different standard deviations.

5.1 Modeling with Linear Programming
P

P
(b) the same mean but different medians. This lesson will familiarize you to a particular technique in operations research that is very useful in our
daily lives, more specifically in decision making that involves optimization of scarce resources. You will
(c) the same median but different means.
learn how to develop a linear programming model out a problem that involves optimization. Different
component of a linear programming problem will also be discussed in this lesson. Graphical and algebraic
PU

PU
method of solutions to different types of linear programming models will also be discussed. Solutions
to linear programming problems with the use of Microsoft excel solver will also be introduced at the
succeeding lessons.

Many businesses in the Philippines have a common goal that is to maximize their profit while minimizing
their operation cost. With limited resources, obtaining such goal is possible with the use of proper
planning and integrating linear programming technique. Linear Programming is a mathematical method
in maximizing or minimizing linear functions subject to set of linear constraints. In business production,
the objective function is a linear function that either maximizes profit or minimizes cost that is subject
to a set of linear inequalities called linear constraints. These set of linear constraints can be viewed as
set of production requirements that is usually limited in quantity.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 5 65 Lesson 5 66

Example 39 (The RAVLAM Company). RAVLAM Company produces two types of abaniko fan, small abaniko fan and large abaniko fan are Php 5.00 and Php7.00 respectively, then the objective function of
and large, from three raw materials R1 , R2 and R3 . The following tables shows the materials used in the model is:
their production and the profit they earned for product: Maximize: P = 5x1 + 7x2 ;

amt. of raw materials where P = total profit.

per piece of (in gms) max. daily availability (in gms.)
small size large size The next step is to develop the linear constraints of the model. These are restrictions in the raw materials
Raw Material (R1 ) 80 70 5,000 of production and daily demand of the product. Constraints are usually set of linear inequalities that
Raw Material (R2 ) 100 150 9,000 define the scarcity or abundance of particular requirements in production. In constructing each constraint,
Raw Material (R3 ) 175 250 13,000 it is very useful to be familiarizing in the given inequality.

S
Profit Per Price PhP 5.00 PhP 7.00 0 1 0 1
usage of raw material A @ daily availability of A
@ ≤ :
Based on their past sales, the total demand for small size abaniko fan should not exceed by 50 units. by both abaniko fan each raw material
DM

DM
RAVLAM Company wants to determine the best combination of their product that will maximize their Always remember that each requirement in the production of abaniko fan will define exactly one con-
daily profit. straint. The daily usage of each type of abaniko fan as shown in the table can be written as:

This is a typical type of problem where linear programming can be used. To be able to help the Daily usage of raw material R1 by small abaniko fan = 80x1 :
RAVLAM Company in their objective, first we need to develop the necessary linear programming model
Daily usage of raw material R1 by large abaniko fan = 70x2 :
of this problem. Basically, there are three components of a linear programming model. These are:
These imply that the daily usage of raw material R1 by both abaniko fan sizes is 80x1 + 70x2 . In similar
1. decision variables that we want to determine; manner we can get the second and third constraints of the LP model using raw material R2 and R3,
that is,
2. objective function that we want to maximize or minimize; Raw Material R2 : 100x1 + 150x2 ≤ 9; 000
P

P
Raw Material R3 : 175x1 + 250x2 ≤ 13; 000
3. set of linear constraints that the solution must satisfy.
Another constraint of the problem can be found on the total daily demand of the abaniko fan. Since
Using these three basic components of linear programming model, we can transform the above problem the daily total demand of small size abaniko fan should not exceed by 50 units, therefore, we restrict
PU

PU
into a linear programming model. that x1 ≤ 50. Now we can finally write the final linear programming model for the “RAVLAM Company
production”. The complete model is
The first step is to define the decision variables. Decision variables are usually what are asked in the
problem to obtain your objective or goal. In the above problem, RAVLAM, Company wants to maximize Maximize P = 5x1 + 7x2
their daily profit by knowing how many abaniko fan of each sizes (small and large) will they produced Subject to: 80x1 + 70x2 ≤ 5000
daily. Thus the decision variables of the LP model are defined as: 100x1 + 150x2 ≤ 9; 000
175x1 + 250x2 ≤ 13; 000
x1 = daily production of small abaniko fan
x1 ≤ 50
x2 = daily production of large abaniko fan
x1 ; x2 ≥ 0:
After defining the decision variable we can now define the objective function. Objective function is a
linear function or equation that defines what we want to optimize (maximize or minimize). Since the The last constraints where x1 ; x2 ≥ 0 is called the nonnegativity restrictions of the decision variable.
company wants to maximize their profit, we can use the profit contribution of each type of abaniko Since the company is producing a product this implies that there should be no negative values of the
fan as seen in the above table to form the objective function. Given that the profit per piece of small decision variables. All values of the decision variables that satisfy each linear constraint is called feasible

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 5 67 Lesson 5 68

solution. From this feasible solution the objective is to find the best feasible solution that will satisfy 5.2 Solution Set of Systems of Linear Inequalities in Two Variables
the objective function called the optimal solution.
Finding the solution of a linear programming model that contains two decision variables requires finding
Example 40 (The Diet Problem). Jackie is a basketball player who regularly monitors his diet so that all the feasible solutions of the constraints. Since the constraints of a linear programming model is a set
regular intake of calories, sugar carbohydrates and protein will satisfy his daily minimum nutritional of linear inequalities, it is necessary to have a deep knowledge in solution of system of linear inequalities.
requirements. Every day he prepares three foods egg, rice and chicken. Each day he must consume
at least 600 calories, 100 grams of sugar, 283 grams of carbohydrates and 300 grams of protein. The
Definition 23
nutritional content per unit of each food is shown in the following table.
A system of linear inequalities in two variables x1 and x2 is a set of two linear inequalities of the
calories sugar carbohydrates protein unit price form 8
Egg (1 piece) 72 1.1 0.4 7 PhP 7.00 <a1 x1 + b1 x2 ≥ (or ≤) c1

S
>

Rice (1 cup) 204 0.08 44.08 4.2 PhP 10.00 :a2 x1

>
+ b2 x2 ≥ (or ≤) c2 ;
Chicken (100 grams) 195 0 0 29.55 PhP 25.00
DM where ai ; bi ; ci ∈ R, for i = 1; 2. The set S of all ordered pairs (x1 ; x2 ) satisfying both the

DM
Develop a linear programming model that satisfies the daily nutritional requirements of Jackie at the inequalities is called the solution space or feasible region of the system.
minimum cost.
To solve the system, we usually proceed using the graphing method:
Solution. Define the decision variables:

Step 1. Replace ≥ and/or ≤ symbols in the system by = and graph the lines that corresponds to each
Let
inequality.
x1 = amount of egg to be consumed.
x2 = amount of rice to be consumed.
Step 2. Determine the solution space of each linear inequality using feasibility test. Choose a point
x3 = amount of chicken to be consumed.
that is not on the linear equation and substitute it to the linear inequality. If it satisfies the
P

P
Then the linear programming model is linear inequality then the region where the point belongs is the solution space of that particular
linear inequality.
Maximize: C = 7x1 + 10x2 + 25x3
Subject to:
PU

PU
Step 3. Determine the intersection of the solution space of the two linear inequalities. All the points
within this region are the solution space or feasible region of the system of linear inequalities.
72x1 + 204x2 + 195x3 ≥ 600 (calorie constraint)
1:1x1 + 0:08x2 ≥ 100 (sugar constraint)
Example 41. Determine the solution space of the following system of linear inequalities using the
0:4x1 + 44:08x2 ≥ 283 (carbohydrate content)
graphing method. 8
7x1 + 4:2x2 + 29:55x3 ≥ 300 (Protein Constraint) <x
>
+ 2y ≤ 4
x1 ; x2 ; x3 ≥ 0 (nonnegativity) :3x
>
+ 2y ≤ 6

Step 1. Graph the lines corresponding to the equations x + 2y = 4 and 3x + 2y = 6.

(a) The intercepts of x + 2y = 4 are (4; 0) and (0; 2). (Red Line)

(b) The intercepts of 3x + 2y = 6 are (2; 0) and (0; 3). (Blue Line)

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 5 69 Lesson 5 70

Step 1. Determine the feasible solution or solution space of the constraints using solution of system of
5 linear inequalities in two variables.

Step 2. Determine the corner points of the solution space by getting the point of intersection of each
pair of lines that defines it.
−4 −2 2 4 6
Step 3. Evaluate the objective functions using this corner points. The corner points the yields the
optimum value (maximum or minimum) is the optimal solution of the linear programming
−5
model.

Theorem 2

S
Step 2. Find the solution space of each linear inequalities by feasibility test. We may choose the point In any linear programming model, the optimal solution (if it exists) can be found in one of the
of origin (0; 0) as test point since it does not lie in either inequalities. corner points of the solution space or feasible region of the constraints.
DM

DM
At (0; 0), x + 2y ≤ 4 is equivalent to 0 ≤ 4, which is true. Therefore, all the points in the same side of Hence, the optimal solutions tot he linear programming problem can be achieved at one among the
the line as the origin are solutions to x + 2y ≤ 4. corner points.

Example 42 (Solution of the (RAVLAM Company) Problem).

At (0; 0), 3x + 2y ≤ 6 is equivalent to 0 ≤ 6, which is true. Therefore, every point in the same side of
the line as the origin are solutions to 3x + 2y ≤ 6. Maximize P = 5x1 + 7x2
Subject to: 80x1 + 70x2 ≤ 5000
Step 3. Determine the solution space of the system by getting the intersection of the solution space of
100x1 + 150x2 ≤ 9; 000
each linear inequality.
175x1 + 250x2 ≤ 13; 000
P

P
x1 ≤ 50
5
x1 ; x2 ≥ 0:

Step 1. Solution space or feasible region of the constraints. Using a graphing software, the following
PU

PU
−4 −2 2 4 6 graph was obtained:

−5

5.3 Graphical Solution for a Linear Programming Model

Linear programming model in two variables can be solved using graphical method. Although three
variables linear programming model can also be solved using this method, it is highly advised to use the
algebra method since we are dealing with solution space in three dimensions. The following steps can Step 2. Identify the corner points of the feasible region by getting the intersection points of each pair
be used to solve linear programming model in two variables. of lines that defines it.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 5 71 Lesson 5 72

Assessment
1. Sketch the solution sets of the following systems of linear inequalities.

(a) x − y ≤ 10 (b) 3x − 4y ≥ 14
x +y ≤5 x +y ≤5

2. Solve the following linear programming problems.

(a) In a manufacturing process, the final product has a requirement that it must weigh exactly
150 [Link] two raw materials used are A, with cost of Php 6 per unit and B, with a cost of

S
: Evaluate the objective functions using this corner points. The corner points the yields the optimum Php 12 per unit. At least 15 units of B and no more than 20 units of A must be used. Each
value (maximum or minimum) is the optimal solution of the linear programming model. unit A weighs 4 kgs; each unit of b weighs 10 kgs. How much of each type of raw material
DM should be used for each unit of final product to minimize cost?

DM
Starting at the point of origin as the first corner point, the following are the other corner points as shown
(b) Charot Polar Products makes downhill and crosscountry skis. A pair of downhill skis requires
in the graph above.
2 man-hours for cutting, 1 man-hour for shaping and 3 man-hours for finishing while a pair of
crosscountry skis requires 2 man-hours for cutting, 2 man-hours for shaping and 1 man-hour
Vertex 1: At (0; 0), P = 5(0) + 7(0) = PhP 0:00
for finishing. Each day the company has available 140 man-hours for cutting, 120 man-hours
for shaping and 150 man-hours for finishing. How many pairs of each type of ski should the
Vertex 2: At (50; 0), P = 5(50) + 7(0) = PhP 250:00
company manufacture each day in order to maximize profit if a pair of downhill skis yields a
profit of Php 10 and a pair of cross-country skis yields a profit of Php 8?
Vertex 3: At (50; 14:286), P = 5(50) + 7(14:286) = PhP 350:00

Vertex 4: At (43:871; 21:29), P = 5(43:871) + 7(21:29) = PhP 368:39 (Max)

P

P
Vertex 5: At (0; 52), P = 5(0) + 7(52) = PhP 364:00.
PU

PU
Decision. The RAVLAM Company should produce 43:871 (≈ 44) units of small size abaniko fan and
21:29(≈ 29) units of large size abaniko fan to be able to maximize their profit at Php 368:385 (≈
Php 367:00).

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 73 Lesson 6 74

Let
Lesson 6: Mathematics of Graphs G1 = (V; E1 ) = {(0; 0); (0; 2); (0; 4); (1; 1); (1; 3); (1; 5); (2; 0); (2; 2); (2; 4);
(3; 1); (3; 3); (3; 5); (4; 0); (4; 2); (4; 4); (5; 1); (5; 3); (5; 5)};
Learning Outcomes
G2 = (V; E2 ) = {(0; 1); (0; 2); (0; 3); (0; 4); (0; 5); (1; 0); (1; 2); (1; 3); (1; 4); (1; 5);
At the end of the lesson, the students are able to
(2; 0); (2; 1); (2; 3); (2; 4); (2; 5); (3; 0); (3; 1); (3; 2); (3; 4); (3; 5);
1. Define and illustrate graphs, paths, circuits, trees, complete graphs, connected graphs and (4; 0); (4; 1); (4; 2); (4; 3); (4; 5); (5; 0); (5; 1); (5; 2); (5; 3); (5; 4)}; and
weighted graphs; G3 = (V; E3 ) = {(0; 1); (0; 2); (1; 0); (1; 2); (1; 3); (2; 0); (2; 1); (2; 3); (2; 4);
2. Apply algorithms in finding Euler circuits and Euler paths in connected graphs; (3; 1); (3; 2); (3; 4); (3; 5); (4; 2); (4; 3); (4; 5); (5; 3); (5; 4)}
are examples of graphs. A graph can be represented diagrammatically by letting the vertices illustrated

S
3. Exhibit the Travelling Salesman Problem and apply algorithms in solving it;
as nodes and edges as arcs connecting the nodes. The following diagrams represent graphs G1 ; G2 and
4. Apply the Kruskal’s Algorithm in finding a minimum spanning tree for a weighted graph G3 .
DM

DM
5. Exhibit and solve a graph coloring problem

Overview
Graph Theory is the mathematics that shows how a pair of objects coming from a particular collection
is abstractly related, and ultimately how to face-off all of these pairs so that a concrete problem may be G1 = (V; E1 ) G2 = (V; E2 ) G3 = (V; E3 )
addressed. Moreover, objects that are paired by distance-relation, time-relation, cost-relation, etc., are
Note that in G1 , a vertex is adjacent to itself. Such edges are called loops.
falling under solutions for the respective problems for the shortest way, the fastest time, the cheapest
amount of expenses, etc. Graph Theory, with aid of a friendly geometry and some well-guided algorithms,
P

P
will deal with all of these concerns. Definition 25
Vertices are said to be adjacent if there is an edge that joins them. Edges are said to be adjacent
6.1 Graph Concepts and Models if they share a common vertex. The degree of a vertex is the number of edges at that vertex.
PU

PU
Definition 24
Example 44. The table below summarizes the degree of each vertex of the previously defined graphs
Let V be a non-empty set, and E be any set of ordered pairs over V . The pair (V; E) is called a G1 ; G2 and G3 .
graph. We denote a graph by G = (V; E). V is called the vertex set of G and its elements as
vertices, while E is called the edge set of G and its elements as edges. Vertex G1 G2 G3
0 3 5 2
1 3 5 3
Example 43. Let 2 3 5 4
3 3 5 4
V = {0; 1; 2; 3; 4; 5};
4 3 5 3
E1 = {(x; y ) | x and y are either both odd or both even};
5 3 5 2
E2 = {(x; y ) | x 6= y }; and
E3 = {(x; y ) | 0 < |x − y | ≤ 2}:

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 75 Lesson 6 76

Definition 26 Moreover, we can visualize graphs thru the following models.

Given a graph G = (V; E). A path in G is a sequence of vertices with no repeated edges. A 1. In 1736, the attention of mathematician Leonhard Euler was caught by a simple puzzle: "Is it
circuit in G is a path that starts and ends at the same vertex. possible to walk around and cross all the seven bridges of the old town of Konigsberg exactly
once?"
Example 45. Consider the graph illustrated below.
Source: 2010 Encyclopedia Britannica

S
DM

DM
The following are some paths: The following are not paths: The following are some cir- Four small islands are connected by seven bridges as shown above in the left figure. Its graph
cuits: representation is shown above in the right figure.
• A-B-E-D • A-C-A-D-E
• A-B-C-A 2. Can you continuously trace this figure starting from any vertex such that you can only pass through
• A-B-C-A-D-E • A-B-C-B-A-D
every edge and every vertex once without lifting your pen?
• A-B-C-B-E • A-D-E-E-D • A-D-E-B-A

• A-C-B-E-E-D • A-B-C-B-E-E-D-A-C-B • A-C-B-E-D-A

P

P
Definition 27
A graph G is said to be connected if there is a path joining any two of its vertices. Otherwise,
3. The table below shows the distances of towns Alpra, Betra, Gamra at Deltra from each other, in
it is said to be disconnected.
km.
PU

PU
Example 46. Alpra Betra Gamra Deltra
Alpra * 11 13 14
Betra 11 * 12 13
Gamra 13 12 * 15
Deltra 14 13 15 *

If a courier service personnel aims to drop packages once in each town, what routing schedule can
be made so that he can travel the shortest distance?

This is a connected graph. Any two distinct This is a disconnected graph. 4. Suppose you are tasked to color a blank map of Metro Manila in such a way that no two adjacent
vertices are joined by a path. No path takes A to G. cities will have the same color. What is the least number of colors you can use to complete this
task?

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 77 Lesson 6 78

6.2 Euler’s Theorems and Fleury’s Algorithms

Definition 28
Given a connected graph G. An edge in G is said to be a bridge if G becomes disconnected when
it is deleted. An Euler path is a path that travels through every edge of G. An Euler circuit is
a circuit that travels through every edge of G.

Example 47. Every vertex of G2 has an even degree. By Euler’s Theorem 1 (B), G2 has at least one Euler circuit.

3. Let G3 be the graph shown below.

S
DM

DM
In this graph, paths E-A-B-C-A-D-G-F-D and In this graph, paths A-B-C-A-D-F-G-D-E-A and
E-A-C-B-A-D-G-F-D are Euler paths. D-A-C-B-A-E-D-G-F-D are Euler circuits.
Every vertex of G3 has an odd degree. Thus, Euler’s Theorem 1 (A) says G3 has no Euler circuit.

Theorem 3: Euler’s Theorem 1

Theorem 4: Euler’s Theorem 2
1. If a graph has any vertices of odd degree, then it cannot have an Euler circuit.
1. If a graph has more than two vertices of odd degree, then it cannot have an Euler path.
P

P
2. If a graph is connected and every vertex has an even degree, then it has at least one Euler
circuit. 2. If a graph is connected and has just two vertices of odd degree, then it has at least one Euler
path. Any such path must start at one of the odd-degree vertices and end at the other one.
PU

PU
Example 48.
Example 49. 1. Let G1 be the graph shown below.
1. Let G1 be the graph shown below.

Only vertices D and E have odd degrees. Hence, by Euler’s Theorem 2 (B), G1 has at least one
Vertices D and E have odd degrees. Hence, by Euler’s Theorem 1 (A), G1 has no Euler circuit. Euler path. The path E-A-B-C-A-D-G-F-D is an Euler path.

2. Let G2 be the graph shown below. 2. Let G2 be the graph shown below.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 79 Lesson 6 80

Fleury’s Algorithm for Finding Eulerian Circuit (Don’t cross the bridge until you have to).

1. Make sure that the graph is connected and all vertices have even degree.

2. Start at any vertex.

3. Travel through an edge if:

By Euler’s Theorem 1 (B), G2 has at least one Euler circuit. Thus, it has an Euler path.
(a) it is not a bridge for the untraveled part, or
3. Let G3 be the graph shown below. (b) there is no other alternative.

S
4. Label the edges in the order in which you travel them.

5. When you can’t travel any more, stop.

DM

DM
Example 51. Using Fleury’s Algorithm, find an Euler Circuit in this graph.

Every vertex has an odd degree. Hence, by Euler’s Theorem 2 (A), G3 has no Euler path.

Theorem 5: Euler’s Theorem 3

1. The sum of the degrees of all the vertices of a graph equals twice the number of edges.

2. The number of vertices of odd degree must be even.

P

P
Solution. START: The graph is connected. Every vertex has an even degree.
Example 50. The table below characterizes the previously defined graphs G1 ; G2 and G3 of Example 7
in reference to Euler’s Theorem 3. 1. Choose vertex D, primarily due to having to having the highest degree.
PU

PU
Number of Vertices Number of Vertices Sum of the Degrees Number of 2. None of the edges (D,A), (D,E), (D, F) and (D, G) is a bridge. Hence, you can travel on any of
with Odd Degree with Even Degree of all Vertices Edges these edges. Say, take (D,A).
G1 2 5 16 8
G2 0 7 18 9 3. Label path D-A.
G3 4 0 14 7
4. Omitting (D, A) in the graph, standing on A makes edge (A, E) the only bridge. Then, you can
travel on either (A, B) or (A, C). Say, take (A, C).

Given a connected graph with all vertices have even degrees, we can find an Euler circuit using Fleury’s 5. Label path D-A-C.
Algorithm.
6. Standing on C, (C, B) is a bridge. Since there are no other edges adjacent to C, take (C, B).

7. Label path D-A-C-B.

8. Standing on B, (B, A) is a bridge. Since there are no other edge adjacent to B, take (B, A).

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 81 Lesson 6 82

9. Label path D-A-C-B-A. Example 52. Using Fleury’s Algorithm, find an Euler Path in this graph.

10. Standing on A, (A, E) is a bridge. Since there are no other edges adjacent to A, take (A, E).

11. Label path D-A-C-B-A-E.

12. Standing on E, (E, D) is a bridge. Since there are no other edges adjacent to E, take (E, D).

13. Label path D-A-C-B-A-E-D.

14. Standing on D, neither (D,E) nor (D,G) is a bridge. Take (D, G).
START: The graph is connected. Only D and E are the vertices with odd degrees.

S
15. Label path D-A-C-B-A-E-D-G.

16. Standing on G, (G, F) is a bridge. Since there are no other edges adjacent to F, take (G, F).
DM 1. Choose vertex D, primarily due to having to having the highest degree.

DM
17. Label path D-A-C-B-A-E-D-G-F.
2. Edge (D, A) is a bridge. Its omission makes the graph disconnected. Hence, you can travel on
18. Standing on F, (F, D) is a bridge. Since it is the only remaining edge of the graph adjacent to F, either (D, F) and (D, G). Say, take (D,G).
take (F, D).
3. Label path D-G.
19. Label path D-A-C-B-A-E-D-G-F-D.
4. Omitting (D, G) in the graph, standing on G makes edge (G, F) a bridge, yet the only edge to F.
The path D-A-C-B-A-E-D-G-F-D is an Euler circuit. Then, take (G, F).

5. Label path D-G-F.

Also, given a connected graph with exactly two vertices of odd degrees, we can find an Euler path using
6. Standing on F, (F, D) is a bridge. Since there are no other edges adjacent to F, take (F, D).
P

P
Fleury’s Algorithm.

Fleury’s Algorithm for Finding an Eulerian Path (Don’t cross the bridge until you have to). 7. Label path D-G-F-D.
PU

PU
8. Standing on D, (D, A) is a bridge. Since there are no other edges adjacent to D, take (D, A).
1. Make sure that the graph is connected and only two vertices have odd degree.
9. Label path D-G-F-D-A.
2. Start at any of the two odd-degree vertices.
10. Standing on A, (A, E) is a bridge. Hence, you can travel on either (A, B) or (A, C). Say, take (A,
3. Travel through an edge if: C).
(a) it is not a bridge for the untraveled part, or 11. Label path D-G-F-D-A-C.
(b) there is no other alternative.
12. Standing on C, (C, B) is a bridge. Since there are no other edges adjacent to B, take (C, B).
4. Label the edges in the order in which you travel them.
13. We have now path D-G-F-D-A-C-B.
5. When you can’t travel any more, stop.
14. Standing on B, (B, A) is a bridge. Since there are no other edges adjacent to B, take (B, A).

15. Label path D-G-F-D-A-C-B-A.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 83 Lesson 6 84

16. Standing on A, (A, E) is a bridge. Since it is the only remaining edge of the graph adjacent to F, The path B-E-A-D-C is a Hamilton path.
take (A, E). G3 has no Hamilton circuits.

17. Label path D-G-F-D-A-C-B-A-E.

4. Let G4 be the graph shown below.
The path D-G-F-D-A-C-B-A-E is an Euler Path.

6.3 Hamilton Circuits, Hamilton Paths and the

Traveling-Salesman Problems

S
Definition 29
Given a connected graph G. A Hamilton circuit is a circuit that passes through each vertex
DM

DM
exactly once. A Hamilton path is a path that passes through each vertex exactly once.
G4 has neither Hamilton paths nor Hamilton circuits.

Example 53. 1. Let G1 be the graph shown below.

Definition 30
A graph Kn with n vertices is said to be a complete graph if every vertex is adjacent to the
other (n − 1) vertices.

The path A-B-C-D-E is a Hamilton path. Example 54. The following are examples of complete graphs.
P

P
The path A-B-C-D-E-A is a Hamilton circuit.

2. Let G2 be the graph shown below.

PU

PU
K1 K2 K3 K4

The path A-B-C-G-D-E-F is a Hamilton path. Definition 31

The path A-B-F-E-D-G-C-A is a Hamilton circuit.
A weighted graph is a graph whose edges have assigned numbers. Such numbers are called
3. Let G3 be the graph shown below. weights. Common weights are time, distance and cost. Complete graphs that are weighted are
simply called complete weighted graphs.

Example 55. Consider this complete weighted graph.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 85 Lesson 6 86

Example 56. Using the Brute Force Method in this complete weighted graph,

S
The vertices represent 5 destinations and the weights represent the cost of reaching one destination from
another destination. Starting at any destination, what is the optimal solution so that all destinations
DM

DM
will be reached exactly once and returns to its starting point? This problem is an example of a Traveling
Salesman Problem.

The Travelling Salesman Problem. we obtain all of the following Hamilton circuits starting at A. Note that you can start at any point. Due
to the cyclic nature, you may find a Hamilton circuit starting at any point that is essentially the same
Suppose that a salesman has to visit each of a number of cities exactly once before returning to with one of the following.
his starting point. What is the shortest available route through the cities?

Remarks. Hamilton Circuits Sum of Weights

A-B-C-D-E-A 200 + 310 + 425 + 375 + 240 = 1 550
P

P
1. Given a complete weighted graph, TSP asks for the circuit of minimum total weight in a graph
A-B-D-C-E-A 200 + 510 + 425 + 410 + 240 = 1 785
that visits each vertex exactly once and returns to its starting point.
A-B-C-E-D-A 200 + 310 + 410 + 375 + 390 = 1 685
2. The optimal solution for a TSP is a Hamilton circuit for a complete weighted graph for which the A-D-C-B-E-A 390 + 425 + 310 + 350 + 240 = 1 715
PU

PU
sum of the weights of the edges traversed is the smallest possible number. A-B-E-D-C-A 200 + 350 + 375 + 425 + 415 = 1 765
A-C-B-D-E-A 415 + 310 + 510 + 375 + 240 = 1 850
We have three methods to determine a solution for a TSP: the Brute Force Method, the Nearest Neigh-
A-C-B-E-D-A 415 + 310 + 350 + 375 + 390 = 1 840
bor Method and the Cheapest Link Algorithm.
A-C-D-B-E-A 415 + 425 + 510 + 350 + 240 = 1 940
A-C-E-D-B-A 415 + 410 + 375 + 510 + 200 = 1 910
THE BRUTE FORCE METHOD
A-D-B-C-E-A 390 + 510 + 310 + 410 + 240 = 1 860
1. Draw a complete weighted graph for the problem. A-B-E-C-D-A 200 + 350 + 410 + 425 + 390 = 1 775

2. List all possible Hamilton circuits.

3. Find the sum of the weights of the edges for each circuit.

The circuit with the smallest sum is the optimal solution.

The least cost is 1 550 and belongs to the Hamilton circuit A-B-C-D-E-A.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 87 Lesson 6 88

THE NEAREST NEIGHBOR METHOD (AN APPROXIMATE SOLUTION)

1. Draw a complete weighted graph for the problem.

2. Starting at a designated vertex, pick the edge with the smallest weight and move to the
second vertex.

3. At the next vertex, pick the edge with smallest weight that doesn?t go to a vertex already
used.

4. Continue until the circuit is completed.

S
The sum of the weights is an approximation to the optimal solution.

DM

DM
Example 57. Using the Nearest Neighbor Method, we determine an approximate solution in the given
complete weighted graph,

The Hamilton circuit formed is A-B-C-E-D-A having the cost 1,685. This method promises an approxi-
mate solution since results may vary depending on the starting point.
P

P
THE CHEAPEST LINK ALGORITHM

1. Draw a complete weighted graph for the problem.

PU

PU
2. Pick the edge with the smallest overall weight. In case of a tie, pick at random.
1. Start at vertex A. The edge with the least cost adjacent with A is (A, B). Take (A, B) and stand
at B. 3. Pick the edge with the next smallest overall weight that doesn’t:

2. At vertex B, the edge with the least cost that is adjacent with B is (B, C). Take (B, C) and stand (a) enclose a smaller circuit that doesn’t reach every vertex or
at C.
(b) result in three chosen edges coming from the same vertex.
3. At vertex C, the edge with the least cost that is adjacent with C is (C, A) However, it leads back
4. Repeat Step 2 until the Hamilton circuit is complete.
to A, so, disregard (C, A). The next edge with the least cost is (C, E). Take (C, E) and stand at
E.

4. At vertex E, the edge with the least cost that is not leading back to A, B and C, is edge (E, D).
Take (E, D) and stand at D.
Example 58. Using the Cheapest Link Algorithm, we determine an approximate solution in the given
5. Since all five vertices are accounted, take edge (D, A) to form a Hamilton circuit. complete weighted graph,

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 89 Lesson 6 90

S
1. The edge with the smallest overall weight is (A, B) with weight 200. Pick (A, B).
DM With the five vertices already chosen, we have the Hamilton circuit A-B-C-D-E-A and the optimal cost

DM
2. Among the remaining edges, the edge with the smallest overall weight is (A, E) with weight 240. as 1,550.
Pick (A, E).

3. Among the remaining edges, the edge with the smallest overall weight is (B, C) with weight 310.
6.4 Spanning Trees and Kruskal’s Algorithm
Pick (B, C). Definition 32

4. Among the remaining edges, the edge with the smallest overall weight is (B, E) with weight 350. A tree is a graph in which any two vertices are connected by exactly one path.
But, (B, E) encloses a smaller circuit with (A, B) and (A, E). Reject (B, E).
The following are some properties of trees:
5. Among the remaining edges, the edge with the smallest overall weight is (D, E) with weight 375.
1. A tree has no circuits.
P

P
Since, it doesn’t enclose a smaller circuit or result in three chosen edges coming from the same
vertex, then (D, E) can be picked.
2. Trees are connected graphs.
6. Among the remaining edges, the edge with the smallest overall weight is (A, D) with weight 390.
3. Every edge in a tree is a bridge.
PU

PU
But, (A, D) encloses a smaller circuit with (A, E) and (D, E), and is the third edge adjacent with
A. Thus, reject (A, D). 4. A tree with n vertices has exactly (n − 1) edges.

7. Among the remaining edges, the edge with the smallest overall weight is (C, E) with weight 410. Example 59. The following are examples of trees on 6 vertices.
But, (C, E) encloses a smaller circuit with (A, B), (B, C) and (A, E), and is the third edge adjacent
with E. Thus, reject (A, D).

8. Among the remaining edges, the edge with the smallest overall weight is (A, C) with weight 415.
But, (A, C) encloses a smaller circuit with (A, B) and (B, C), and will be a third edge adjacent
with A. Thus, reject (A, C).

9. Among the remaining edges, the edge with the smallest overall weight is (C, D) with weight 425.
Since, it doesn’t enclose a smaller circuit or result in three chosen edges coming from the same
vertex, then (C, D) can be picked.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 91 Lesson 6 92

Definition 33 4. Among the remaining edges, the edge with the lowest weight that does not form a circuit with
A spanning tree for a connected graph G of n vertices is a connected subgraph that is a tree on (D; E); (D; F ) and (B; C) is (B; F ) with weight 21. Thus, pick (B; F ).
n vertices. 5. Among the remaining edges, the edge with the lowest weight is (C; F ) with weight 24. But, (C; F )
A minimum spanning tree for a weighted graph is the spanning tree for that graph that has forms a circuit with (B; C) and (B; F ). Thus, reject (C; F ).
the smallest possible sum of the weights.
6. Among the remaining edges, the edge with the lowest weight that does not form a circuit with
A spanning tree for a graph is a tree that results from the removal of as many edges as possible from (D; E); (D; F ); (B; C) and (B; F ) is (A; B) with weight 27. Thus, pick (A; B).
the original graph without making it disconnected. To find the underlying minimum spanning tree in a
With the six vertices already chosen, we have the required minimum spanning tree highlighted:
connected graph, one may apply the so-called Kruskal’s algorithm.

S
KRUSKAL’S ALGORITHM
To construct a minimum spanning tree for a weighted graph:
DM

DM
1. Choose the edge with the lowest weight (and highlight it in color). If there is more than
one, pick one at random.

2. Choose the unmarked edge with the next lowest weight that does not form a circuit with
the edges already highlighted, (and highlight it).

3. Repeat until all vertices have been connected.

Example 60. Determine the minimum spanning tree in this weighted graph.
6.5 Graph Coloring
P

P
Definition 34
Graph coloring is a function that assigns either the vertices or edges of a graph by a unique color
(or label). Graph coloring is specified as either vertex coloring or edge coloring depending
PU

PU
whether the vertices or the edges are labelled.

Definition 35
A graph is said to be a planar graph if it can be drawn in a plane without the edges crossing.

Solution. Example 61. The graph

1. The edge with the lowest weight is (D; E) with weight 14. Pick (D; E).

2. Among the remaining edges, the edge with the lowest weight that does not form a circuit with
(D; E) is (D; F ) with weight 18. Thus, pick (D; F ).

3. Among the remaining edges, the edge with the lowest weight that does not form a circuit with
(D; E) and (D; F ) is (B; C) with weight 20. Thus, pick (B; C).

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 93 Lesson 6 94

is a planar graph since it be drawn in a plane without the edges crossing as

VERTEX COLORING ALGORITHM

1. Determine the vertex with the highest degree. Assign to it the first color.

2. Also, assign the first color to all vertices that are not adjacent to the first chosen vertex.

3. Among the remaining vertices, determine the vertex with the highest degree. Assign to it
the second color.

4. Also, assign the second color to all vertices that are neither adjacent to the second chosen
vertex nor to vertices that already received the second color.

S
5. Continue doing Steps 3 and 4 to until all vertices are colored.

DM The number of colors used is the chromatic number.

DM
Example 62. What is the chromatic number of the planar graph representing this map?

Definition 36
Given a graph coloring problem, the smallest number of colors needed to color a graph is called
the chromatic number.
P

P
Observe that graphs representing the adjacency of countries, provinces or cities are planar graphs. The
most famous coloring problem is derived from the idea of coloring maps such that no two adjacent
countries, provinces or cities are of the same color. With the way of this coloring, its chromatic number
PU

PU
can be determined.
The map show above has the its graph adjacency representation as

Theorem 6: The Four Color Theorem

Every possible geographical map can be colored with at most four colors in such a way that no
two adjacent regions have the same color.

Two regions are called adjacent if they share a border segment, not just a point. To determine the
chromatic number for a given geographical map, it should be represented as a graph where a vertex
represents a region, and vertices are adjacent if the region they represent are adjacent in the map.

The following algorithm lets the fulfillment of the Four-Color Theorem.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 95 Lesson 6 96

Applying the Vertex Coloring Algorithm on the graph, we have the following. Assessment
1. The vertex with the highest degree is F with degree 7. Assign to F the first color (to be presented
as red). 1. Let V = {cities of Metro Manila} and E = {(x; y ) | x and y are adjacent cities in Metro Manila}.

2. The vertices A, C, D, L, M, N and O are not adjacent to A. Note that among these vertices, there
(a) Draw the graph G defined by G = (V; E). You may use initials to name a vertex representing
are also adjacent vertices. Choose the vertices strategically such that most of them will receiver
a city.
the first color. Say, choose vertices A, D, L, and N to receive the first color.
(b) Apply the Four-Color Theorem to determine the chromatic number of the vertex coloring for
3. Among the remaining vertices, the vertices with the highest degree with noncolored vertices are B
G.
and I. Choose one of them to receive the second color (to be represented by yellow). Say, B will

S
receive the second color.
2. Apply Euler’s Theorems and Fleury’s Algorithm to determine Euler path and Euler circuits in each
4. The vertices H, I, J, K, M and O are not adjacent to B. Note that among these vertices, there are graph.
DM

DM
also adjacent vertices. Choose the vertices strategically such that most of them will receiver the
second color. Say, choose vertices H, J and M to receive the second color. (a) (b)

5. Among the remaining vertices, the vertex with the highest degree with noncolored vertices is G.
Hence, assign to G the third color (to be represented by green).

6. Vertices E, I and O are not adjacent to G. Also, none of them are adjacent. Thus, E, I and O will
receive the third color.

7. Lastly, vertices C and K are not adjacent. Hence, C and K will receive the fourth color (to be
represented as pink).
P

P
The following are the corresponding colored graphs and maps based on the algorithm.

3. A business man has to visit five cities A, B, C, D and E. The distance (in hundred miles) between
the five cities is as follows:
PU

PU
A B C D E
A * 7 6 8 4
B 7 * 8 5 6
C 6 8 * 9 7
D 8 5 9 * 8
E 4 6 7 8 *

If the businessman starts from city A and has to come back to his starting point, which route
should he select so that the total distance travelled is minimum.

4. Apply Kruskal’s Algorithm to determine a minimum spanning tree in each graph.

All Rights Reserved. 2020 Abdul, Atienza, et. al. All Rights Reserved. 2020 Abdul, Atienza, et. al.
Lesson 6 97

(a) (b)

S
DM
P
PU

All Rights Reserved. 2020 Abdul, Atienza, et. al.

 Final Exam in GEED 10053

Instructions. This is a multiple choice exam. Fully shade the circle corresponding to your answer. If your answer
is not among the choices, shade the circle corresponding to choice E. Avoid erasures and do not put unnecessary
markings on the answer sheet. Turn to the next page for the problems.
Final Exam in GEED 10053 (Mathematics in the Modern World) Page 1

1. Which of the following best describes the true nature of mathematics?

(a) Mathematics consists of doing arithmetic operations and calculations.
(b) Mathematics sheds light to the nature of reality.
(c) Mathematics is the study of patterns and relationships.
(d) Mathematics is the study of the universe.

2. By ignoring the colors, which of the following logos is a cyclic rosette pattern?

(a) (b) (c) (d)

3. If a frieze pattern only admits symmetries generated by one translation, one horizontal reflection, and one glide
reflection, which of the following classifies the pattern using the John B. Conway naming system?
(a) Jump (b) Hop (c) Siddle (d) Step

4. Which of the following equals the 10th Fibonacci number F10 ?

(a) 21 (b) 34 (c) 55 (d) 89

5. Leonardo Da Vinci named this ratio as the “divine proportion”. This ratio can be approximated by taking a
large positive integer n and divide Fn by Fn+1 . What is the name of this ratio?
(a) Holy Ratio (b) Bronze Ratio (c) Silver Ratio (d) Golden Ratio

6. If p and q are given true propositions, which of the following is also true?
(a) p −→ (¬ q) (b) (¬ p) ∨ (¬ q) (c) p ∧ (¬ q) (d) (¬ p) −→ (¬ q)

7. Consider the conditional statement “If a pentagon has less than five sides, then an icosahedron has at least
fifteen faces.” Which of the following gives the contrapositive of the conditional statement?
(a) An icosahedron has at least fifteen faces only if a pentagon has less than five sides.
(b) If an icosahedron has less than fifteen faces, then a pentagon has at least five sides.
(c) If an icosahedron has at least fifteen faces, then a pentagon has less than five sides.
(d) If a pentagon has at least five sides, then an icosahedron has less than fifteen faces.

8. Which of the following collections is well-defined?

(a) the collection of all stars in the universe
(b) the collection of all real numbers whose square is irrational
(c) the collection of all sets
(d) the collection of all mathematicians 12 feet tall

9. Which of the following sets is equivalent to the set A = {4; 5; 6; 7; 8}?

(a) {1; 2; 3; 4} (b) {x | x is prime and 1 < x < 12}
(c) {x ∈ R | 4 ≤ x ≤ 8} (d) {n ∈ N | n < 9}
Final Exam in GEED 10053 (Mathematics in the Modern World) Page 2

10. In a class of 50 students, sixty percent use neither an iPhone nor an iPad. Twenty percent use an iPhone, while
thirty percent use an iPad. How many students in this class are using both an iPhone and an iPad?
(a) 5 (b) 10 (c) 15 (d) 30

11. Which of the following is a type of reasoning where we make conjectures based on observable examples?
(a) inductive reasoning (b) deductive reasoning (c) hyperactive reasoning (d) selective reasoning

12. The conjecture “If n is a positive integer, then n2 + n + 1 is prime” is false. Which of the following values of n
is a counterexample?
(a) n = 3 (b) n = 5 (c) n = 2 (d) n = 4

13. Which of the following illustrates deductive reasoning?

(a) I’m going to be rich someday because everyone in my family who graduates in college got rich and I just
graduated college.
(b) On Christmas day, movie theaters and Chinese restaurants are always open. Therefore, this Christmas, we
can go to a movie and get some Chinese take out food.
(c) My teacher usually give surprise quizzes on Friday. Today is Thursday, so I must review my lessons because
my teacher might give a surprise quiz tomorrow.
(d) Note that 92 = 81, 992 = 9; 801, and 9992 = 998; 001. Therefore, 99992 = 99; 980; 001.

14. Using inductive reasoning, determine which of the following is the sum of

1 1 1 1
+ + + ··· + ?
1·2 2·3 3·4 99 · 100

49 50 99 100
(a) 50
(b) 51
(c) 100
(d) 101

15. A piece of rope is 48 inches long and is cut so that one piece is twice the as long as the other. Which of the
following is the length of the longer piece?
(a) 8 in (b) 16 in (c) 24 in (d) 32 in

16. Which of the following is the type of sampling where every possible subsets of size n from a population of size
N has the same chance of being selected?
(a) purposive sampling (b) simple random sampling
(c) quota sampling (d) non-probability sampling

17. The totality of elements that we are interested to study in a statistical investigation is called the
(a) population (b) sample (c) parameter (d) statistic

18. This level of measure classifies data into categories which can be ranked; however, the precise differences of
these categories may not be clear. Which one is it?
(a) ratio level (b) interval level (c) ordinal level (d) nominal level
Final Exam in GEED 10053 (Mathematics in the Modern World) Page 3

19. Which of the following measures of central tendencies is most appropriate if the data can be measured up to
the nominal level only?
(a) mean (b) median
(c) mode (d) none of the other choices

20. This measure of variability can be calculated by taking the average deviation from the mean. Which one is it?
(a) range (b) variance (c) standard deviation (d) mean
For the next three items, consider the following scenario:
Chaka Furniture Shop located in Cavite makes two kinds of products, cabinets and dressers, which pass through
the assembly and the finishing departments. The Assembly department has 60 hours of work available each
week, while the finishing department has 48 hours each week. Making one cabinet needs 2 hours in Finishing
and 4 hours in Assembly, while it takes 2 hours to assemble a dresser and 4 hours to finish it. If the profit
generated per cabinet is P100 and per dresser is P80.(Hint: Let x be the number of cabinet produce and y be
the number of dresser produce).

21. Which of the following LP model is the best describe from the given problem?

(a) (b) (c) (d)

Max P = 100x + 80y Max P = 100x + 80y Max P = 80x + 100y Max P = 100x + 80y
subject to subject to subject to subject to
2x + 4y ≤ 60 4x + 2y ≤ 60 4x + 2y ≤ 60 4x + 2y ≥ 60
4x + 2y ≤ 48 2x + 4y ≤ 48 2x + 4y ≤ 48 2x + 4y ≥ 48
x; y ≥ 0 x; y ≥ 0 x; y ≥ 0 x; y ≥ 0

22. How many units of cabinet should the company produce to maximize the profit?
(a) 15 (b) 12 (c) 6 (d) 0

23. How many units of dresser should the company produce to maximize the profit?
(a) 12 (b) 9 (c) 6 (d) 0

(0; 8)

(5; 7)
24. Consider the objective function z = 2:5x + 1:5y . Which of the following is the
maximum value of z in the feasible region as shown in the right?
(6; 4)
(a) 7.5 (b) 12
(c) 23 (d) 25

(3; 0)

25. Which of the ff. shaded region will best describe the solution set of the system of inequalities:

(x ≥ 0) ∧ (y ≥ 0) ∧ (2x + y ≤ 4) ∧ (3x + 5y ≤ 15)?

Final Exam in GEED 10053 (Mathematics in the Modern World) Page 4

(a) (b) (c) (d)

26. How many edges are there in a graph with 10 vertices each of degree six?
(a) 10 (b) 20 (c) 30 (d) 40

27. What is the adjacency matrix that will represent the pseudograph as shown?

2 3 2 3 2 3 2 3
0 3 0 2 0 2 0 3 0 3 0 2 2 1 2 0
6 7 6 7 6 7 6 7
63 0 1 17 63 0 1 17 60 1 1 27 63 0 1 17
(a) 6
60
7 (b) 6 7 (c) 6 7 (d) 6 7
4 1 1 27
5
60
4 1 1 27
5
63
4 0 1 175
60
4 1 1 275
2 1 2 0 2 1 2 0 2 1 2 0 0 3 0 2
28. Which of the following graphs has neither a Hamilton circuit nor a Hamilton path?

(a) G1 only. (b) G2 only. (c) G3 only. (d) None of the above.

29. What is the height of the rooted tree shown below?

(a) 0 (b) 2 (c) 4 (d) 6

30. is a circuit that contains every edge of a graph exactly once.

(a) Euler Circuit (b) Euler Path (c) Hamiltonian Circuit (d) Hamiltonian Path