59.255 - Assignment 1

Due at or before 10AM Tue 19 April

No extensions will be given under any circumstances.
This assignment will be marked out of 15 and contributes 15% to the overall grade.

Note: Marks will be given for all serious attempts to solve the problems, even if the correct answers are not obtained.

Part 1 (3 marks)

Answer any one of the following two questions:

Question 1: Marble Garble

When Joe gave his sister a blue marble from his bag, she gave it back to him saying she wanted one of a different colour. But Joe said ``That's impossible. All marbles are the same colour'' and tried to convince her with the following inductive proof:

The assertion is: S(n): All marbles in a bag containing $n$ marbles are of the same colour.

Basis: Obviously S(1) is trivially true. All the marbles in a bag containing just one marble are of the same colour.

Induction: Assume that S(n) is true. i.e. That ``All marbles in a bag containing n marbles are of the same colour'' is true. Now consider a bag with n+1 marbles. Remove an arbitrary marble from the bag. Now the bag contains n marbles which must all be the same colour by the inductive hypothesis. Swap this marble with any other marble in the bag. Again all the marbles in the bag must be of the same colour. By symmetry, the marble initially removed from the bag must be the same colour as the rest of the marbles in the bag. The inductive hypothesis is thus proved.

However, Jill, being a keen 59.255 student immediately proceeded to demolish Joe's proof and demanded that he indeed swap her marble for one of a different colour. Describe clearly how Jill invalidated Joe's proof.

Question 2: Redundant Exponents

Explain what is wrong with the following inductive proof:

Assertion: S(n): For all n >= 0: an = 1

Basis: S(0) = a0 = 1 which is true.

Induction: Assume S(i) is true for 0 <= i < n. Now

an = (an-1)(an-1) / an-2

By the inductive hypothesis, an-1 = an-2 = 1

Thus an = 1/1 = 1

We have thus proved that an = 1 for all n.

Part 2 (5 marks)

Answer any one of the following two questions:

Question 1: Odd Shakers

During the Bizarre ball, everybody gets introduced to a number of people. Assume that introduction is always accompanied by a shaking of hands. Using structural induction, prove that the number of persons who have shaken hands an odd number of times is even. (Because of the nature of refreshments that are provided during this ball, people frequently tend to forget that they were introduced to a certain person and so bear in mind that a person may be introduced to someone more than once.)

Question 2: Safe encounters of the nth kind

At an interplanetary Bizarre ball, three Earthlings were once introduced to a beautiful Martian with whom they desired to shake hands. However, it was common knowledge that Martians were covered with Martian dust which is deadly to Earthlings. They may only shake hands with a Martian if gloves are worn by either or both parties. To complicate matters, the Earthlings weren't even sure if one of the others of them has had an unsafe handshake with a Martian before. So they must protect themselves not only against Martian dust from the Martian, but also against Martian dust that may have rubbed off on to one of the less careful Earthlings.

To their dismay, however, they found that between them they only had two gloves and that all the glove vending machines on campus were empty, as could be expected during an event such as this one. Nonetheless, being mathematicians of the first rank, they soon came up with the following ingenious solution:

The Martian wears glove 1 first. Earthling 1 then proceeds to shake the Martian's hand wearing glove 2, followed by Earthling 2 who shakes her hand without wearing a glove at all (Remember that he is safe because the Martian is wearing a glove). Finally, the third Earthling turns glove 2 inside out, wears it (ensuring that he is in contact only with its uncontaminated side), and shakes the Martian's hand.

Reminiscing about the encounter the following morning, one of the Earthlings remarked that he could in fact generalise from their experience that 2n-1 Earthlings can shake hands safely with a Martian using just n gloves. Prove this using mathematical induction.

Part 3 (7 marks)

Answer any one of the following two questions:

Question 1: A Pizza Puzzle

A few years ago, Dial-a-Dino's launched a promotion in which you get a free pizza of equal or lesser value for every pizza you ordered. After Toga party night, when everybody was tired and hungry, a large group of students decided to order pizzas into the dorm in Kiwitea Lounge.

One bright student, who was slightly more sober than the rest proposed the following algorithm in order to keep total costs to a minimum: Sort all the pizzas, largest first, and only pay for the odd numbered pizzas. (Note that if the number of pizzas is odd, then you pay for the last pizza unpaired).

Show using mathematical induction that this algorithm is in fact the best that one could come up with if the aim is to keep total costs to a minimum.

Question 2: Bundled Bottles

A certain well-known bottled beverage only comes in packs of 6, 10 and 15. What is the largest number of bottles that cannot be bought? Prove your answer using mathematical induction.