Mid-Term Problem Solving

Mathematics 5

Winter Term 2002

The World According to Mathematics

Mid-Term Problem Solving Exam

January 30, 2002 Name:______________________________

Dwight Lahr, David Rudel

In class on Monday, February 4, hand in this sheet with your solutions to the following problems. You should feel free to ask questions of your instructors as you work on these problems. However, it is a violation of the honor principle to consult anyone else. You may use as resources only the text and notes of the course. By the way, the new date to turn in the paper is Wednesday, February 6. Good luck.

(5 points) 1. Let's define an infinite set as a set that can be placed in a one-to-one correspondence with a proper subset of itself. [Note: Set A is a proper subset of set B if A is contained in B and not equal to B.] Using this definition of infinite set, show that is an infinite set.

(10 points) 2. Transfinite arithmetic:

(a) When we write , we have in mind the process of putting together three disjoint (i.e. no elements in common) sets, one with three elements, one with two elements, and one with one, and counting the number of elements in the new set to get six. Carry out a similar procedure with specific disjoint sets to illustrate the fact that , where is the cardinality of the set of natural numbers.

(b) When we write , we have in mind the process of combining three disjoint sets of three elements into a single set and counting the number of elements of this new set. Carry out a similar procedure with specific disjoint sets to illustrate the two facts:

(i) (ii)

(10 points) 3. Here is an algorithm for testing for divisibility by 11: Find the sum of the digits in the odd positions (from the right) and the sum of the digits in the even positions. Then find the difference between the sums. If the difference is 0 or a number divisible by 11, then the original number is divisible by 11. For example, to determine whether 9867 is divisible by 11, first form the sum 7 + 8 = 15, then the sum 6 + 9 = 15, and subtract 15 - 15 = 0. Since the difference is 0, the original number 9867 is divisible by 11. (Of course, we can check this answer by actually dividing 11 into 9867 to obtain 897.)

(a) Use the algorithm to check that 2002 is divisible by 11.

(b) A number that reads the same forwards and backwards is called a palindrome. The number 2002 in part (a) is a palindrome. Use the algorithm to explain why every four-digit palindromic number must be divisible by 11.

(d) Is every six-digit palindromic number divisible by 11? Explain.

(e) Based on what you have learned in parts (a) through (d), what do you believe is true about palindromic numbers and why?

(6 points) 4. We all know that , which means that divides , in fact, times. Moreover, divides , as the following equations show:

(a) Now, letting and , rewrite all of the above formulas.

(b) Explain why the foregoing shows that always divides .

(9 points) 5. Start with the Maple worksheet ISBN.mws (on the Math 5 website). For each part of this problem, you should use the worksheet to answer the question, and then submit a printed copy of the worksheet showing your solution.

(a) Verify that 1-85894072-9 is a valid ISBN. [Note: this book is published in England.]

(b) Find a book of your own that is published in the United States. Verify the validity of its ISBN.

(10 points) 6. Do one of the following two logic exercises:

(a) There is an island of sheep in which all sheep wear either blue or red hats. Those sheep with red hats always tell the truth, and those sheep with blue hats always lie (now we know why it is so out of vogue to wear blue hats in sheep culture). The leader (who wears a red hat) is brought a report that a spy has invaded the island. The spy was tackled by two other sheep. However, in the ensuing scuffle all the hats were knocked off the sheep, so we don’t know which one was the spy. Thus, all three sheep are on trial. The leader says the following:

“I will ask each of you a question, and I will stop whenever I can convict or acquit any of you.”

All that is known is that of the three sheep, 1 is the spy, 1 is a liar, and 1 is a “truth”er. The spy can either lie or not.

The Leader asks the first sheep “Are you the spy?”

The leader then asks the second sheep “Is the first sheep lying?”

The leader then asks the third sheep “Are you the spy.”

The leader then convicts one of the sheep.

Which sheep is convicted?

(b) A group of perfectly logical pirates finds a treasure chest of 100 coins. The pirates have a captain, a first mate, a second mate, etc. [that is, there is a ranking system that includes everyone.] The Captain proposes a plan for divvying up the gold. The pirates vote on it (ties go to the Captain). If the vote is in the Captain’s favor, his plan is carried out. If not, the pirates throw the captain overboard and the first mate becomes the Captain, the second mate becomes the first mate, etc., and the new captain proposes a plan for divvying the gold. This continues until one of the plans is agreed upon.

The pirates are perfectly logical and there are three things defining their choice:

i) Self-preservation: If a course of action allows them to live and another will cause them to die, they will always choose the course of action that allows them to live.

j) Greed: Given the choice, they will always choose a course of action that causes them to have the greatest amount of gold.

k) Sanguinity: Given a choice, they will choose a course of action that will cause another pirate to die.

These three things are listed in importance: Self-preservation is always more important than Greed, greed is always more important than sanguinity.

Describe what occurs in each of the following cases:

1) There are 3 pirates

2) There are 30 pirates

3) There are 300 pirates.

[Note, if there are only 2 pirates, the captain could simply make his plan “I get all the gold,” because there will only be 2 votes, and he will win the tie.]