Math 1101

Final Review

Fall 2002

Solutions (not guaranteed)

Number of Voters	12	21	8	10	2
1^st Choice	B	A	D	C	A
2^nd Choice	D	D	C	A	C
3^rd Choice	A	C	A	D	D
4^th Choice	C	B	B	B	B

1. Given the above voting schedule determine the winner via the following methods:
1. Plurality method

i. A has 23 1^st place votes and wins

2. Borda count method

i. A 162, B 89, C 124, D 155: A wins

3. Pairwise comparison method.

i. A defeats B, A defeats C, A defeats D and A is the winner.

4. Plurality-with-elimination method.

i. D is the first eliminated as they have a mere 8 votes, C gets 8 more fist place votes and B is eliminated. This then give A 35 first place votes and A is the winner.

2. Determine who came in second using
1. The extended-plurality method.

i. B has 12 first place votes and comes in second.

2. The recursive Borda count method.

i. A won, so we remove A from the list. Now B has 77 points, C has 106 points, D has 135 points and D comes in second.

3. Is there a condorcet candidate? Why or why not?

A is the Condorcet Candidate as they defeat everyone in head to head competition.

4. know the meanings of the following criterion: the majority criterion, the condorcet criterion, the monotonicity criterion, and the independence-of-irrelevantoalternatives criterion.

Weighted Voting:

5. Given the voting system: {15: 5, 4, 3, 2, 1}
1. Who is the dictator? No one.

6. Given the voting system: {15:10, 7, 5, 3, 3 }
1. Who is the dictator: No one
2. Are there any dummies? No, it is possible for any of the voters to be a necessary part of a winning coalition.
3. What is the power index of each voter using the Banzhaf power index?

i. Winning coalitions

Coalition critical members

P1,p2 p1, p2

P1, p3 p1, p3

P1,p2, p3 p1

P1, p2, p4 p1, p2

P1,p2, p5 p1, p2

P1,p3,p4 p1,p2

P1,p3,p5 p1,p3

P1,p4,p5 p1, p4, p5

P2,p3,p4 2,3,4

P2,p3,p5 2,3,5

P1.p2,p3,p4 none

P1.p2,p3,p5 none

P1.p2,p4,p5 p1

P1.p3,p4,p5 p1

P2,p3,p4,p5 1,2

P1,p2,p3,p4,p5 None

Player number times critical Power index

P1 11 11/26

P2 7 7/26

P3 4 4/26

P4 2 2/26

P5 2 2/26

4. How many Banzhaf coalitions are there? 2^5 = 32
5. What is the power index of each voter using the Shapley-Shubik power index?
6. How many Shapley-Shubik sequential coalitions are there? 5! = 120 Coalitions
6. Given the voting system: {q: 10, 8, 6, 4, 3}, find q if a 2/3 majority is needed to pass a referendum? (2/3)(31) = 20 2/3 or q = 21
7. Given the above voting system, what is the minimum quota? Must be greater than 50%. .5(31) = 15.5 or 16 is the minimum quota.
8. Which of the following is not a possible Shapley-Shubik power index for a system with 6 players. 1/3, 1/5, 1/7, 1/8. The number of coalitions is 6! Or 720 coalitions. 720 is divisible by 3, 5 and 8 but not 7 so 1/7^th is not a possible power index.
9. Henry likes chocolate cake 5 times as much as he likes strawberry cake. If a cake which is half and half is worth $24, how much is the chocolate half worth to him?

i. Let x = the value of the strawberry portion, then

5x = the value of the chocolate portion

The total value of the cake is x + 5x = 24

X = $4

The chocolate portion is worth $20.

11. If the cake is cut in half so that one piece is 1/3 chocolate and 2/3 strawberry, how much is this piece worth to Henry. (1/3)(20)+(2/3)(4)= $8 to Henry.
12. Explain the divider-chooser method.
13. Know the lone divider and lone chooser methods.
14. Using the method of sealed bids determine who gets which item and how much cash they receive or pay out.

The Bids are:

	Mavis	Donald	Douglas
Car	15000	10,000	5,000
Yacht	15,000	25,000	20,000
Jewelry	10,000	5,000	18,000
Total Value	40,000	40,000	43,000
Should get	13,333.33	13,333.33	14,333.33

Car: Mavis

Yacht: Donald

Jewelry: Douglas

Mavis gets car and pays 1,666.67 to the pot.

Donald gets the yacht and pays 11,666.67 to the pot

Douglas gets the Jewelry and pays 3,666.67 to the pot.

The pot has $17000.01 in it. This is divided out three ways and each person gets $5666.67

Mavis gets car and gets $4000.

Donald gets the yacht and pays $6,000

Douglas gets the Jewelry and gets $2000.

Apportionment:

	Population In ten thousands	Lower Quota	Standard Quota	Upper Quota	Apportionment Hamil? Jeff
Minnesota	492	27	27.94	28	28
Wisconsin	536	30	30.44	31	30
Iowa	293	16	16.64	17	17
Kansas	269	15	15.28	16	15
Nebraska	171	9	9.71	10	10
Total	1761	97		102

15. A panel is to be created consisting of representation of the following states, and the panel is to consist of 100 members.
1. What is the standard divisor? 1761/100 =17.61
2. Find the standard quota for each state.
3. Fill in the lower and upper quotas.
4. What will be the apportionment using the Hamilton method? See who has the largest Portion left over and give the extra three states to them.

5. What will be the apportionment using the Jefferson method? Lower quota = number of seats

	Population	Lower Quota	Modified Quota	Upper Quota	Apportionment
	In ten thousands				Jeff
Minnesota	492	28	28.63714	29	28
Wisconsin	536	31	31.19818	32	31
Iowa	293	17	17.05423	18	17
Kansas	269	15	15.6573	16	15
Nebraska	171	9	9.953152	10	9
	17.18049	100		105

6. What will be the apportionment using the Adams method? Upper quota = # seats

	Population	Lower Quota	modified Quota	Upper Quota	Apportionment
	In ten thousands				Adams
Minnesota	492	27	27.3799	28
Wisconsin	536	29	29.82851	30
Iowa	293	16	16.30551	17
Kansas	269	14	14.9699	15
Nebraska	171	9	9.516184	10
	17.96939	95		100

7. What will be the apportionment using Webster’s method? Round the quota to the nearest number.

	Population	Lower Quota	Standard Quota	Upper Quota	Apportionment
	In ten thousands				Webster’s
Minnesota	492	27	27.93867	28	28
Wisconsin	536	30	30.43725	31	30
Iowa	293	16	16.63827	17	17
Kansas	269	15	15.27541	16	15
Nebraska	171	9	9.710392	10	10
	17.61	97		102	100

16. Which of the above methods favor larger states? You can see from the examples above which tend to favor the larger and smaller states…Ham, Jeff
17. Which favor smaller states? Adams, Webster
18. Which violate the quota rule? Jeff, Ham, Web. The Alabama paradox? Ham. Population paradox? Ham New-States paradox? Ham
19. Know the terminology:
1. Adjacent edges and vertices,
2. Bridges
3. Circuit
4. path
5. Euler circuit
6. Euler path
7. How to eulerize a graph
8. Connected graphs
9. Loop
10. Multiple edges
11. Unicursal tracings.
20. problem 25 page 183. If the graphs do not have Euler paths, eulerize them.
21. problem 62 on page 190.
22. Draw a complete graph with 6 vertices. Draw six vertices, or a hexagon, and draw lines connecting each vertex to every other vertex.
23. How many edges does a complete graph with 10 vertices have? N(N-1)/2 or 45 edges.
24. How many Hamilton circuits will a complete graph with 10 vertices have? (n-1)! Or 9! Hamilton circuits.
25. Traveling salesman problems

Use the following algorithms to find a path for a traveling salesman visiting each of the following cities:

	Alexandria	Minneapolis	Rochester	Brainerd	Bemidji	Mankato
Alexandria	*	131	214	86	133	165
Minneapolis	131	*	83	125	214	120
Rochester	214	83	*	208	297	83
Brainerd	86	125	208	*	97	179
Bemidji	133	214	297	97	*	266
Mankato	165	120	83	179	266	*

1. Nearest-neighbor algorithm.
2. Repetitive-nearest-neighbor algorithm
3. Cheapest-Link algorithm
4. Kruskal’s algorithm to find the minimum spanning network between the above cities.

26. Create a project digraph for the following information:
1. Then determine a descending time priority list and make a schedule accordingly.
2. Determine the critical values of each vertex.
3. Create a critical path list.
4. Find a schedule using the critical path priority list.

Task	Length of Task	Tasks that must be completed Before you can start
A	7
B	5
C	6
D	8
E	5	A ,B
F	7	E, C
G	5	D, F
H	4	E
I	4	F
J	3	G,I
K	1	H, L
L	4	I
M	3	L, J
N	6	K
O	3	L

27. Find the 10^th Fibonacci number. 55 or = 55
28. What is the golden ratio?
29. What is the golden ratio to the 10^th power?

30. Calculate gnomons
31. Use chapter 10 reviews already provided…
32. Find the value of $40,000 in 8 years if interest is 8% nominal compounded quarterly .

One Payment: Compound interest. Looking for a future value

33. How much needs to be invested now at 9% compounded semi-annually to have $40,000 in 5 years?

One Payment: Compound interest looking for a present value.

34. James invests $200 at the beginning of each month from January 1^st 2003 until December 1^st 2013. On January 1^st 2014 he starts investing $500 per month until he retires on December 31^st 2039. What will the value of this annuity be on the day he retires if interest is 9% compounded monthly during this time?

Future Value of an annuity due.

Let’s think of this as two annuities. One worth $200 going from 1/1/03 to 12/1/39 and another worth $300 starting 1/1/14 and last payment on 12/2/39. Then add the two annuities together.

35. Find the effective interest rate on 7% compounded monthly to the nearest hundredth of a percent.

36. You buy a house for $150,000. The loan is for 30 years at 7.2% compounded monthly. What is the house payment before insurance and taxes? Create the first 3 rows of an amortization table for the loan.

This is the present value of an ordinary annuity to find the payment.

R=1018.18