Solving Problems, Writing Proofs, and Enjoying the Pain: How to Succeed in This Class

While humans are capable of rudimentary abstraction, our brains did not evolve to do formal mathematics. Rather, we are best suited for simple, concrete tasks. This informs a possible strategy for actually succeeding in a field like math. To gain real intuition or insight into a problem, it often helps to simplify: substitute values for a variable, draw a picture, compute and test small examples.

In this lecture we will present some short mathematical problems, strategies for problem solving, and advice for writing good proofs. Honing these skills will not only help you survive and succeed in 251, but will also be a great asset in your career as a computer scientist.

Problem 1: A strange game of hats

As an example, consider the following problem: Two bright young people, Alice and Bob, are facing each other wearing hats. Alice's hat is labeled with a positive integer and Bob's hat is labeled similarly with another positive integer . Because they are facing each other, Alice knows the value of (but not ) and Bob knows the value of (but not ). They also both know that and are consecutive (i.e., ).

Now, Alice and Bob (being self-conscious) both want to know the values written on their own hats, but they are not allowed to simply tell each other (they like the challenge). Rather, they are only allowed to say "I don't know what my number is" or exclaim "I know what my number is!" Because her name is first in the alphabet, Alice gets to go first. Suppose we have the following exchange:

Round 1: Alice says, "I don't know what my number is." Round 2: Bob says, "I don't know what my number is." Round 3: Alice says, "I don't know what my number is." Round 4: Bob says, "I don't know what my number is." ... Round 252: Bob exclaims, "I know what my number is!"

Question: If the exchange takes 252 rounds (as above) before either knows the number on his/her hat, then what are the values of and ?

The answer to this question may not be immediately apparent, but there is actually a relatively simple way to arrive at the answer. Rather than letting this charade go on for 252 rounds, suppose it had gone on only for one round.

---

Small Example 1: What if Alice and Bob had instead had the following (brief) exchange?

Round 1: Alice exclaims, "I know what my number is!"

In this case, Alice looks at Bob's number and immediately knows what her number must be. Recall that are consecutive positive integers. Which of the following numbers could (Bob's number) be?

• Could ? No. If Alice saw 2 then she would know that her number is either 1 or 3, but she could not be certain of either value without more information.
• Could ? No. For the same reasons.
• Could ? Yes! If Alice saw 1 on Bob's hat, then she would know that 2 is the number on her hat. Let's follow Alice's chain of reasoning: "I see that and I know that are positive integers and that . But then , the number on my hat, must be a positive integer which satisfies whence I may conclude that !"

---

Small Example 2: Similarly, suppose that Alice and Bob had had the following exchange:

Round 1: Alice says, "I don't know what my number is." Round 2: Bob exclaims, "I know what my number is!"

In this case we must have . Here's a short argument: If Alice sees that she knows that her number is 1 or 3 but cannot be certain of either value and is forced to say "I don't know what my number is." But Bob sees that and can therefore conclude that along the same line of reasoning as Alice in the previous small example.

---

How do we extend this to the case when the exchange is 252 statements long? In addition to being pretty good with concrete tasks, humans are exceptional at recognizing patterns. Let be the value of given that the exchange between Alice and Bob lasts for exactly rounds. In the above two examples we saw that and . Similar reasoning gives us the following table of values of for small values:

n	1	2	3	4	5	6	7	8
H(n)	(2,1)	(1,2)	(3,2)	(2,3)	(4,3)	(3,4)	(5,4)	(4,5)

There is obviously a pattern here and knowing what it is (in this case) is enough to figure out what the answer should be. One might even be so formal as to write down a (somewhat cumbersome) mathematical formula for :

Where (read "the ceiling of ") means divide by 2 and round up. We can use the observed pattern to divine the answer to the original problem: .

Problem 2: Splitting up magnets

Here's another problem: Suppose you have a clump of magnets all stuck together and you want to separate them into single magnets. Each time you split a clump you consume units of energy, where are the sizes of the new piles you have made. What is the least amount of energy necessary to complete the task?

Again, we start with small examples:

• If you have 2 magnets, then there is only one possible way to split them into component magnets: and this consumes units of energy.
• If you have 3 magnets, then you must begin by splitting (which takes units of energy) and then split the remaining pile of size 2: (which takes 1 unit of energy). The total energy cost is 3 units of energy.
• If you have 4 magnets, then you have a choice for the first step:
  • Splitting requires 4 units of energy and the remaining splits (two instances of ) require 2 units of energy total. Thus the whole ordeal costs 6 units of energy.
  • Splitting requires 3 units of energy. We know that splitting up the remaining pile of 3 magnets requires 3 units of energy. Again, the total energy cost is 6 units.

Working these small examples out gives us a clue as to how much energy is required to split up magnets. In fact, such a task requires exactly units of energy, no matter how you choose to perform the task.

A word of caution

Finding patterns is an extremely helpful skill in solving mathematical problems, but it is not infallible! Simply observing a pattern one does not constitute a mathematical argument. If you were asked on a 251 assignment to solve either of the above problems, you would not only be required to produce the right answer (as we have above) but also to prove that this answer is correct.

Mathematics is one of the oldest disciplines of human thought. Experience has taught us that patterns are extremely useful, but occassionally they can be very misleading. For example, if we compute elements of the sequence

we find f(0)=1, f(1)=2, f(2)=4, f(3)=8, and so on.* In fact, up to this gives the powers of 2. If you were unlucky or just overly optimistic, you might have tried to prove that f simply gives the powers of 2. But actually f(6)=63.

While testing small values is always a good idea it can only give you so much information. If you encounter a really funny looking sequence (like the one above) make sure to (1) test enough values and (2) be prepared to modify your claim if need be.

* Remember that is defined as the number of subsets of which have exactly elements. So, for example, . There is an "intuitive reason" why the above sequence can not be . In particular, can be written as a polynomial in k of degree n, so f exhibits polynomial growth. But exponential growth dominates polynomial growth, so f eventually "falls short."

Problem 3: Advice on crossing structurally questionable bridges at night

In tackling the next problem, we will see again how intuition can be misleading: Four guys, Adam, Ben, Carl, and Dave, want to cross a bridge which can only hold 2 people at a time. It is pitch dark and they only have one flashlight, so they must cross either alone or in pairs (bringing the flashlight). Their walking speeds allow them to cross in 1, 2, 5, and 10 minutes, respectively— when a pair crosses, it travels at the slower speed of the two guys. Is it possible for them to cross the bridge in 17 minutes?

Here are some observations: Suppose Adam (the fastest guy) is present in every trip back and forth across the bridge. Intuitively, this seems like it would be the fastest way to cross the bridge.

Step 1: Adam and Dave (the slowest guy) cross the bridge to the far side (10 minutes). Step 2: Adam crosses back to the near side (1 minute). Step 3: Adam and Carl cross the bridge to the far side (5 minutes). Step 4: Adam crosses back to the near side (1 minute). Step 5: Adam and Ben cross the bridge to the far side (2 minutes).

But 10+1+5+1+2=19 so they do not cross in time. So our intial intuition about the problem cannot be right!

Let's think about this a little harder. If Carl and Dave (the two slowest guys) cross separately, this consumes 15 minutes, which doesn't leave a lot of time for Adam and Ben to get across or the flashlight to come back on the return trips. However, if we make it so that Carl and Dave travel as a pair, this only requires 10 minutes.

Of course, we should not send Carl and Dave (the slow team) across the bridge first, because then one of them would have to carry the flashlight back, and they're kind of slow. This suggests that Adam and Ben (the fast team) should cross first (which takes 2 minutes) and then one of them should come back with the flashlight and deliver it to the slow team. But which one should return?

• If Adam returns (1 minute) and gives the slow team the flashlight, and they cross (10 minutes), then someone has to return across the bridge to give it back to Adam, the fastest choice being Ben (2 minutes). But then Adam and Ben still have to cross to the far side (2 minutes).
• If Ben returns (2 minutes) and gives the slow team the flashlight, and they cross (10 minutes), then Adam returns to give Ben the flashlight (1 minute). They cross together to the far side (2 minutes).

Either way, the whole party crosses in 17 minutes. So, here is a possible solution:

Step 1: Adam and Ben cross to the far side (2 minutes). Step 2: Adam crosses to the near side (1 minute). Step 3: Carl and Dave cross to the far side (10 minutes). Step 4: Ben crosses to the near side (2 minutes). Step 5: Adam and Ben cross to the far side (2 minutes).

(The other solution trades Steps 2 and 4.) Here are some important things to remember when solving this kind of problem: We often have an intuitive idea of the "best case" or "worst case" scenario. In this problem, you might think the "best case" scenario involves Adam going back and forth on all the trips because he is the fastest! However, the simple observation that it takes 15 whole minutes for the slower two guys to cross if they do so separately changes our whole view of the problem.

Here's some good advice. Always make sure you understand what the problem is asking. As you try to solve the problem, make note of when you think or say "It would be weird if," or "I'm sure that," or "It is probably true that." While such statements may represent strong convictions on your part, conviction does not make a proof! Finally, work backwards (say, from the assumption that Carl and Dave cross together) and use lots of paper or whiteboard to help you figure things out.

But can you prove it?

When you prove a mathematical statement, you must act as a kind of "logical lawyer" arguing your claims in the clearest, and most precise manner possible.

Good proofs do more than simply connect "what you know" and "what you want to prove" by logical implications. Rather, a good proof helps a reader understand "what is going on" in the problem. Euclid's famous proof of "there are infinitely many prime numbers" is a great example of such a proof because it illustrates in detail a process whereby we can produce evidence for a "new" prime given a finite set of "old" primes. This allows the reader to work examples that will enhance his/her understanding of how number theory actually works.

There are many ways to make your proofs better in this regard: (1) Use words. A string of symbols is not only difficult to read, it is annoying to grade. (2) Comment. For example, it is sometimes a good idea to explain a strategy at the outset so that readers have a good idea of how you intend to go about your proof. (3) Proofread. Read over your proof and verify that everything makes sense and that all your implications are actually true. Play the Devil's advocate, because you can be sure that your graders will.

There are many things to avoid doing in a proof:

• Do NOT cite a list of high-end theorems and then claim that the theorems and their proofs contain all the necessary information to derive a proof. This may be technically true, but it is completely worthless to both the author and the reader.
• Do NOT "prove by example." Unless they exhaust all cases, working small examples does not constitute a proof.
• Along the same vein, do NOT neglect to cover all the possible cases in a problem. If your proof involves a case breakdown, it is a very good idea idea to enumerate all the possible cases before you start writing anything up.
• Do NOT prove an implication in the wrong direction. This happens a lot in Concepts homework: "Assume that and are true. Then is true." This is logically unsound in the worst possible way. Always make sure you have proven what you meant to.
• Do NOT attempt to exhaust the reader with an overly long proof. Try to be as brief as possible without sacrificing clarity.
• Do NOT argue that your claim is "clear" or "obviously true." Do NOT leave the proof as an "exercise to the reader."
• Do NOT argue that a claim holds by assuming that it is true in the first place.
• Do NOT argue that a claim holds "by definition" when it does not.

Another thing to avoid is "cumbersome notation." While it is largely a matter of taste, there are some definite things you can do to clean up notation: Do not use double (triple, etc.) subscripts or superscripts unless absolutely necessary (i.e. when talking about entries in a matrix). Avoid using Greek letters until the Roman alphabet has been exhausted. Not every quantity needs its own name.

Writing good proofs is best achieved through practice, but if you follow the above advice, your life in 251 will be much easier!