Mathematics in the Modern World

Mathematics as Language Propositional Connectives Propositions and the Truth Table ^ and conjunction v or disjunction Proposition – a complete declarative sentence that is either => implies implication True or False, but not both. <=> if and only if biconditional ¬ not negation Ex. • Manila is the capital of the Philippines Example: • 2+2=5 Let ������ and ������ be the propositions “I’m a Lasallian.” and “I Examples of not a Proposition love Mathematics”, respectively. 1. Is it time already? - Interrogative 2. Pay attention to this. - Imperative 1. p v q 3. x+1=2 - Neither true or false (x has no value) - I’m a Lasallian or I love Mathematics. 4. x+y=z - Neither true or false (x, y, z have no values) 2. ¬ p ^ q p, q, r, etc. - symbols that are typically used in a proposition - I’m not a Lasallian and I love Mathematics. Propositional Connective - an operation that combines two 3. ¬ q propositions to yield a new proposition whose truth value - I don’t love Mathematics depends only on the truth values of the two original propositions. 4. p => q - If I am a Lasallian, then I love Mathematics. Compound Proposition - combinations of propositions using propositional connectives. 5. p <=> q - I am a Lasallian if and only if I love Mathematics. Compound Propositions: • Conjunction Truth Table o p and q p q p ^ q p v q p=>q p<=>q ¬p ¬q • Disjunction o p or q T TT T T T FF • Negation o not p T FF T F F FT • Conditional o If p, then q (or p implies q) F TF T T F TF Ex. If a polygon is a rectangle, then FfF F T T TT the polygon has 4 sides. (TRUE) If a polygon has 4 sides, then the Determine the Truth Value of the compound statement polygon is a rectangle. (FALSE) given that p is a false statement, q is a true statement, and If a polygon is a triangle, then the r is a true statement. polygon has 3 sides. (TRUE) If a polygon has 3 sides, then the 1. p v (¬ q v r) polygon is a triangle. (TRUE) 2. r ^ ¬ (p v r) • Biconditional 3. (p ^ q) v (¬ p ^ ¬ q) o p if and only if q 4. (p ^ q) v [(¬ p ^ ¬ q) v q] 5. [¬ (p ^ ¬ q) v r] ^ (p ^ ¬ r) Ex. A polygon is a triangle if and A compound proposition that is: only if the polygon has 3 sides. • Always TRUE – Tautology (TRUE) • Always FALSE – Contradiction • Sometimes TRUE - Contingency

Argument Validity Deductive Reasoning – is the process of reasoning from one or more statements (premises) to reach a logical Logically Equivalent – two propositions p and q are logically conclusion. (top-down logic) equivalent if have the same truth value (column). Ex: Show that ¬ (p v q) and ¬p ^ ¬q A. All men are mortal. Some logical equivalences Socrates is a man. Therefore, Socrates is mortal The above is an example of syllogism. Syllogism – an argument composed of one or more statements/ premises or “givens”, followed by a conclusion. - for any given set of premises, if the conclusion is guaranteed, the arguments is said to be valid. - If the conclusion is not guaranteed (at least one instance in which the conclusion does not follow), the argument is said to be invalid. Some rules of inference Conditional Statement p -> q p = hypothesis/ antecedent q = conclusion/ consequent Converse q -> p Ex: Anna is a human resource management major. Inverse ¬p -> ¬q 1. Therefore, Anna is either a human resource Contrapositive ¬q -> ¬p 2. management major or a computer applications major. Addition Ex: If you have a current network password, then you A. If a quadrilateral is a rectangle, then it has two can log on to the network. You have a current pairs of parallel sides. network password. Therefore, you can log on to a. Converse: If a quadrilateral has two pairs the network. Modus Ponens of parallel sides, then it is a rectangle. b. Inverse: If a quadrilateral is not a 3. If you have a current network password, then you rectangle, then it does not have two pairs can log on to the network. You can’t log on to the of parallel sides. network. Therefore, you don’t have a current c. Contrapositive: If a quadrilateral does not network password. Modus Tollens have two parallel sides, then it is not a rectangle. (Logically equivalent) 4. If I go swimming, then I will stay in the sun for an hour. If I stay in the sun for an hour, then I will get Therefore, an implication is always logically equivalent to sunburn. Therefore, if I go swimming, then I will its own contrapositive. get sunburn. Hypothetical Syllogism When is a mathematical reasoning valid? Inductive Reasoning – involves going from a series of specific cases to a general statement. The conclusion in an inductive argument is never guaranteed. (bottom-up logic) Ex: A. What is the next number in the sequence 6, 13, 20, 27,…? B. every object I release falls to the ground. Therefore, the next object I release will fall to the ground.

Invalid: Formal Proof of Validity Fallacy of Converse p -> q Ex: q If Spock is emotional, then he is like Doctor --------------- McCoy. Therefore, p On the other hand, if Spock is logical, then he Fallacy of Inverse has a predominant Vulcan personality. p -> q Either Spock is emotional or logical. ¬p Everyone knows that Spock is not like Doctor ---------------- McCoy. Therefore, ¬ q Hence, Spock has a predominant Vulcan False Chain Pattern personality. p -> q p -> r E: Spock is emotional. ---------------- M: Spock is like Doctor McCoy. Therefore, q -> r L: Spock is logical. V: Spock has a predominant Vulcan personality. (1) E -> M (2) L -> V (3) E v L (4) ¬ M _______________ Therefore, V

Mathematics for Number of interest periods per year Personal Finance • Annual – 1 • Semi-Annual – 2 Simple Interest • Quarter – 4 • Month – 12 - is where the amount of interest earned is fixed over time. • Week – 52 I = Prt • Day – 365 I = Interest P = Principal Ex: r = rate of interest per anum (decimal) A. If 10,000 pesos is invested at rate of 95 per year t = time in years compounded quarterly, find the amount of investment after 5 years, 10 years, and 15 years. The final amount or future value A in your account after t Solution: years is a. t = 5 years A = P + I = P (1 + rt) A = P ( 1 + r/n)nt A = 10,000 (1 + 0.09/4)(4)(5) Ex: If you put Php 280,000 in a savings account which A = Php 15, 605.09 A. gives you 0.75% simple interest and you leave that I = Php 5,605.09 amount for an entire year, at the end of the year you will have earned b. t = 10 years A = P ( 1 + r/n)nt Solution: A = 10,000 (1 + 0.09/4)(4)(10) I = Prt A = Php 24,351.89 = (280,000) (0.0075) (1) = Php 2,100 I = Php 14, 351.89 In your account, you will have a total of c. t = 15 years A = P ( 1 + r/n)nt Solution: A = 10,000 (1 + 0.09/4)(4)(15) A=P+I A = Php 38, 001.35 = 280,000 + 2,100 = Php 282, 100 I = Php 28, 001.35 B. If you put Php 280,000 in a savings account which B. An amount of Php 25,000 is placed in a time gives you 0.75% simple interest and you withdraw deposit account that pays an annual rate of the amount after 90 days, the interest up to that 5.15%. If no withdrawals or additional deposits point is are made, how much will there be in the account after three and a half years if interest is Solution: compounded: I = Prt a. Yearly = (280,000) (0.0075) (90/365) = Php 517.81 = 25,000 ( 1 + 0.0515/1)1(3.5) = 29, 803.86 b. Semi-annually = 25,000 ( 2 + 0.0515/1)2(3.5) = 29, 869.69 c. Quarterly = 25,000 ( 4 + 0.0515/1)4(3.5) = 29, 903. 49 Compound Interest Formula: A = P (1 + r/n) nt A = Amount P = Principal r = Interest Rate (decimal) n = Number of times interest is compounded per year t = Time (Years) Time Deposit - is a bank product wherein you money will be kept by the bank for a fixed period of time (30 days, 60 days, 90 days or more) in exchange for an interest rate higher than savings account.

Investing in the Philippines • Choose and Buy Stocks o start with the blue-chip companies/ top Investing in the Philippine Stock Market performing companies. Stocks – also called shares or equities are just portions of a o 3-5 stocks for beginners. company. Investing in bonds 2 Types of Stocks • Common – you get voting rights Bonds (utang/ loan) • Preferred - you get preference for the dividends/ - They are issued by governments and corporations when priority when it comes to dividends. they want to raise money. - By buying a bond, you are giving the issuer a loan. In other Why companies sell their stocks? words, the government or a company owes you money. • Raise funds/capital to - They agree to pay you back the face value of the loan on o Acquire assets a specific date, and to pay you periodic interest payments o Expand along the way (twice or four times a year). o Research and development o Etc. Retail Treasury Bonds = Gov’t Bonds - a form of debt Stock Exchange – facilitates the stock market. - it’s the government borrowing money from the people Stock Market – serves as a market for all of the companies - usually for the infrastructure projects, education projects, who want to share their shares and their stocks to the social welfare, poverty, health, etc. public. - some are transferrable - one of the riskier forms of investments. - higher risks, higher rewards. RTB24 - Philippine Stock Exchange - 24th treasury bond ever issued by the government - aka progreso bonds 2 ways you can earn from the stock market: - intended to raise funds for the government to use in 1. Dividends helping the country bounce back from the corona virus - when companies ear and they decide to give a impact. portion of their earnings to the investors. - people who bought their stocks. 4 ways to invest: - Can be done quarterly or annually • Over the counter (with the selling agent) - In the form of: • Website Order o Cash • Bonds.ph o More shares o Pioneering the digital distribution of the o Products retail treasury bonds. • Secondary bond market 2. Capital gains - when you bought 10 shares of a company at 100 Investing in Mutual Funds pesos, total of 1000 pesos. Over time, the price of the 10 shares became 110 pesos, now the value is Mutual Fund 1,100 pesos. The 100 pesos you earned is called - is a type of financial vehicle made up of a pool of money capital gains. collected from many investors to invest in securities like stocks, bonds, money market instruments, and other How and Why prices fluctuate/ change? assets. • News and public opinion - Mutual funds are operated by professional money • Company’s earnings and operations managers, who allocate the fund's assets and attempt to o value of the company ^ = stock price ^ produce capital gains or income for the fund's investors. o more people buy = price stock ^ - A mutual fund's portfolio is structured and maintained to o more people sell = price stock v match the investment objectives stated in its prospectus. - issued by individual companies Buyers – bid at the price that they’re willing to pay for. Sellers – ask for a price they want for the stocks that may Unit Investment Trust Funds (UITF) currently have. - issued by banks How you can trade: How you make money? • Broker – middle man between company and - each mutual fund has an average share price or an investors. average price per unit o Broker-assisted – from a traditional - Mutual fund – Net Asset Value Per Share (NAVPS) brokerage - UITFs – Net Asset Value Per Unit (NAVPU) o Online brokerage account - NAVPS and NAVPU are calculated on a daily basis NAVPS = ������������������������������ ������������������������������������−������������������������������ ������������������������������������������������������������������ ������������������������������������ ������������ ������ℎ������������������������ ������������������������������������������������������������������

Pros of Mutual Funds: Investing in REITs • It has a low barrier to entry. Most mutual funds require for as low as Php1,000 or Php5,000. The What are REITs? minimum incremental top-up is Php500. - Real estate is a very profitable investment, but many • Diversification. When you are investing in mutual middle-class Filipinos shy away from it because they can’t funds, your money is immediately diversified afford the high purchase price and the recurring costs of across many different investments. property ownership. • Less management on your part. Less pressure to - Enter the real estate investment trusts (REITs)— the monitor your investments since these are pooled emerging alternative for small investors who want to make funds that have fund managers. money in real estate. • Mutual funds aren’t taxed. - REITs offer an easier, more accessible, and more affordable way to earn from large-scale, profitable Cons of Mutual Funds: properties without having to pay for their full cost. • Lack of control. Fund managers do the decision - Modeled after mutual funds, REITs pool the capital of making for you. numerous investors. This makes it possible for individual • There are fees. Even though they aren’t taxed, investors to earn dividends from real estate investments— there are a couple of fees associated with these without having to buy, manage, or finance any properties funds. themselves. o Sales Load Fees Why should I invest in REITS? o Exit/ Redemption Fees o Management Fees • 90% of rental income given to investors as cash • Cut-off period for placing orders. dividends. • You won’t know the price of the NAVPU or NAVPS. NAVPU/S is released at the end of the trading day. • You don’t have to have a lot of money to buy a • T + 1-4 Banking days for redemption. REIT. Exchange Traded Funds (ETF) • REITs are diversified. - traded on the stock exchange. - you can buy and sell it freely in the stock exchange. How do REITs grow? • REIT uses funds from the IPO to buy more Types of Funds: properties. 1. Index Funds • When the prices of properties go up, the value of - a fund that tracks an index. REITs go up. 2. Equity Funds - Invest in individual companies. Benefits of REITs: - Actively managed funds. • Professionally managed. 3. Bond Funds • Affordable - mutual fund that invests in bonds. • Diversified 4. Balanced Funds • Liquid - composed of equities and bonds. 5. Money Market Funds How to buy REITs? - low risk investments. Short-term investments 1. Subscribe to the IPO to buy the shares of REITs. 6. Feeder Funds 2. After IPO, you can buy REITs like stocks through - feeded into another fund. your COL account. Fund performance is influenced by many different factors. What are the risks of REITs? • If a property has fewer tenants, dividends will go How to invest in mutual funds? down. • Banks • REITs are traded like stocks, so its price can go up • Investment Companies and down. • Some stockbrokers • Seedbox.ph Note: 1. Know the outlook of the industry. 2. Check the quality of the assets.

Mathematics for Communicating Efficiently Coding Theory - The study of coding theory is based on the human need to communicate efficiently. -The goal of the coding theory is to detect error in the message sent, if there are any, and correct these errors. - field of study that deals with the design of error-correcting codes for the reliable transmission of information across noisy channels. Communication model Data – usually transferred in the form of a series of 0s and Codeword – is a string of 0’s and 1’s representing an actual 1s. message. Error-correction codes Ex: Ex: Stop -> 000 • Hamming codes Go -> 101 • Shannon’s paper on information theory. Wait -> 110 • Reed-Solomon codes 000, 101, 110 are codewords. • Turbo codes 100, 111, 001, 011 are NOT codewords. (meaningless to • Shor codes (quantum) both sender and receiver) Length of a codeword – the number of binary digits it has. Source coding – is changing the message source, such as a Code – The collection or set of all codewords. data terminal or the human voice, to a suitable code for Ex: transmission through channel. The code is C = {000, 101, 110}. Encode – message becomes a codeword. Source encoder - transforms the source output into a Decode – received codeword is reverted back to a message. sequence of symbols which we call a “message”. Parity Check - the one responsible for the transformation of the source - The simplest form of error detection (without error- message. correction capability) is parity, where a single bit is appended to a bit string. Example of source coding: - single error detection only. • ASCII code (American Standard Code for A bit string has odd parity if the number of 1s in the string Information Interchange) is odd. - is a character encoding standard for electronic Ex: 101011001 – five 1s communication. If the number of 1s is even, then an error will be - represent texts in computers, detected. telecommunications equipment, and other - given more preference because if there were a short devices. circuit, the receiving end would receive binary word of all 0s. 1s = even, then no error would be detected. A bit string has even parity if the number of 1s in the string is even. Ex. 10101100 – four 1s If the number of 1s is odd, then an error will be detected.

Parity Bit: Extra Bit If no error is made during transmission, the receiver gets Repetition Codes and Majority Decoding 000 111 111 000 111 000 000 Repetition Code - simplest possible error correcting code. Now assume that the receiver gets For instance, if we wanted to send the message 1010, we 000 111 110 000 111 000 010 could repeat each letter a certain number of times and send, say r = 3 times and we obtain, The original binary digit is (likely) the one appearing more 111 000 111 000 frequently in the block. Ex: Received word y 1. Encode the bit string 011001 by repeating each bit y = 000 111 110 000 111 000 010 twice. Solution: Use the majority rule to decode 00 11 11 00 00 11 D(y) = 000 111 111 000 111 000 2. Encode the bit string 011 by repeating each thrice. Cons: Solution: 1. This kind of decoding is not perfect because there 000 111 111 may be two errors in one block. 2. Expensive when it comes to memory. Repetition Code - Messages having k bits can be encoded by repeating each Hamming distance between two codes bit r times. - When we repeat each bit r times, this creates a codeword The Hamming distance between two code words is the of length n = kr. number of differences between corresponding bits. - The corresponding code is called repetition code of type [n, k]. If x and y are two bits (binary strings) then their hamming Ex: distance is denoted by d(x, y). Ex: • Encode 011010 using [n, k] = [18, 6] repetition code. • What is d(0010, 1100)? Solution: Solution: n = 18, k = 6 -> r = n/k r = 18/6 = 3 0010 1100 Answer: 000 111 111 000 111 000 3 different corresponding bits • Encode the message 101 with the [12, 3] repetition code. Answer: Hamming distance = 3 • What is d(101011, 111111)? Solution: n = 12, k = 3 -> r = n/k r = 12/3 = 4 Solution: 101011 Answer: 1111 0000 1111 111111 • Enumerate all the codewords of the repetition code of type [4, 2]. 2 different corresponding bits Solution: n = 4, k = 2 -> r = n/k Answer: Hamming distance = 2 r = 4/2 = 2 Nearest Neighbor Decoding 00 01 10 11 • Suppose that when a codeword x from a code C is Answer: 0000 0011 1100 1111 sent, the bit string y is received. Majority Decoding • If the transmission was error-free, then y would be - even if a number of digits got garbled in transmission, the the same as x. But if there are transmission errors, original message may be recovered from any message by then y would not be the same as x. How can we identifying the one which appears most frequently in a correct errors? That is, how can we recover x? block. Consider a code where each bit is repeated 3 times. One approach would be to compute the Hamming distance Suppose we want to transmit the following bit string: between y and each of the codewords in C. 0110100. Then, to decode y, we take the codeword of minimum Hamming distance from y, if such a codeword is unique. If the distance between the closest codewords in C is large enough and if sufficiently few errors were made in transmission, this codeword should be x. This type of decoding is called nearest neighbor decoding.

Ex: Cryptography Given the code C = {0000 0000, 0000 1111, 1111 1111}, Cryptography is used to protect transactions between decode the received word computers as well as secured data. Individuals also use cryptography to secure their documents, e-mail messages, y= 1111 1010 and credit card details. Objectives of Encryption We find the Hamming distance between the received word y and each codeword x in C. 1. Confidentiality 2. Integrity d(0000 0000,y) = 6 3. Authenticity d(0000 1111, y) = 6 4. Non-Repudiation d(1111 1111, y) = 2 Pigpen Cipher • The PIGPEN CIPHER is another example of a By using the nearest neighbor decoding principle, we obtain substitution cipher in which the letters are replaced by symbols. D(y) = 1111 1111 • Although its true origins are unknown, it has been used by many groups. Most notoriously, it was the since this codeword is the nearest word to the received cipher of choice for use by the Freemasons, a word or has the smallest hamming distance. secret society in the 18th Century. • In fact, they used it so much, that it is often The Nearest Neighbor decoding is not viable when there referred to as the Freemasons Cipher. are two minimum hamming distance. • However, it was not exclusively used by them, with Union prisoners in Confederate camps using it to Minimum distance of a code communicate in the American Civil War. Minimum distance of a code – is the smallest Hamming Caesar’s Cipher distance between any two distinct codewords in the code. - shift cipher, shift each letter places to the left. - Key of 3 Ex: - If he had anything confidential to say, he wrote it in cipher, Given C = {111, 110, 011}, we have that is, by so changing the order of the letters of the d(111, 110) = 1 alphabet, that not a word could be made out. If anyone d(111, 011) = 1 wishes to decipher these, and get at their meaning, he must d(110, 011) = 2 substitute the fourth letter of the alphabet, namely D, for A, and so with the others. Therefore, the minimum distance of C is d(C) = 1. Detection and Correction Capability of a Code Let C be a set of codewords and let 2e + 1 be its minimum Hamming distance. Then It is possible to detect up to 2e errors. It is possible to correct up to e errors. Minimum Error Detection/Correction Distance 1 No detection possible 2 1 – error detecting 3 2 – error detecting 1 – error correcting 4 3 – error detecting 1 – error correcting 5 4 – error detecting 2 – error correcting Ex: minimum distance = 4 Solution: 2e+1 = 4 2e = 3 -> error detecting e = 1.5 or 1 (round down) -> error correcting

Vigenère Cipher Ex: • The Vigenère encryption was the creation of the French Decryption of Vigenère by subtracting letters diplomat, Blaise de Vigenère, • To decrypt, take the first letter of the ciphertext 1523-1596. and the first letter of the key, and subtract their • He viewed the cipher as a value (letters have a value equals to their position substitution cipher where a in the alphabet starting from 0). different alphabet was used for • If the result is negative, add 26 (26=the number of the next letter of the message, letters in the alphabet), the result gives the rank of with the alphabets repeating the plain letter. periodically – according to some key. Ex: Modular Arithmetic When we divide two integers, we will have an equation that looks like the following: • Sometimes, we are only interested in what the Symmetric Encryption remainder is when we divide A by B. - also called secret key encryption - the key which is used to encrypt a plain text is the same • For these cases, there is an operator called the key for decrypting a cipher text. modulo operator (abbreviated as mod). Asymmetric Encryption - also called public key encryption • Using the same A, B, Q, and R as above, we would - to decrypt a cipher text, another key which is not the same have: A mod B = R as the encryption key is needed. - only available to the recipient. Ex. -introduced by W. Diffie and M. Hellman in 1976 In a public key cryptosystem, the sender encrypts the data Vigenère Ciphering by adding letters using the public key of the receiver and uses an encryption • To cipher a text, take the first letter of the message algorithm that is also decided by the receiver and the and the first letter of the key, add their value receiver sends only the encryption algorithm and public (Letters have a value depending on their rank in key. the alphabet, starting with 0). But by using the public key, data can only be encrypted but • The result of the addition modulo 26 (26=the not decrypted, and the data is only decrypted by the number of letter in the alphabet) gives the rank of private key that the receiver has. So, no one easily can hack the ciphered letter. the message.

RSA Cryptosystem RSA Encryption Process 1. Translate the message into a sequence of integers. RSA System 2. Group the integers together to form large - example of public cryptography numbers, each representing a block of letters. - Ron Rivest, Adi Shamir, and Leonard Adleman 3. Transform the message M to be encrypted version - The security of RSA encryption rests on the fact that C using there’s no fast way to identify the prime factors of very large numbers. If you’re not the intended recipient of a Ex: message – and if you therefore lack the right key to decode A. Goal: Send the message STOP it – you could search for a thousand years Step 1: Translate the message into a sequence of with the best computers and still not find the right prime integers factors. ABCDEF…YZ -> 00 01 02 … 25. Mathematics of RSA Step 2: Group the integers together to form even - A user starts with a message and performs arithmetic on larger integers, each representing a block of it that involves multiplication by a very large number letters. (hundreds of digits long). The only way to decode the STOP -> 18 19 14 15 -> 1819 1415 message is to find the prime factors of the resulting Step 3: Encrypt 1819 and 1415 as follows: product. M1 = 1819, M2 = 1415 C (M1) = C (1819) RSA Key Generation = 181913 (mod 2537) (use wolframalpha) Public Key: (n, e) = 2081 Private Key: (n, d) C (M1) = C (1415) = 141513 (mod 2537) (use wolframalpha) The value of n in the public key is the same as the value of n in the = 2182 private key. Therefore, the message STOP is equivalent to the ciphertext 2081 2182. Steps: Take two large prime numbers p and q, and 1. compute n = pq. RSA Decryption Process 2. Choose a number e less than n and does not have to retrieve the original message M, decrypt the message C 3. a common factor with (p-1) (q-1). using Find another number d such that ed – 1 is divisible by (p-1) (q-1). A formula for d is for some integer k. Cd mod n Decryption function M (C) = Ex: Ex: A. Let p = 43 and q = 59. Then n = pq = 2537. A. Goal: Decrypt “2081 2182” will perform the 1. Public key: (2537, e) following decryption: Private key: (2537, d) C1 = 2081, C2 = 2182 2. (p-1) (q-1) M(C1) = M (2081) (42) (58) = 2436 = 2081937 (mod 2537) (use wolframalpha) Choose e = 13 = 1819 This is both less than 2537 and does not have M(C2) = M (2182) a common factor with (p-1) (q-1) = (42) (58) = = 2182937 (mod 2537) (use wolframalpha) 2436 = 1415 3. 1 + k (2436) / 13 (Trial and error) The receiver will conclude that 2081 2182 is 1819 1415 or ST OP or STOP. d should be a whole number k=5 d = 937 Answer: Public key: (2537, 13) Private key: (2537, 937)

Mathematics in costs Php20 million but captures Php30 million inComp 1 Decision Sciences revenues from the competitor provided that the competitor does not advertise. Construct the Game normal form of this game. - a situation in which players make strategic decisions that AComp 2 N take into account each other’s actions and responses. A (30, 30) (60, 20) N (20, 60) (50, 50) Game Theory 50-20+30 50-30 - is the study of strategic decision-making where situations Simultaneous vs Sequential are called games and the participants are called players. - the study of how people, companies, or even nations • Simultaneous – Each player has only one move and determine strategies under different situations in the face all these moves are done simultaneously. (rock, of competing moves or strategies acted out by other paper, scissors) players. It deals with problems in which a player’s strategy depends on what the other players do. • Sequential – No two players move at the same time and players may have several actions Prisoner’s Dilemma (moves). (tic-tac-toe) - is a paradox in decision analysis in which two individuals acting in their own self-interests do not produce the Analyzing Simultaneous Games in Normal Form optimal outcome. • Games in normal form are used to analyze - The typical prisoner’s dilemma is set up in such a way that simultaneous games. both parties choose to protect themselves at the expense • Solutions: of the other participant. o Maximin Solution - As a result, both participants find themselves in a worse o Nash Equilibrium state than if they had cooperated with each other in the o Dominant Strategy decision-making process. Maximin Solution Some applications: • Safety first • Business competing in a market • This solution involves choosing the strategy that • Diplomats negotiating a treat gives you the maximum among your worst payoffs. • Gamblers betting in a card game • This was proposed by the mathematician John von • Auctions (a la eBay) Neumann • Trade transactions in basketball • Evolutionary biology Ex: A. Working on a project game: you and your Normal Form classmate work together on a course requirement - A game in normal form is a table of numbers with the and each of you can choose to either work hard strategies listed along the margins of the table and the (W) or take it easy (T). You both want to pass but payoffs for the participants in the cells of the table. both of you do not like working very hard. Assume that the two of you would meet tomorrow to o Strategy – a rule or plan of action for playing a combine your outputs. Determine your and your game. classmate’s maximin energy. o Payoff – the outcome of a game that depends on The payoff matrix is shown below, and the payoff values the selected strategies of the players. represent “comfort/ease” levels. - the value associated with a possible outcome of a game. Maximin solution: (T, T) Ex: A. Game: Rock, paper scissors. Payoff: Tie = 0, Win = 1, Lose = -1 PLAYER 1 ROCK Player 2 SCISSORS PAPER (1, -1) SCISSORS ROCK PAPER (-1, 1) (0, 0) (-1, 1) (0, 0) (1, -1) (0, 0) (-1, 1) (1, -1) B. Two companies share a market where they make Php50 million each. They need to decide whether they will advertise (“A”) or not (“N”). Advertising

Other Examples: Maximin Strategy 2. Determine the best response of the row player to every strategy of the column player. To do this, 1. For the working on the project game, the maximin underline the highest payoff value among the solution is (Take it easy, Take it easy). This solution second coordinates of the ordered pairs in each leads to the payoff pair (1, 1). row. If there are ties, underline all. 3. If there are ordered pairs with both coordinates 2. Suppose Alice knows that Bob will play his maximin underlined, then the game has a Nash Equilibrium. strategy. What is the rational thing that Alice Nash Equilibrium: (T, T) should do? A Nash Equilibrium is a state where no one person can improve, given what others are doing. • Maximin strategy of Alice: B A Nash Equilibrium is a set of “no regrets” strategies. Given o 1 and 2 are the worst payoffs what the other players chose, you have no regrets for your o Choose the best between 1 & 2 choice. • Maximin strategy of Bob: D • Nash Equilibria – 2 solutions o 2 and 3 are the worst payoffs Dominant Strategy o Choose the best between 2 & 3 • Any strategy that always does better than any Maximin Equilibrium: (B, D) other strategy Nash Equilibrium • Hence, a rational player should always choose this strategy. You can rely on a rational rival always • This solution concept was named after John Forbes playing a dominant strategy. Nash, Jr. His theories are used in economics, and in fact he won the Nobel Prize for Economic Sciences Ex: in 1994. Dominant Strategy of Kiko: B • A Nash equilibrium is a strategy for each player Dominant Strategy of April: F such that every players’ action is the best response Dominant Strategy Equilibrium: (B, F) to the other players’ actions. Review: • Each player is using his best response in the game. Maximin Solution: (Advertise, Advertise) So, switching into another strategy would result Nash Equilibrium: (Advertise, Advertise) & (No advertise, into a lower payoff. No advertise) Dominant Strategy Equilibrium: None • In other words, no player can reach a better payoff by changing strategies. Steps to determine Nash Equilibrium: 1. Determine the best response of the row player to every strategy of the column player. To do this, underline the highest payoff value among the first coordinates of the ordered pairs in each column. If there are ties, underline all.

Sequential Game Backward Induction • Simplification of a sequential game In game theory, a sequential game involves multiple • Eliminate actions at the final node and work one’s players who do not make decisions simultaneously. way forward Instead, one player chooses their action before the others • Choose those actions that would not maximize an choose theirs. Importantly, the later players must have individual’s profit at that point some information of the first player's choice so that one • A rational player always tries to maximize their player's decision affects the outcomes and decisions of own profits other players. o You can rely on a rational rival never choosing these actions A sequential game is represented by a game tree (also called the extensive form) with players moving • The best solution for Hershey’s is to accepts the sequentially. deal if offered a deal. Therefore, eliminate the “no product placement” part. Ex: The “Chocolate Wars” Game Setting • Mars should sign the deal. • Universal Studio charges $1.0mn for a product Price setting placement • Product placement by Mars o Mars’ gross profits increase by $0.8mn -1 = -1 o Hershey’s decrease by $0.1mn • Product placement by Hershey o Hershey’s gross profits increase by $1.2mn -1 = 2 o Mars decrease by $0.5mn • No product placement: “business as usual” Game Tree (I/II) • First decision starts the game’. • Every decision point represents a node. • From there, the decisions of the subsequent players branch out accordingly. Strategy (I/II) Both firms will charge a low price. • (Extended) Working definition for this course: Two more examples to illustrate backward induction in o A player’s plan of actions in a game, given solving a sequential game in extensive form: any possible circumstance. Ex. Price Setting Potential strategies for B • high if high • high if low • high if high • low if low

Backward Induction Analyzing Sequential Games in Extensive Form - A subgame includes a decision point and all other parts of the diagram emanating from it. Backward Induction • Step 1: Solve the subgames at the last stage in each branch to reduce the game into a smaller one. • Step 2: We repeat until all subgames have been solved. • Step 3: The resulting tree diagram gives the equilibrium solution. Ex:

Mathematics in Ex: Decision Sciences (Social Choices) Majority Rule Method Social Choice Theory • tackles processes by which different and • Majority Rule - In this method, the candidate who conflicting choices of members of a group are receives majority (more than 50%) of the first- consolidated into a single choice of the group. place votes wins the election. The basic question of social choice theory is on how groups Plurality Method can best arrive at decisions. Is the choice the least unpopular, broadly acceptable, winning in all one-for-one • In this method, whoever receives the most first- contests, etc.? place votes is declared the winner. This is, by far, A related social choice problem is the selection of a good the most simple and widely-used voting method voting system. Voting is the main vehicle by which decisions (though it may require a tie-breaker). are arrived at in a democratic society. It lies at the very heart of representative government and participatory • Voting systems which make use of the plurality democracy. Any voting system must produce at least one method include barangay, local, and national winner to be considered legitimate. elections in the Philippines. However, voters simply choose candidates without ranking them. Axiomatic approach • Fairness criteria Plurality versus majority: • Obtain conclusions representing new knowledge about the process of voting based on those • Plurality winner = candidate with the most first axioms/ criteria. place votes Preference tables • Majority winner = candidate with more than half We begin by discussing some terminologies related to of the first place votes voting. • A preference ballot is a ballot on which each voter ranks all eligible candidates, from first to last place, with no tied ranks. o Ranks the choices in order of preference. • A preference table or schedule is a table showing how many times each possible ballot was submitted. o Ballots are combined into one preference schedule/ table, which shows the number of voters in the top row that voted for each option. o • A voting method is a mathematical procedure that uses data from preference table to determine a winner. Introduction to voting: Creating a Preference Table Voting Theory - Sometime voting is more involve that just electing whoever gets the most votes. There are several methods to determine the winner. A certain method for selecting a winner may be more appropriate based upon the type of election. For example, the method of electing the President fairly might be different than a group of friends deciding on what movie to watch.

• Plurality = the most votes If an election is held, and if there is a majority candidate, • Majority = most of the votes but the majority candidate does not win the election, then the election result violates the Majority Criterion. Fairness Criteria - axiomatic approach. Caution: Sometimes, there is no majority candidate in an election, then the majority criterion has nothing to say By axiomatic approach, we begin with axioms or self- about who should or should not win. Thus, no matter which evident truths that govern the universe of (mathematical) candidate wins such an election, there is no violation of the objects. This approach is seen in your high school Majority Criterion. geometry. Recall that plane geometry is based on five Another viewpoint: In any election there are three postulates/axioms of Euclid. These basic 'truths' govern the possibilities: creation and extension of geometric ideas. 1. There is a majority candidate who is also the 1. A straight line segment may be drawn from any winner of the election. This is good news from the given point to any other. point of view of the Majority Criterion, because there is a “right” candidate, and the right 2. A straight line may be extended to any finite candidate wins. length. 2. There is a majority candidate, who is not a winner 3. A circle may be described with any given point as of the election. This can actually happen, and when its center and any distance as its radius. it happens it is very bad news from the point of view of the Majority Criterion, because there is a 4. All right angles are congruent. “right” candidate while the rest are “wrong”, and 5. If a straight line intersects two other straight lines, a wrong candidate wins. and so makes the two interior angles on one side 3. There is no majority candidate. In this case, the of it together less than two right angles, then the Majority Criterion has nothing to say about who other straight lines will meet at a point if extended should win, since there is no “right” candidate in far enough on the side on which the angles are less this situation. than two right angles. In voting, the axioms that we specify are precise statements Important idea: From the point of view of the Majority that express our expectation of what should or should not Criterion, only case 2 is an instance of unfairness. occur in a fair election. We refer to these axioms as called Remark: Here, we can apply what we learn in Logic. The fairness criteria. majority criterion is a conditional statement (i.e., p⇒q). Very important idea: Therefore, it is not logically equivalent to its inverse Fairness criterion - a precise statement which expresses ¬p⇒¬q. In other words, it is NOT valid to conclude that \"If the specific intuition about what should or should not occur there is no majority candidate, then there should be no in a fair election. winner\". Caution: There is a difference between a voting method and a fairness criterion. In a specific election, a voting method tells us who does in fact win. A fairness criterion either: • tells us who should win that particular election, • or it doesn’t apply to that particular election and therefore has nothing to say about who should win. Fairness Criterion 1: The Majority Criterion The Majority Criterion: If there is a majority candidate in an election, then that candidate should be the winner.

Plurality Method satisfies the Majority Criterion Ex: In an election using plurality method, the winner can be any Condorcet Candidate of the two possibilities: - A Condorcet candidate in an election is a candidate, if 1. The winner is the majority candidate, and there is one, that beats all other candidates in one-on-one therefore, the plurality candidate as well. Hence, or head-to-head competition. the Majority Criterion is satisfied. Ex: 2. The winner is the plurality candidate but not a Fairness Criterion 2: The Condorcet Criterion majority candidate. In this case, the Majority Criterion is not applicable (or not violated). So, the Condorcet Criterion: If there is a Condorcet candidate in winner is still the fair winner according to the an election, then that candidate should be the winner. Majority Criterion. Ex: In any case, the Majority Criterion is met. Therefore, the Plurality Method never violates the Majority Criterion. If there is a majority candidate, then that candidate has more than 50% of the first choice votes. Such a candidate is automatically a plurality candidate, and therefore the winner of the election under the Plurality Method. For any specific voting method, there are two possibilities: Either the method never violates the Majority Criterion, 1. i.e. it is guaranteed to declare the majority candidate the winner of the election, in every 2. election which has a majority candidate or, the method sometimes violates the majority criterion, i.e. there are some elections in which there is a majority candidate, but the method declares a different candidate to be the winner. Fact: The Plurality Method never violates the Majority Criterion. If there is a majority candidate, then that candidate has more than 50% of the 1st choice votes. Such a candidate is automatically a plurality candidate, and therefore the winner of election under the Plurality Method. Fairness Criterion 2: The Condorcet Criterion Head-to-Head Competition • Often useful to compare just two candidates to one another, temporarily ignoring all other candidates; we consider which of the two candidates rank higher on more ballots than the other. The comparison is called “ head-to-head competition”, Of the two candidates, the candidates ranked higher on more of the ballots is the winner of that head-to-head competition. The Plurality Method sometimes violates the Condorcet Criterion.

Fairness Criterion 3: The Monotonicity Criterion - The criterion too pertains to the situation of an election and a revote, but now it is not the ballots which change We consider a new fairness criterion, which pertains to from election #1 to election #2, but rather the candidates. what should happen when an election is held and a winner There are only very specific situations in which it applies at is declared, but for some reason, there is a re-election. all. Monotonicity Criterion: It should be impossible for a winning candidate to lose in a re-election if the only Suppose that an election is held using a specific changes in the votes were changes that were favorable to voting method, and a winner is declared. that candidate. Suppose further that a revote is held, in which a non-winning choice is removed from the ballot. Suppose that an election is held using a specific Then the original winner should remain the winner voting method, and a winner is declared. in the revote. Suppose further that a revote is held, and some Difference between the Monotonicity and the I.I.A. voters change their votes to move the winner of Both criteria pertain to an original vote and a revote. for the election higher on their ballots. Moreover, no each one, there are specific circumstances in which a changes are made which move another candidate change in winner from the original election to the revote higher on any ballots, or the original winner lower. counts as a violation, i.e. an unfair outcome. Then the original winner should remain the winner These specific circumstance are different for the two in the revote. fairness criteria: • For the Monotonicity Criterion, the issue is that Fairness Criterion 4: The Independence of some ballots have changed in a very specific way. Irrelevant Alternatives (IIA) Criterion • For the I.I.A. criterion, the issue is that the list of candidates has changed in a very specific way. Similar to the previous criterion, the new fairness criterion here pertains to what should happen when an election is Fairness Criterion 5: The Pareto Criterion held and a winner is declared, but for some reason, there is a revote. The Pareto Criterion: If there is at least one candidate, say Candidate X, that every voter prefers to another candidate, There is a certain intuition that this behavior is irrational. say Candidate Y, then it should be impossible for Candidate The ice cream is an “Irrelevant alternative”, an option Y to win the election. which wasn’t going to be selected in the first place. Removing it altogether from the list of choices should have • PARETO - The Pareto condition for single winner no effect, and if it does change the outcome, then there is system is that if everyone prefers one candidate x something irrational about the decision making process. to another y, then y is not the winner. For systems Idea: Decisions should be independent of whether that output a social ranking of just one winner, the irrelevant alternatives” are available as options or not. condition claims that is everyone in the society The Independence of Irrelevant Alternatives (IIA) Criterion: prefers x to y, then y cannot rank higher than x on If a re-election is held with the same ballots and non- the final societal ranking. winning candidates are removed, the previous winner This condition seems amazingly intuitive, if should still win. everyone wants choice x over choice y, and choice y is chosen or rank higher than choice x on the final ranking, something has gone horribly wrong with our system. Three types of voting methods: • Majority rule method • Plurality method • Condorcet method Condorcet method • A philosopher and mathematician, the Marquis de Condorcet (1743-1794) was well aware of the flaws in the plurality system.

• Condorcet suggested a method based on the fact • This method is used, among others, in choosing that majority rule works so well for two site of the Olympics, the Academy Awards, and • candidates. elections in Australia and Ireland. In Condorcet method, a candidate is a winner Ex: when he/she, on the basis of the ballots cast, Round 1 defeat every other candidate in a one-on-one (or • Count the first choice votes for each candidate, head-to-head) contest using majority rule. In fact, just as you would in the Plurality method. if there are only two candidates, the Condorcet • If a candidate has a majority of first-choice votes, method is the same as the Majority Rule method. then immediately declare that candidate the winner, and the election is over. 1. • If two or more candidates are tied for the dubious honor of having fewest first-choice votes, eliminate both/all such candidates. 2. Round 2 • Cross out the name(s) of the candidates eliminated from the preference table and recount the first- choice votes. • Our convention is that when a candidate is eliminated from the preference table. in each table the candidates below it move up a spot. • If after moving the surviving candidates up in this way, there is now a candidate with a majority of first-choice votes, then declare that candidate the winner. • Otherwise, eliminate the candidate who currently has the fewest first-choice votes. The Condorcet method, like the Majority rule method, may not produce a winner when there are more than two candidates. This situation is called the Condorcet's voting paradox. Consider the following example. Instant Runoff Voting (IRV) System • In this method, a winner is determined by repeatedly deleting candidates, in stages, that are least preferred. A winner may emerge after all other candidates have been deleted or when there is a tie among two or more candidates. • The IRV system is also called the Hare System after Thomas Hare (1806-1891) who introduced the method.

Round 3 and 4 The candidate with the highest total number of • Repeat the process, each time eliminating one or points is the winner under the Borda Count more candidates until there is a candidate with a Method. majority of first-choice votes. In the extended Borda Count method, we rank candidates based on the number of Borda Count points received. The Borda Count method is used in many important aspects of our civilization, including ranking college football and basketball teams. It is not commonly used in political elections. A convenient way to check your work when using the Borda Count method is to add up the points that all the candidates have received. This should equal the total number of points on each ballot multiplied by the number of ballots. What is wrong with IRV? What is wrong with Borda Count? 1. IRV can sometimes violate the Condorcet Criterion. 1. Borda Count can sometimes violate the Majority 2. IRV can sometimes violate the Monotonicity criterion. Criterion. o If voters change their votes to increase the • A candidate could receive a majority of the first- preference for a candidate, it should not votes and still lose the election. harm that candidate’s chances of winning. 2. Sometimes described as a consensus-based voting Borda Count Method system, since it can choose a more broadly acceptable option over one with the majority • The Borda Count Method is named after Jean- support. Charles de Borda (1733-1799). • This is a different approach than plurality and • This method assigns points to the ranked instant runoff voting that focus on first-choice candidates on each voter's preference list. The votes. Borda count considers every voter’s entire total points received for each candidate for all ranking to determine the outcome. voters are added. Sequential Pairwise Voting • The winner is the candidate with the most points (referred to as the candidate's Borda score). • Sequential pairwise voting begins with an agenda, which is the order in which the candidates are This method is based on a point system, so that every entry compared one-to-one, and pits the first candidate on every ballot counts for something. against the second in a head-to-head competition. Each last choice vote a candidate receives is worth • For example, comparing X and Y, X wins if more 1 point each second to the last choice vote is worth voters rank X above Y. The winner then moves on 2 points etc. If there are N candidates, then each first choice vote a candidate receives is worth N points.

one candidate, or all of the candidates. The winner of the election is the candidate with the largest number of votes. Arrow's Impossibility Theorem • States for every voting method, there is at least one fairness criterion which the voting method sometimes violates. • No voting method can be engineered so that it is guaranteed to avoid violating any of our four fairness criteria. to confront the third candidate in the list, also head-to-head. Losers are eliminated. • This process continues throughout the agenda. • The one remaining at the end wins. Sequential pairwise vs Condorcet • If there is a Condorcet winner, then that winner will be the sequential pairwise winner no matter what agenda is used. • If there is not a Condorcet winner, then it will always be possible to change the sequential pairwise winner by using a different agenda. What is wrong with Sequential Pairwise Voting? 1. Sequential Pairwise Voting can sometimes violate the Pareto Criterion. • Pareto condition states that if everyone prefers one candidate (in this case B) to another candidate (D) , then this latter candidate (D) should not be among the winners of the election. 2. Sequential Pairwise Voting can sometimes violate IIA Criterion Approval Voting - In this method of voting, each voter chooses as many of the candidates as he/she finds acceptable. A voter can choose none of the candidate, one candidate, or more than

What is wrong with Approval Voting? Sometimes the approval voting tends to elect the least disliked candidate. Arrow’s Impossibility Theorem Kenneth Arrow proved that it is impossible to design a voting system that would simultaneously obey all the fairness criteria. More precisely, it is possible that in an election, a particular outcome of votes will violate some fairness criteria. Arrow’s Impossibility Theorem states for every voting method, there is at least one fairness criterion (of the four we have discussed) which the voting method sometimes violates. Caution: Arrow’s Theorem does not imply that in every election, a violation actually occurs. Nor does it imply that democracy is inherently unfair. What does Arrow’s Theorem imply? No voting method can be engineered so that it is guaranteed to avoid violating any of our four fairness criteria. Clarification: “sometimes violates” should be thought of as meaning “eventually violates”. This means that if a specific voting method is applied to a large enough collection of preference tables (or pairs of “before and after” preference tables, with regard to Monotonicity and I.I.A. criteria), then it will eventually violate one of our four fairness criteria. In other words, there is an example of an election in which that voting method produces a violation.

Mathematics for Efficiency Two variable LP: Introduction to Linear Programming Maximize f(xy) = 40x + 32y Basic steps of the OR Process: subject to 1. Defining the Problem. 2. Building a Mathematical Model. 10 ≤ x ≤ 40 3. Solving a Mathematical Model. 30 ≤ y ≤ 70 x + y ≤ 90 Linear Programming x≥o y≥0 • The adjective linear means that all the mathematical functions in this model are required There are many techniques of solving LP problems. One of to be linear functions. Involve planning of activities them is the graphical method. to obtain an optimal result. Basic Components of Linear Programming Idea: Graph the constraints to determine all feasible 1. solutions to the problem. • Decision variables – These are quantities to be 2. Find the optimum solution among all the feasible determined. solutions. • Objective Function – This represents how each decision variable would affect the cost, or, simply, the value that needs to be optimized. • Constraints – These Represent how each decision variable would use limited amounts of resources. Maximization & Maximization Problem A fruit shake stand sells banana and mango shakes. To be Corner Point Theorem profitable, it must sell at least 10 orders of banana shakes - If a linear function and 30 orders of mango shakes per day. Due to limited space however, no more than 40 orders of banana shakes f(x,y) = ax + by or 70 orders of mango shakes can be served. Even the total assumes a maximum or minimum value subject to a system number of orders for the day cannot exceed 90. If profit is of linear inequalities, then it does so at the corners or Php40 for each banana shake sold and Php32 for each vertices of that system constraints. mango shake, how many of each kind should the vendor Steps to solve a LP problem sell in order to maximize profit? Decision Variables: 1. Determine the feasible region (the solution to the x = No. of banana shakes system of inequalities). y = No. of mango shakes 2. Find coordinates of the corner points in this Shake Profit per Number Total profit feasibility region. Flavor item sold per item 3. Test these corner points in the objective function Banana 40 x 40x to find the optimal solution (highest or lowest Mango 32 y 32y value). Maximize profit function -> f(xy) = 40x + 32y Constraints: • 10 ≤ x ≤ 40 - At least 10 but no more than 40 orders of banana shakes. • 30 ≤ y ≤ 70 – At least 30 but no more than 40 orders of banana shakes. • x + y ≤ 90 – Total number of orders cannot exceed 90. • x ≥ o and y ≥ 0 [nonnegativity constraints]

Solve using desmos: The Shortest Path Problem The shortest path search is a problem whose application can be found in • traffic information systems • mapping (google map, waze, etc.) • data network routing (the goal is to find the path for data packets to go through a switching network with minimal delay) Graphs are structures consisting of vertices (or nodes) and edges (or links) that connect the vertices/nodes. Real life application: With this representation, graphs can also be used to model the spread of infectious diseases (such as COVID-19) and design prevention and response strategies. Vertices represent individuals, and edges their possible contacts. This model is useful to calculate how a particular individual is connected to others. Knowing the shortest path lengths to other individuals can be a relevant indicator of the potential of a particular individual to infect others. This also attests to the importance of effective contact tracing of susceptible and infected individuals. To improve the representation, we will consider weighted graphs wherein the weights may represent • cost • distance • time of delay, etc. These weights are typically indicated in the edges of a graph. Consider the graph below. This graph represents a map in which the: • vertices (A, B, C, D, & E) represent different cities • edges represent the routes connecting the cities • weights of the edges represent the distances of the routes

Problem: You are at city A and you want to join a festival in Assignment Problems city D. What is the shortest distance between A and D? There are several efficient methods or algorithms that - are linear programming problems that are primarily concerned with determining search the shortest path between vertices in a weighted optimal assignment or allocation of resources: graph. The one that will be presented here is the one ▹ People to tasks developed by the Dutch mathematician Edsger Dijkstra ▹ Jobs to machines (1930-2002). ▹ Contracts to bidders DIJKSTRA’S ALGORITHM ▹ Salespeople to areas Let distance of start vertex from start vertex = 0. The objective is most often to minimize total costs Let distance of all other vertices start = ∞ (infinity). or total time of performing the tasks at hand. Repeat Assumptions: ▸ In an assignment problem, only one person is assigned • Visit the unvisited (or unexplored) vertex with to one task, one job to one machine, one contract to one the smallest known distance from the start bidder and one salesperson to one area. vertex ▸ The number of assignees and the number of tasks are the same. (Balanced problem) • For the current vertex, examine its unvisited ▸ Each assignment problem has an associated table neighbors (opportunity cost table) where the rows contain people we wish to assign, and the columns contain the tasks to • For the current vertex, calculate distance of be assigned. We would like to make assignments such each neighbor from start vertex that opportunity cost for each assignment is zero and thus minimizing the total cost. • If the calculated distance of a vertex is less that the known distance, update the shortest Ex: The F-Shop has just received three new rush distance • projects to repair: (1) a radio, (2) a coffee maker, and (3) a oven toaster. • Update the previous vertex of each of the • updated distances • Three repair persons, each with different talents and abilities, are available to do the jobs. • Add the current vertex to the list of visited • vertices The owner of the shop estimates what it will cost in wages to assign each of the workers to each of Until all vertices are visited the three projects. Finding the route The costs which are shown in the given table differ because the owner believes that each worker will We can use Dijkstra’s algorithm to find the length of the differ in speed and skill on these quite varied jobs. shortest distance between two vertices in a network. However, if we want to find the corresponding route, we Repair Costs of F-Shop need to record more information as we apply the algorithm. Tip: Instead of listing temporary values, we put a letter after each value, which indicates the preceding vertex on the route. We find the route by backtracking through the network from the finishing point.

Hungarian Method PHASE 2 (Optimization of the Problem) PHASE 1 (Row and Column Reduction) 1. Draw a minimum number of lines to cover all the zeros of the matrix. 1. Subtract the minimum value of each row from the Procedure: entries of that row. a. Row scanning 2. Subtract the minimum value of each column from the • Starting from the first row, ask the following entries of the column. question: Is there exactly one zero in that row? If yes, mark a square around that zero entry and draw a vertical line passing through that zero. Otherwise, skip that row. • After scanning the last row, check whether all the zeros are covered with lines. If yes, go to step 2. Otherwise, do column scanning. b. Column scanning • Starting from the first column, ask the following question: Is there exactly one zero in that column? If yes, mark a square around that zero entry and draw a horizontal line passing through that zero. Otherwise, skip that column. • After scanning the last column, check whether all the zeros are covered with lines. 2. Check whether the number of marked squares is equal to the number of rows (or columns) of the matrix. If yes, go to step 5 (i.e., optimality is reached). Otherwise, go to step 3.

3. Identify the minimum value of the undeleted cell values. Maximization Problem a. Add the minimum undeleted cell value at the • Some assignment problem are phrased in terms of intersection points of the present matrix. maximizing the payoff (as opposed to minimizing b. Subtract the minimum undeleted cell value from cost) of an assignment. the undeleted cell values. • By subtracting every number in the original payoff c. All other entries remain the same. table from the largest single number in the table, we obtained an equivalent minimization problem. 4. Go to step 1. • The transformed entries represent opportunity 5. If the number of rows equals the number of marked costs, and minimizing the opportunity costs for the squares, optimality is reached. The optimal solution is transformed problem produces the same optimal precisely the ones marked with squares. assignment as the original maximization problem. 3. Identify the minimum value of the undeleted cell values. Ex: a. Add the minimum undeleted cell value at the A department chairperson has 4 teachers to assign to 4 intersection points of the present matrix. different subjects (W, X, Y, Z). All teachers have taught the b. Subtract the minimum undeleted cell value from courses in the past and have been evaluated with a score the undeleted cell values. from 0 to 100 as shown in the table. The chairperson wants c. All other entries remain the same. to know the optimal assignment of teachers to subjects that will maximize the overall total score. Solution:

Mathematics in Finding the nth Term in the Fibonacci Sequence Nature and Arts (Binet Form) The Number Phi φ Ø = ( 1 + √5 )n and - Ø = ( 1 - √5 )n 22 - The golden number - Phi ( Φ = 1.618033988749895… ), most often pronounced Ex: fi like “fly,” is simply an irrational number like pi ( p = 3.14159265358979… ), but one with many unusual Find the 13th Fibonacci number mathematical properties. Unlike pi, which is a transcendental number, phi is the solution to a quadratic Ø = ( 1 + √5 )13 and - Ø = ( 1 - √5 )13 equation. 22 Phi is the basis for the Golden Ratio, Section or Mean - The ratio, or proportion, determined by Phi (1.618 …) was = 233 known to the Greeks as the “dividing a line in the extreme and mean ratio” and to Renaissance artists as the “Divine The Golden Ratio and Fibonacci Sequence in Nature Proportion” It is also called the Golden Section, Golden and Arts Ratio and the Golden Mean. Golden Ratio: Divide a line so that: • The proportions of the human body • The proportions of many other animals the ratio of the length of the entire line (A) to the length • Plants of larger line segment (B) is the same as • DNA the ratio of the length of the larger line segment (B) to the • The solar system length of the smaller line segment (C). • Art and architecture This happens only at the point where: • Music A is 1.618 … times B and B is 1.618 … times C. • Population growth Alternatively, C is 0.618… of B and B is 0.618… of A Phi • The stock market with an upper case “P” is 1.618 0339 887 …, while phi with a lower case “p” is 0.6180339887, the reciprocal of Phi and Fibonacci Sequence: also Phi minus 1. • Shells What makes phi even more unusual is that it can be derived • trees in many ways and shows up in relationships throughout the • Flower Pistils universe. • Flower Petals • Leaves The Fibonacci Sequence • Storms The Fibonacci Sequence and the Golden Ratio Fractals The Fibonacci Sequence is the series of • A fractal is a never-ending pattern. Fractals are numbers: infinitely complex patterns that are self-similar 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... across different scales. They are created by The next number is found by adding up the two numbers repeating a simple process over and over in an before it: ongoing feedback loop. • the 2 is found by adding the two numbers before it • The word fractal was coined in 1980 by the Belgian (1+1), mathematician Benoit Mandelbrot (1924-2010). Mandelbrot chose the name fractal because it • the 3 is found by adding the two numbers before it reminds us of the word \"fraction\". (1+2), Fractal Construction (Self-similarity) • the 5 is (2+3), and so on Suppose that we start with a filled-in triangle. We connect the midpoints of each side and remove the middle triangle. We then repeat the process. What will the resulting shape be?

Sierpinski otherwise impossible with conventional technology. On a Triangle related note, fractals are also used in creating some computer Use the initiator and generator shown to create the graphics. iterated fractal. In addition, fractals are a very important part in biological studies. For example, a lot of objects in nature are composed of complex figures that are otherwise not possible to be defined by Euclidean shapes. Most natural objects, such as clouds and organic structures, resemble fractals. As such, fractals can be used to capture images of these complex structures. In addition, fractals are used to predict or analyze various biological processes or phenomena such as the growth pattern of bacteria, the pattern of situations such as nerve dendrites, etc. And speaking of imaging, one of the most important uses of fractals is with regards to image compressing. A pretty controversial process, it takes an image and expresses it into an iterated system of functions. This image is displayed quickly and is expressed in detail in any magnification. Fractals in Nature Examples: • Broccoli • Snowflake • Universe Fractals: Application Koch snowflake 3 x 4n Contrary to its complicated nature, fractals do have a lot of uses in real life applications. First, we start with art. The image created by a fractal is complex yet striking, and has intrigued artists for a long time already. In fact, fractal art is considered to be true art. Artists such as Jackson Pollock and Max Ernst, has used fractal patterns to create seemingly chaotic yet defined forms. Even in African art and architecture fractal shapes and images are prevalent. In addition, some artists are inspired by fractal images when creating their own art forms. Not only that: fractal images are actually being used nowadays to create special effects. Utilized in shows such as Star Trek and Star Wars, fractals are used to create landscapes that are

References: Fibonacci Sequence. Math is Fun. (2020). https://www.mathsisfun.com/numbers/fibona cci-sequence.html. McGraw, V. (2019, October 16). 7 Beautiful Examples Of The Fibonacci Sequence In Nature. The Odyssey Online. https://www.theodysseyonline.com/7- beautiful-examples-fibonacci-sequence- nature. What are Fractals? When Do You Use Them In The Real World? TeAchnology. (n.d.). https://www.teach- nology.com/teachers/subject_matter/math/fra ctals/. For more questions, email me at [email protected]