Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Much of being a good problem-solver is utilizing clever strategies to make the solution to the problem more accessible. One of the most useful of these strategies is to simplify the problem. There are a number of different simplifications that will lead to progress towards the solution. One of these is to simply restate or rephrase the problem in terms that are more understandable. In mathematics and computer science, you will use techniques described as divide-and-conquer, decrease-and-conquer, and transform-and-conquer, but we’re going to talk about them here under the general banner of “simplify.”

Another way to simplify a problem is to solve a simplified version of a more difficult problem. This often allows connections and insights into the solution of the problem as stated. It’s really important, however, to make sure that you are still solving the same problem. There is an old joke about a man who leaps out of a plane with a parachute and an instructor. They pass through 10,000 feet and the instructor says “Open the chute!” The man does nothing. They pass through 5,000 feet and the instructor screams “Open the chute!” The man still does nothing. They get to around 100 feet and the instructor says “Are you mad!” The man replies “No, I’m going to wait until I get to 6 feet because I can jump down from there.”

FormalPara Student Pitfall

Students will often try to solve a simpler problem, rather than a simpler version of the same problem. Watch carefully for excessive assumptions that make the problem trivial. Students can become very defensive when this is addressed so be ready to explain why a given assumption is a step too far. (Like waiting until 6 feet so you can jump!)

Yet another way to simplify a problem is to assume a value for missing information and then do the problem with that information. This often leads to progress towards the solution.

FormalPara Student Pitfall

Many challenging problems seem completely intractable at first glance. It is not uncommon for students to dislike problems that are unfamiliar to them. In fact, some completely shut down when presented with a new problem, often saying something like, “How do you expect us to do the problem if you don’t show us how?” We have also heard, “It’s the teacher’s job to show us how to do the problems.” As the teacher, your goal should be to convince the students that solving new problems is a key skill for success in today’s society. The formal term for this, in terms of Perry’s classification of how students gain knowledge, is dualism. Students require an authority and, if you won’t dole out easy answers the moment they get stuck, may make the mistake of assuming that your lack of cooperation indicates a lack of knowledge! One of the key skills a teacher has to develop, when using puzzle-based techniques, is a way to get the class working on the problems on their own and resisting the urge to give out early answers.

The unfamiliarity and challenge of a large and intimidating problem can cause students to “freeze up” for two reasons: firstly, because they require too much thought, and secondly because they require too much action. Cognitive and kinetic load combined can be very discouraging for students. Not only does a simpler version of a problem allow students to reach solutions more easily, it also limits the amount of time that has to be spent in the search for the solution and reduces any associated physical activity as well.

FormalPara Teacher Tip

Pitching the load at the right level for your class will greatly increase the number of active and engaged students that you will work with. Set the bar too low and problems become trivial, with little satisfaction gained by solving them. Set the bar too high, and load issues mean that frustration and disappointment will dominate your class. The younger the class, the simpler the problem, but, very importantly, the converse is not true! An older class may not have the background, patience, or training to sit and experiment with a large complex problem for 30 minutes. Watch carefully for signs of fatigue, boredom, or general disengagement and use this to try and match the load of the puzzles to the capacity of your class.

Simplification can take several forms. In some cases, we can reduce the problem to less confronting number of possibilities. In other cases, a simple change of representation can yield results. Simplification is a powerful and useful mathematical technique that we will not address here mathematically, but we will provide some basic guidelines for applying it generally:

  1. 1.

    Can we reduce the problem to a much smaller problem and still solve the same problem? (This is called instance simplification.)

  2. 2.

    Can we turn complicated or hard to understand concepts into simpler ones? (Can we make a representation change?)

  3. 3.

    Can we move the problem from one that we don’t know how to solve into something that we do know how to solve? (Can we carry out problem reduction?)

Our fearless skydiver from the joke was (badly) applying our third principle of simplification. Rather than deal with the bigger problem, he opted to solve a problem he already understood and could solve. Physics, of course, had other ideas.

This chapter contains a collection of problems that were specifically designed to demonstrate to the student that simplification is a powerful problem-solving tool.

We start with a classic that can certainly cause consternation in students that lack the ability to simplify.

FormalPara Problem 9.1

A man stands in front of a picture of a man and says, “Brothers and sisters I have none, but this man’s father is my father’s son.” Who is in the picture?

FormalPara Discussion 9.1

As the problem is stated, it usually requires multiple readings before the student can even begin to solve the problem.

FormalPara Teacher Tip

Many students will guess at the answer to this problem simply because there are not many possibilities. You will often get students quickly shouting out answers like stepbrother, uncle, himself, his son, his father, and perhaps others. Try to get the students to understand that guessing the answer does not develop problem-solving ability. No answer should be accepted without clear explanation – even if it is a correct guess.

This one becomes a lot easier to understand when the last phrase, “my father’s son,” is replaced by the word “me.”

So, the simplified version of the same problem is, “brothers and sisters I have none, but this man’s father is me.” This can even be simplified further by considering only the phrase, “This man’s father is me.” With this simplification, it is clear that the man in the picture is his son. Without this simplification, the problem is difficult for the students to wrap their heads around.

FormalPara Problem 9.2

A young woman is in the second day of a job interview for the position of scientist at a multinational chemical company. She is in a conference room with three senior scientists at the company who want to test her problem-solving ability. The senior scientist shows her a standard deck of 52 cards in which 19 of the cards are face up. He shuffles the deck several times and then blindfolds her (with a pair of safety goggles that have been painted black). He then shuffles the deck a couple more times and then places it in her hands, informing her that the challenge is to separate the deck into two piles, each with the same number of cards that are face up. She thought in silence for a couple of minutes, barely moving a muscle. Then, her fingers started slowly moving the cards across the top of the deck. She then placed two piles on the large oak table – each with the same number of face-up cards. How did she do it?

FormalPara Discussion 9.2

This is a great example of a problem that seems impossible but yields readily to a person who knows how to simplify.

When considering a deck with 19 face-up cards and 33 face-down cards, it is very difficult to make any headway on this problem. Let’s tackle a much simpler version of the same problem. How about a deck with two cards, one of which is face up? The only way to make two decks with two cards is with one card in each deck. When there are two cards on the table, one of which is face up and the other of which is face down, it is not hard to see that flipping over either card will produce two piles each with the same number of face-up cards. When one card is flipped, either both are face up or both are face down. In both cases, the number of face-up cards in each pile is the same.

This relatively simple observation actually represents significant progress towards the solution that would not have been made while trying to tackle the problem as stated.

Now let’s consider a total of three cards, one of which is face up. We can make two piles by placing one card in the first pile and two cards in the second pile. One of the three is face up and, blindfolded, we don’t know which one. However, flipping over the lone card in the first pile will ensure that the two piles have the same number of face-up cards.

It might also be prudent to consider also a case with three cards, two of which are face up. To figure out what to do here, split the three cards into two piles as we did before. There are two possibilities, either the lone card is face up or the lone card is face down. Here we need to flip the pile with the two cards in it. This will ensure that both piles have either no face-up cards or both have one face-up card.

Now let’s consider a standard 52-card deck with only one face-up card. The same principle applies. We put one card in the first pile and the rest in the second pile. By flipping the lone card in the first pile, we ensure that there will be the same number of face-up cards in each pile. If the lone card in the first pile happened to be the lone face-up card, then all the cards will be face down and both piles will have zero cards face up. If the card in the pile was face down, then both piles will have only one card that is face up.

As a last stepping-stone towards the solution, let’s consider a 52-card deck with two face-up cards. Let’s start by separating the deck into a pile of two cards and a pile of 50 cards. It is possible that the two-card pile contains the two face-up cards, one face-up card and one face-down card, or two face-down cards. In each of these three cases, flipping over the two-card pile will result in two piles with the same number of face-up cards.

So, the young woman in the job interview counted off the top 19 cards, flipped those 19 cards and placed them on the table. Then she placed the remaining 33 cards on the table next to it.

This is a true story, and she got the job.

FormalPara Teacher Tip

It would be a good idea for the students to confirm that this would work for a range of possible face-up cards among the 19 that the candidate flipped. For example, if 9 of the 19 cards in the first deck were face up, there would be 10 face-up cards in the second deck. Flipping the entire 19-card deck will result in ten face-up cards in the first deck as well.

FormalPara Problem 9.3

A child leaves his home and rides his bike to the store, averaging 15 km/h. When he comes out of the store, he sees that he has a flat tire and walks the bike back home at a constant speed of 5 km/h. Assuming that he takes the same path, what is his average speed for the back-and-forth trip?

FormalPara Discussion 9.3

This puzzler will stymie many students because there is a variable missing – the distance between the child’s home and the store. An experienced problem-solver will simply make up a value for the missing parameter to move the problem forwards. Further, the experienced problem-solver will select a value that is very convenient. In this case, the distance of 15 km from the home to the store is a good choice.

FormalPara Student Pitfall

Students have a tendency to plus numbers into equations to get answers. The equation relating average speed, distance traveled, and time taken is x = vt. The students have only the average speed and, without the distance or the time, many will claim that the problem can’t be done.

With an assumed distance of 15 km, the average speed can be determined by dividing the total distance of 30 km by the time it takes the child to bike there and walk the bike back. At 15 km/h, it will take the child 1 hour to get to the store, and at 5 km/h, it will take the child three hours to walk back. So the average speed is:

$$ v=\frac{30\kern0.37em \mathrm{km}}{4\kern0.37em \mathrm{hours}}=7.5\kern0.37em \mathrm{kph} $$

Does this work for all distances? Let’s use the variable x as the distance from the home to the store. Therefore, the total distance traveled is 2x. The time it takes for the child to bike to the store is x/15 km/h, and the time it takes for the child to make the return trip is x/5 km/h. So, the total time traveled is:

$$ t=\frac{x}{15\kern0.37em \mathrm{kph}}+\frac{x}{5\kern0.37em \mathrm{kph}}=\frac{4 x}{15\kern0.37em \mathrm{kph}} $$

The average speed is the distance traveled divided by the time taken:

$$ \overline{v}=\frac{2 x}{4 x/15\kern0.37em \mathrm{kph}}=\frac{30\kern0.37em \mathrm{kph}}{4}=7.5\kern0.37em \mathrm{kph} $$

So, the average is 7.5 km/h irrespective of the distance between the home and the store.

Making up values for missing information won’t always lead to the correct answer, but it is a valuable problem-solving technique because it often can provide insights into the solution to the problem.

FormalPara Problem 9.4

There is a 2-meter long, one-lane vine on which there are 100 tiny ants. Sixty are traveling to the left and 40 are traveling to the right. Each ant moves at a constant speed of 2 cm/second. When ants collide on the vine, they immediately reverse direction. If they reach either end of the vine, they keep going away from the vine. What is the longest time you will have to wait before all of the ants have left the vine?

FormalPara Discussion 9.4

After a quick read of this problem, the students may start a classroom coup, as it appears exceedingly difficult. However, a clever simplification renders it almost trivial. The key is to realize that there is no difference between ants going through one another when they collide and two ants reversing directions when they collide. Once this simplification is made, the problem is reduced to the question, “What is the maximum time it would take for an ant to walk off a 2-meter long vine if it was traveling at a speed of 2 cm/second?” The answer is 100 seconds and that is the answer to the problem as posed.

FormalPara Problem 9.5

Ten pirates have plundered a ship and discovered 100 gold pieces. They need to divide the loot among themselves. They want to be fair and abide by the law of the sea: to the strongest go the spoils. They have an arm-wrestling match to determine how strong each pirate is and then sort themselves from weakest to strongest. No two pirates are equally strong so there is no doubt about the order. We can label the pirates from weakest to strongest as P1, P2, and so forth, up to P10. The pirates also believe in democracy, and so they allow the strongest pirate to make a proposal about the division, and everyone votes on it, including the proposer. If 50 % or more of the pirates vote in favor, then the proposal is accepted and implemented. Otherwise, the proposer is thrown overboard, into the shark-infested waters, and the procedure is repeated with the next strongest pirate.

All pirates like gold (a lot!), but they hate sharks even more than they like gold. So any one of them would rather stay on board the ship and get no gold than be thrown overboard to the sharks. All the pirates are rational, and they know that if they damage any of the gold pieces (e.g., by trying to divide them into smaller pieces), then the bullion will lose almost all of its value. Finally, the pirates cannot agree to share pieces, as they do not trust each other.

What proposal should the strongest pirate propose to get the most gold?

FormalPara Discussion 9.5

The strongest pirate may start with something along the lines of “we get 10 coins each.” While a group of students voting for this might support the arrangement, it’s important to remind them that pirates are greedy, and, while they are sensibly scared of sharks, any pirate who reasonably thinks he/she can get more gold will vote against the proposal. When reminded of this, the strongest pirate may then keep more gold and divide the rest (without fractions) to the rest but it’s rare for students to get the solution immediately.

FormalPara Teacher Tip

This problem can be very rewarding if you split the students up into groups of the right size and get them to work through the solution. (If you have smaller groups, then, once you are familiar with the concepts, you could vary the number of pirates or gold to reflect the number of students you have.)

FormalPara Discussion 9.5 (cont)

Working through the solution is often easiest if we start with the simplest case: a single pirate. In this case, the single pirate is the strongest pirate, and assuming he votes for his own strategy of keeping everything, he walks away with 100 gold pieces.

So, let us start at the second simplest case, when there are just two pirates, P1 and P2. In that case, the strategy of the strongest pirate, P2, is obvious: propose 100 gold pieces for himself, and none for P1. His vote would carry 50 % of the vote necessary for the acceptance of the proposal and he would be one rich pirate!

FormalPara Student Pitfall

The biggest mistake most students make is that when they extend to two pirates, they forget that a successful vote only requires 50 % of the pirates to agree.

FormalPara Discussion 9.5 (cont)

Now we can consider the case with three pirates. Note that pirate P1 knows (and P3 knows that P1 knows!) that if P3’s proposal is turned down, the procedure would proceed to the two-pirate stage where P1 gets nothing. So P1 would vote for absolutely any proposal from P3 that gets him something. Knowing then that the optimal strategy for P3 is to use a minimal amount of gold to bribe P1 to secure his vote, P3 should propose 99 gold pieces for himself, 0 for P2, and 1 gold piece for P1.

The strategy of P4 in the scenario with four pirates is similar. As he needs 50 % of the vote, he needs a vote of one additional pirate. Again, he should use a minimum amount of gold to secure this vote, so his proposal is 99 gold pieces for himself, 0 for P3, 1 gold piece for P2, and 0 for P1. Of course, P2 would be happy to vote for this proposal; otherwise, P4 is thrown overboard, the procedure reduces to three pirates, and P2 gets nothing.

Now, the strategy of P5 in the scenario of five pirates is just slightly different. He needs two additional votes from his fellows. Thus, he proposes 98 gold pieces for himself, 0 for P4, 1 gold piece for P3, 0 for P2, and 1 gold piece for P1. Clearly, the votes of P3 and P1 are secure, because in the four-pirate scenario, they would get nothing.

It is straightforward now to design a proposal for P6 in a six-pirate scenario, for P7 in a seven-pirate scenario, etc. In particular, the proposal for P10 is: 96 gold pieces for himself, 1 gold piece for each of the pirates P8, P6, P4, and P2, and none for the rest. This solves the small version of the puzzle. It is good to be the strongest pirate, at least when there is a small number of pirates and a lot of gold.

FormalPara Teacher Tip

At this stage, consider taking the students to “the next level” and move to the larger version of this puzzle, leaving all the assumptions as they were but increasing the number of pirates to 500. The same pattern emerges, but there is a catch, because it only works only up to the 200th pirate. P200 will offer 1 gold piece for himself, 1 gold piece for each even-numbered pirate, and none for the rest. And that is when the fun starts in this larger version of the problem.

FormalPara Discussion 9.5 (cont)

P201 still can follow the previous strategy except that he runs out of gold and he proposes nothing for himself. So he proposes 1 gold piece for each odd-numbered pirate from P199 to P1. In that way, he gets nothing but at least he stays on board and avoids being eaten by sharks.

P202 also gets nothing. He has to give all 100 gold pieces to 100 pirates and stay dry. The selection of these pirates is not unique, as there are 101 pirates who are willing to accept the gold (pirates who do not get anything in the 201-pirate scenario), so there are 101 ways to distribute these bribes.

What about the 203-pirate scenario? This pirate must get 102 votes for his proposal including his own vote and he does not have enough gold pieces to give to 101 of his fellow pirates. So P203 will go overboard regardless of what he proposes! Too bad for him.

This is important for P204 though, as he knows that P203 would vote for anything to save his life! So P204 can count on P203 no matter what he proposes. That makes his task easy, as he can count on P203, himself, and 100 fellows that get a gold piece each, so he can secure 102 votes. Again, the recipients of the gold should be among the 101 pirates who would receive nothing under P202’s proposal.

The pirate P205 in the 205-pirate scenario faces an impossible task. He cannot count on P203 or P204 for support: each will vote against him to save themselves. So P205 will be thrown overboard no matter what he proposes. The moral is do not be the strongest in a group of 205 democratic pirates. The same fate awaits P206: he can be sure of P205’s vote, but that is all he can count on, so overboard he goes. Similarly, P207 faces a soggy end to his existence, as he needs 104 votes: his own, 100 from the gold, and 3 additional followers. He can get votes from P205 and P206, but these are not enough, so overboard he goes.

The fate of pirate P208 is different, as he also needs 104 votes, but P205, P206, and P207 will vote for him to save their lives! With his own vote and 100 votes, his proposal will be accepted and he will survive. Of course, the recipients of his gold must be among those who would get nothing under P204’s proposal: the even-numbered pirates P2 through P200, and then P201, P203, and P204.

Now, we can see the pattern, which continues indefinitely. Pirates who are capable of making successful proposals (even though they get no gold from their proposals, but at least they get to stay on the ship) are separated from one another by ever longer sequences of pirates who would be thrown overboard no matter what they propose! So the pirates who can make a successful proposal are P201, P202, P204, P208, P216, P232, P264, P328, P456, and so on (i.e., pirates whose number equals 200 plus a power of 2).

It is also easy to see which pirates receive the gold. As we saw before, the solution is not unique, but one way to do this is for P201 to offer gold to the odd-numbered pirates P1 through P199, for P202 to offer gold to the even-numbered pirates P2 through P200, for P204 to the odd numbers, for P208 to the even numbers, and so on, alternating between even and odd.

So, as the puzzle clearly illustrates, being the strongest and having a chance to put forwards the first proposal is not always the best (unless, of course, the number of pirates is quite small; sometimes, it is good to be a big fish in a small pond!).

The last problem in this section is one in which the simplification strategy is almost essential as it reduces the difficulty of the problem by at least an order of magnitude.

FormalPara Problem 9.6

Imagine a village of one-eyed aliens who are very logical, but have an unusual cultural tradition regarding the color of their eye – which is known to be either brown or blue. If any member of the community can logically deduce their eye color, they have to leave the village forever after making the announcement that they have figured out the color of their eye (at the daily meeting, which is mandatory for everyone in the village). The village is isolated with no contact with the outside world and they have no mirrors or reflecting surfaces. Let’s say that there are 5 blue-eyed aliens and 25 brown-eyed aliens in this village. One day, a visiting anthropologist addresses them at their daily meeting and says, “My word, your blue and brown eyes are beautiful!” There was a collective gasp among the aliens because she mentioned eye color. It would be natural to think that no harm was done as a result of this announcement because every member of the community already knew this – any blue-eyed alien could see 4 blue eyes and 25 brown eyes, and any brown-eyed alien could see 5 blue eyes and 24 brown eyes. However, the village will be empty within a week. Why?

FormalPara Discussion 9.6

This puzzler stymies a person without a lot of experience solving problems. After all, everyone in the community already knew that there were both blue-eyed and brown-eyed members. Without experience in tackling new, unstructured puzzles, it is a challenge to make any progress whatsoever on this classic.

FormalPara Teacher Tip

In order to convince the student the value of simplification, it is best to let them struggle with the problem as it stands. You can attempt to solve the problem as an entire class in a brainstorming session or you can break the class up into smaller groups. They are very unlikely to make any progress on this one without simplifying it (or googling it on their PDA).

This problem will not easily yield to a direct attack. To slay this one, it helps to start with a much simpler version. What if there was only one blue-eyed alien? Here the answer is straightforward. The lone alien with a blue eye must know he is blue as soon as the anthropologist reveals that they have both blue and brown eye color among them. The reason is, of course, that the alien with a blue eye sees no one else with a blue eye. Since he knows his eye color, he must announce this fact at the daily meeting the next day and say his goodbyes. As soon as he leaves, all the other members know they are brown because the only way the lone blue-eyed alien would know he is blue immediately after the anthropologist’s remark is if he saw no other alien with a blue eye. Therefore, the rest of the community leaves on the second day.

Of course, we don’t have the solution to the original problem yet because with only one alien with a blue eye. Nevertheless, we have made progress. Now, what if there were only two aliens with a blue eye?

Addressing the situation in which there are 2 blue-eyed aliens and, say, 28 with brown eyes, no one would leave at the first daily meeting after the anthropologist makes her announcement. However, both blue-eyed aliens are expecting that the other blue-eyed alien will leave because they see only one blue eye. When the two blue-eyed aliens see that the other blue-eyed alien did not leave on the first day, they conclude that they must have a blue eye as well and they leave together on the second day. When the two blue-eyed aliens leave on the second day, the rest of the community realizes that they must have a brown eye and they all leave on the third day.

With three blue-eyed aliens and the rest brown-eyed, the whole process is delayed by a single day. Let’s consider the point of view of a blue-eyed alien when there are a total of three aliens with blue eyes. He could guess that he has a brown eye because he is looking at 27 brown eyes and 2 blue eyes. He would also reason that the two blue-eyed aliens he can see would not be able to figure out that they have a blue eye until the second day. However, when they do not leave on the second day, he must conclude that the only reason they did not leave is that he has a blue eye as well. The other two blue-eyed aliens reason similarly and the three leave together on the third day. On the fourth day, all the brown-eyed aliens abandon the island because they realize their eye must be brown.

So, in the original problem, the answer is that the 5 blue-eyed people leave on the fifth day and the remaining 25 brown-eyed people leave the day after.

FormalPara Teacher Tip

Consider to challenge the students with the following question: “What new information from the anthropologist doomed the community?” This is discussed in Problem 15.7.

FormalPara Debriefing

The simplification technique should be a tool in every problem-solver’s toolbox. The simplification technique is a very useful technique to apply when the problem is too difficult to attack as it is stated.