Problem Solving · applications

Applications: Problem Solving

10 question types · Pre-University · each worked step by step with a figure that follows the steps

01

A Game of Taking 1, 3 or 4 Counters from a Pile, and the First Move from a Pile of 26

methodLabel Each Pile Winning or Losing, Starting from the Empty Pile and Working Up, Then Look for a Repeating Pattern

Two players share a pile of counters. They take turns, and on each turn a player removes 1, 3 or 4 counters from the pile. The player who takes the last counter wins. Call a pile size losing if the player about to move loses when both players play as well as possible, and winning otherwise. (a) Working backwards from a pile of 0, find every losing pile size from 0 to 14. (b) A game starts with 26 counters and you move first. How many counters should you take, and what pile does that leave for your opponent?

0123456789101112131415161718192021222324252627Red: losing for the player to move. Green: winning.
An empty pile is lost for the player to move. Piles of 1, 3 and 4 are taken in one move.
A pile of 0 is losing: the player to move has nothing to take, because the opponent has just taken the last counter. Piles of 1, 3 and 4 are winning, because one move takes every counter.
step 1 of 6

The end of the game is the one position that is completely known: a player facing an empty pile has lost, because the opponent took the last counter. Working backwards from there, a pile is winning if some move leaves a losing pile, and losing if every move leaves a winning pile. Each label uses only labels already found for smaller piles.

  1. A pile of 0 is losing: the player to move has nothing to take, because the opponent has just taken the last counter. Piles of 1, 3 and 4 are winning, because one move takes every counter.
  2. A pile of 2 is losing: the only possible move is to take 1, which leaves the winning pile 1 for the opponent. Piles of 5 and 6 are winning, because taking 3 or 4 leaves the losing pile 2.
  3. A pile of 7 is losing, because its moves leave 6, 4 or 3, and all three are winning. A pile of 8 is winning, because taking 1 leaves 7. A pile of 9 is losing, because its moves leave 8, 6 or 5, all winning. Piles of 10 and 11 are winning: taking 1 from 10 leaves 9, and taking 4 from 11 leaves 7.
  4. (a) Piles of 12 and 13 are winning, because taking 3 or 4 leaves 9. A pile of 14 is losing, because its moves leave 13, 11 or 10, all winning. The losing piles from 0 to 14 are 0, 2, 7, 9 and 14.
  5. Whether a pile is losing depends only on the piles 1, 3 and 4 below it. Piles 7, 8, 9 and 10 read losing, winning, losing, winning, exactly as piles 0, 1, 2 and 3 do, so the labels repeat every 7 piles: a pile is losing exactly when its remainder on division by 7 is 0 or 2.
  6. (b) 26 = 3 × 7 + 5 leaves remainder 5, so it is winning. Taking 1 leaves 25 (remainder 4) and taking 4 leaves 22 (remainder 1), both winning for your opponent. Taking 3 leaves 23, remainder 2, a losing pile. Take 3 counters and leave 23. Check: from 23 your opponent can leave 22, 20 or 19, and you answer by taking 1, 4 or 3 to leave 21 or 16, both losing.

answer(a) 0, 2, 7, 9 and 14; (b) take 3 counters, leaving a pile of 23

techniqueWorking Backwards from the Goal · From a Special Case to Every Case

Common pitfalls

  • Calling a pile losing because one of its moves leads to a winning pile. A pile is losing only when EVERY move leaves a winning pile; a single move to a losing pile is enough to make it winning, as with 5, which can leave 2.
  • Using the rule for a game where a player takes 1 or 2 counters, where the losing piles are the multiples of 3. The losing piles depend on the moves allowed; here 2 and 9 are losing, and neither is a multiple of 3.
02

A Bacterial Culture That Doubles Every Hour and Is Harvested at the End of Each Hour

methodUndo Each Hour in Reverse Order, Adding Back the Harvest Before Halving, and Run the Hours Backwards from the Last One

A laboratory grows bacteria in a bioreactor. During each hour the number of cells doubles, and at the end of the hour a technician harvests 3200 million cells for testing. (a) At the end of the fourth hour, just after the harvest, the culture holds 8000 million cells. How many cells did it hold at the start? (b) For a new batch the technician needs six harvests, one at the end of each of the first six hours, and every harvest must take the full 3200 million cells. What is the smallest number of cells the new batch can start with?

Million cells at the end of each hour, after the harveststarthour 1hour 2hour 3hour 48000One hour back: add the 3200 harvested, then halve
An hour doubles the cells and then removes 3200 million, so running an hour back adds 3200 million and then halves.
Going forward, an hour takes a count of x million cells to 2x − 3200. To run an hour backwards, undo the last move first: add back the 3200 harvested, then halve. So a count of y at the end of an hour came from y + 32002 at its start.
step 1 of 5

The state at the end is known and the state at the start is not, so run the hours backwards. Each hour is two moves, doubling and then harvesting; to run an hour backwards, undo them in the opposite order. In part (b) the goal is a condition rather than a number, and it can be carried back in the same way.

  1. Going forward, an hour takes a count of x million cells to 2x − 3200. To run an hour backwards, undo the last move first: add back the 3200 harvested, then halve. So a count of y at the end of an hour came from y + 32002 at its start.
  2. Start from the end of the fourth hour. 8000 + 32002 = 5600 at the end of the third hour, 5600 + 32002 = 4400 at the end of the second, and 4400 + 32002 = 3800 at the end of the first.
  3. (a) 3800 + 32002 = 3500: the culture held 3500 million cells at the start. Check forward: 3500 → 7000 − 3200 = 3800 → 4400 → 5600 → 8000.
  4. For (b), the goal is that the sixth harvest can take the full 3200 million, so after it the count is at least 0. Run the same rule back: at least 0 + 32002 = 1600 at the end of the fifth hour, then at least 2400, 2800, 3000 and 3100 at the end of the fourth, third, second and first hours.
  5. (b) One more hour back gives at least 3100 + 32002 = 3150: the batch must start with at least 3150 million cells. Check forward: 3150 → 3100 → 3000 → 2800 → 2400 → 1600 → 0, six full harvests, the last one emptying the bioreactor. A start of fewer cells leaves every count lower, so the sixth harvest would be short.

answer(a) 3500 million cells; (b) 3150 million cells

techniqueWorking Backwards from the Goal

Common pitfalls

  • Undoing the moves in the order they happened, halving first and then adding 3200. From 8000 that gives 7200 at the end of the third hour, which is wrong: the harvest was the last thing done in the hour, so it is the first thing to undo.
  • In (b), asking for 3200 million cells at the START of each hour. The harvest comes after the cells double, so the count at the end of the fifth hour needs to be only 1600 million, and demanding 3200 gives a starting number that is far too large.
03

A Thanksgiving Dinner to Be Served at 6:00 pm, and When the Turkey and the Gravy Must Start

methodFix the Last Tasks at the Deadline and Work Back Through the Tasks, Taking the Earlier Time Where Two Tasks Wait on One

A family will serve Thanksgiving dinner at 6:00 pm. The turkey is prepared (30 minutes), roasted (3 hours), rested (30 minutes) and carved (15 minutes), in that order, each task starting when the one before it ends or later. The gravy takes 15 minutes and is made from the juices in the roasting pan, so it can start only once the roasting has finished. Several cooks share the work, so tasks that do not depend on each other can run at the same time, and everything must be finished by 6:00 pm. (a) What is the latest time the turkey's preparation can start, and how many minutes before 6:00 pm is that? (b) The turkey starts at that latest time. What is the latest time the gravy can start, and for how many minutes can it wait after the roasting ends?

Rest5:15 to 5:45Carve5:45 to 6:00Times are pm, fixed back from dinner at 6:00
Carving ends at 6:00 pm, so it starts by 5:45 pm, and resting starts by 5:15 pm.
Start from the goal. Carving takes 15 minutes and must end by 6:00 pm, so it starts by 5:45 pm at the latest. The turkey rests for 30 minutes before carving, so resting starts by 5:15 pm.
step 1 of 5

The deadline is fixed and the starting time is what is asked, so work backwards from the deadline. Each task's latest start is its latest finish minus its length, and a task's latest finish is the latest start of the task that waits on it. Where two tasks wait on the same task, it must finish in time for both, so it takes the earlier of their latest starts.

  1. Start from the goal. Carving takes 15 minutes and must end by 6:00 pm, so it starts by 5:45 pm at the latest. The turkey rests for 30 minutes before carving, so resting starts by 5:15 pm.
  2. The gravy takes 15 minutes and must also be ready at 6:00 pm, so it starts by 5:45 pm at the latest.
  3. Two tasks wait on the roasting: resting, which must start by 5:15 pm, and the gravy, which must start by 5:45 pm. The roasting must finish in time for both, so it finishes by the earlier time, 5:15 pm, and three hours of roasting start by 2:15 pm.
  4. (a) Preparation takes 30 minutes before the roasting, so it starts by 1:45 pm at the latest. That is 255 minutes before 6:00 pm. Check: 30 + 180 + 30 + 15 = 255 minutes.
  5. (b) Starting at 1:45 pm, the roasting ends at 5:15 pm, and the juices are ready then. The gravy can start at any time from 5:15 pm to 5:45 pm, so its latest start is 5:45 pm and it can wait up to 30 minutes after the roasting ends. Check: 5:45 pm plus 15 minutes is 6:00 pm.

answer(a) 1:45 pm, which is 255 minutes before 6:00 pm; (b) 5:45 pm, so the gravy can wait up to 30 minutes after the roasting ends at 5:15 pm

techniqueWorking Backwards from the Goal

Common pitfalls

  • Letting the gravy set the roasting's deadline, so that the roasting ends at 5:45 pm. The resting also waits on the roasting and must start by 5:15 pm, so the roasting has to meet the earlier of the two times.
  • Adding up every task, gravy included: 30 + 180 + 30 + 15 + 15 = 270 minutes, a start at 1:30 pm. The gravy runs at the same time as the resting and carving, so it adds nothing to the time before dinner.
04

A Round Cake Cut into Tasting Pieces with Straight Cuts, and the Cuts Needed for 50 Pieces

methodCount the Pieces for One, Two, Three and Four Cuts, Find What Each New Cut Adds, Then Add Up for n Cuts

A baker cuts a large round cake into tasting pieces for a food fair. Each cut is straight and runs right across the cake. The pieces are sold by weight, so they need not be the same size, and she places the cuts so that no two are parallel, no three pass through one point, and every crossing is inside the cake. (a) How many pieces do n cuts made in this way give? Find a formula in n. (b) What is the smallest number of cuts that gives at least 50 pieces?

1 cut2 pieces2 cuts4 pieces3 cuts7 pieces
One cut makes 2 pieces, two cuts make 4, and three cuts make 7.
Solve the smallest cases. One cut makes 2 pieces. Two crossing cuts make 4. Three cuts, each crossing the other two at different points, make 7, and four cuts make 11.
step 1 of 5

A formula for every n is hard to see at once, so solve the simplest cases first: count the pieces for one, two, three and four cuts. The counts suggest what each new cut adds, and looking at how a new cut meets the old ones explains why, which turns the pattern into a formula.

  1. Solve the smallest cases. One cut makes 2 pieces. Two crossing cuts make 4. Three cuts, each crossing the other two at different points, make 7, and four cuts make 11.
  2. The counts 2, 4, 7, 11 go up by 2, 3 and 4: each new cut seems to add one more piece than the cut before it.
  3. See why. The nth cut crosses each of the n − 1 earlier cuts once, at n − 1 different points inside the cake, and those points split it into n segments. Each segment divides one piece into two, so the nth cut adds exactly n pieces.
  4. (a) The whole cake is 1 piece before any cut, so n cuts give 1 + (1 + 2 + ⋯ + n) = 1 + n(n + 1)2 pieces. Check: n = 4 gives 1 + 10 = 11.
  5. (b) Nine cuts give 1 + 9 × 102 = 46 pieces, fewer than 50, and ten cuts give 1 + 10 × 112 = 56 pieces. The smallest number of cuts is 10.

answer(a) 1 + n(n + 1)2 pieces; (b) 10 cuts, since nine cuts give only 46 pieces and ten give 56

techniqueSolving a Simpler Problem First · From a Special Case to Every Case

Common pitfalls

  • Assuming each cut doubles the pieces, since 1 cut gives 2 and 2 cuts give 4. Three cuts give 7, not 8: the third cut crosses only two earlier cuts, so it passes through only three pieces.
  • Taking 2n pieces, as for cuts that all pass through the center. Cuts through one point break the rule that no three meet, and they add only 2 pieces each, so 10 such cuts give 20 pieces, not 56.
05

A Garden Path Paved with Rectangular Slabs, and the Patterns That Look the Same from Both Ends

methodCount the Patterns for the Shortest Paths, Split Every Pattern by How It Begins, Then Split the Mirror Patterns by What Covers the Middle

A garden path from the back door to the gate is 1 m wide and 5 m long. It is paved with identical slabs 1 m long and 0.5 m wide, with no gaps and no cutting. A slab can lie across the path or along it. The path has a door end and a gate end, so a pattern and its reverse count as two patterns when they differ. (a) In how many different patterns can the path be paved? (b) How many of those patterns look the same from both ends of the path?

acrossa pair alongA slab is 1 m by 0.5 m, and the path is 1 m wideA slab along covers half the width, so another lies beside it
Measure in half-meters. A slab across fills one half-meter; slabs along the path come in pairs that fill two.
Measure the path in half-meters: 5 m is 10 half-meters. Let an be the number of patterns for a path n half-meters long. A slab across the path fills 1 half-meter of its length. A slab along the path fills only half the width, so the other half beside it must also be a slab along the path: slabs along the path come in side-by-side pairs, and each pair fills 2 half-meters.
step 1 of 6

A path 5 m long has too many patterns to list, so solve shorter paths first. The short cases show how every pattern is built from a shorter one, which gives a rule that climbs to the full length. The patterns that look the same from both ends are then counted by a second, smaller problem: what happens at the middle of the path.

  1. Measure the path in half-meters: 5 m is 10 half-meters. Let an be the number of patterns for a path n half-meters long. A slab across the path fills 1 half-meter of its length. A slab along the path fills only half the width, so the other half beside it must also be a slab along the path: slabs along the path come in side-by-side pairs, and each pair fills 2 half-meters.
  2. Solve the shortest paths. a1 = 1 (one slab across), a2 = 2 (two across, or one pair along), a3 = 3 and a4 = 5.
  3. Every pattern begins either with a slab across, leaving a path n − 1 long, or with a pair along, leaving a path n − 2 long. So an = an − 1 + an − 2, and the counts run 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.
  4. (a) The path is 10 half-meters long, so it can be paved in a10 = 89 patterns.
  5. A pattern looks the same from both ends when it is its own mirror image about the middle, 5 half-meters from each end. A slab across fills a single half-meter, so it cannot lie over the middle, which falls between the 5th and 6th half-meters. Either a join between slabs lies on the middle, and the door half can be any of a5 = 8 patterns, with the gate half its mirror image; or a pair along covers the middle, and the 4 half-meters before it can be any of a4 = 5 patterns.
  6. (b) 8 + 5 = 13 of the 89 patterns look the same from both ends. Check the method on a path 4 half-meters long: it predicts a2 + a1 = 3, and of its 5 patterns exactly three read the same both ways: four slabs across, a pair along between two slabs across, and two pairs along.

answer(a) 89 patterns; (b) 13 patterns

techniqueSolving a Simpler Problem First

Common pitfalls

  • Letting a single slab lie along the path next to a slab across it. A slab along the path covers only half the width, and a slab across cannot fill the other half, so slabs along the path always come in side-by-side pairs.
  • Halving the 89 patterns to count those that look the same from both ends. Halving counts pairs of mirror images, which is a different question, and 89 is odd; the symmetric patterns are counted by what lies over the middle.
06

A Runner's Week That Adds 1 km Each Day, and Her Coach's Observations About the Total

methodTest a Few Plans, Name the Middle Day to Cover Every Plan at Once, and Pair the Days Around It

A runner's training plan for a week has her run a whole number of kilometers on the first day and 1 km more on each day after that, for seven days. Her coach has noticed on past plans that the week's total is always 7 times the distance of the fourth day. (a) Prove the coach's observation for every such plan, and use it to find the first day's distance in a week that totals 91 km. (b) For a four-day plan built the same way, the coach guesses that the total is always a multiple of 4. Test the guess on two plans, then settle it for every four-day plan.

plan, kmtotal7 × day 41 to 7287 × 45 to 11567 × 8In each plan, the total is 7 times the fourth day
Two plans: 28 = 7 × 4 and 56 = 7 × 8, where 4 and 8 are the fourth days.
Test two plans first. The plan 1, 2, …, 7 totals 28 = 7 × 4, and the plan 5, 6, …, 11 totals 56 = 7 × 8. In each, 4 and 8 are the fourth day's distances, the middle of the week.
step 1 of 6

A pattern seen in a few examples is only a guess until it is proved for every case. Testing special cases shows what to prove, and a letter for the right quantity covers every case at once. Here the right quantity is the middle day, because the other days sit symmetrically around it.

  1. Test two plans first. The plan 1, 2, …, 7 totals 28 = 7 × 4, and the plan 5, 6, …, 11 totals 56 = 7 × 8. In each, 4 and 8 are the fourth day's distances, the middle of the week.
  2. Now take every plan at once. Call the fourth day's distance m km. The seven days are m − 3, m − 2, m − 1, m, m + 1, m + 2 and m + 3.
  3. Pair the days around the middle: days 1 and 7 add to 2m, and so do days 2 and 6, and days 3 and 5. The three pairs and the middle day give 2m + 2m + 2m + m = 7m, which proves the observation for every plan.
  4. (a) A week of 91 km has 7m = 91, so m = 13 km on the fourth day and 13 − 3 = 10 km on the first. Check: 10 + 11 + 12 + 13 + 14 + 15 + 16 = 91.
  5. Test the four-day guess: 1 + 2 + 3 + 4 = 10 and 5 + 6 + 7 + 8 = 26. Neither is a multiple of 4, and both leave a remainder of 2.
  6. (b) Prove what the tests show. With a km on the first day, the total is a + (a + 1) + (a + 2) + (a + 3) = 4a + 6 = 4(a + 1) + 2. That is a multiple of 4 plus 2, so every four-day total leaves remainder 2 on division by 4, and the guess is false for every four-day plan, not only the two tested.

answer(a) The total is 7m, where m km is the fourth day's distance; the first day is 10 km; (b) the guess is false for every four-day plan: the total is 4(a + 1) + 2, which leaves remainder 2 on division by 4

techniqueFrom a Special Case to Every Case

Common pitfalls

  • Calling the observation proved because it held for the plans tried. Any number of examples covers only those plans; the total 7m covers every plan at once.
  • Expecting the four-day total to be 4 times a middle day. Four days have no middle day: the middle falls between days 2 and 3, at a + 1.5 km, so the total is 4(a + 1.5) = 4a + 6, which is never a multiple of 4.
07

Two Spreadsheet Columns Built from Powers of n, and the Largest Number That Divides Every Entry

methodRead a Candidate Off the First Few Entries, Then Prove It for Every n by Factoring and Taking Cases by Remainder

A student fills a spreadsheet column with n3 − n for n = 2, 3, 4, 5, 6 and gets 6, 24, 60, 120 and 210. (a) Find the largest whole number that divides every entry n3 − n for every whole number n ≥ 2, and prove that it does. (b) A second column holds n5 − n. Use its first entries to find the largest whole number that could divide every entry, and prove that it divides n5 − n for every whole number n ≥ 2.

nn3− nas a product261 × 2 × 33242 × 3 × 44603 × 4 × 551204 × 5 × 662105 × 6 × 7n3− n = (n − 1) × n × (n + 1)
n3 − n = (n − 1)n(n + 1), three consecutive whole numbers multiplied together.
Factor the first expression: n3 − n = n(n2 − 1) = (n − 1)n(n + 1), the product of three consecutive whole numbers. Check with n = 5: 4 × 5 × 6 = 120.
step 1 of 6

The first few entries are special cases. Any number that divides every entry must divide these, so their highest common factor is the only candidate for the largest. The candidate is then proved for every n by factoring the expression and, where a factor is not guaranteed, by taking cases by remainder.

  1. Factor the first expression: n3 − n = n(n2 − 1) = (n − 1)n(n + 1), the product of three consecutive whole numbers. Check with n = 5: 4 × 5 × 6 = 120.
  2. Of any three consecutive whole numbers, one is a multiple of 3 and at least one is even, so their product is a multiple of 2 × 3 = 6 for every n.
  3. (a) Every entry is a multiple of 6, and the first entry is 6 itself, so no larger number divides every entry. The largest is 6.
  4. For n5 − n the first entries are 25 − 2 = 30, 35 − 3 = 240, 45 − 4 = 1020 and 55 − 5 = 3120. Their highest common factor is 30 = 2 × 3 × 5, and nothing larger can divide the entry 30, so 30 is the candidate.
  5. Factor: n5 − n = n(n4 − 1) = (n − 1)n(n + 1)(n2 + 1). The first three factors make a multiple of 6, as before. For 5, take n by its remainder on division by 5. A remainder of 0, 1 or 4 makes n, n − 1 or n + 1 a multiple of 5. A remainder of 2 or 3 makes n2 + 1 a multiple of 5: (5q + 2)2 + 1 = 25q2 + 20q + 5 and (5q + 3)2 + 1 = 25q2 + 30q + 10.
  6. (b) Every entry n5 − n is a multiple of both 6 and 5, so of 30, and the entry 30 at n = 2 allows nothing larger. The largest whole number is 30.

answer(a) 6, because n3 − n = (n − 1)n(n + 1) always has a factor 2 and a factor 3; (b) 30, because n5 − n = (n − 1)n(n + 1)(n2 + 1) also has a factor 5 for every remainder of n on division by 5

techniqueFrom a Special Case to Every Case

Common pitfalls

  • Answering 6 for the second column because the first column gave 6. The first entries of n5 − n have highest common factor 30, and the cases by remainder show that 5 divides every entry as well.
  • Checking a few more entries and calling the result proved. The spreadsheet shows a candidate; only the factoring and the five remainder cases cover every n.
08

A Winter Coat Raised 25% for the Season and Cut 25% in the Sale, and a Salesperson's Claim About the Price

methodPut In the Actual Prices and Ask What Amount Each Percentage Is Taken Of

A store raised the price of a winter coat by 25% at the start of the season. In the January sale it cut the coat's price by 25%, and a salesperson told a customer: 'The price went up 25% and came down 25%, so you are paying exactly what the coat cost before the season.' Before the season the coat cost $160. (a) Find the sale price, and name the step in the salesperson's argument that fails and why. (b) By what percentage of the raised price should the store have cut the price to bring it back to exactly $160?

Before$160Raised$160+$40$200
The rise is 25% of $160, which is $40, so the raised price is $200.
Put in the prices. The rise is 25% of $160, which is $40, so the raised price is $200.
step 1 of 5

An argument about percentages can sound right and still be false, and putting in the actual amounts is the quickest way to find the false step. A percentage is always a percentage of some amount, and the same percentage of two different amounts is two different amounts of money.

  1. Put in the prices. The rise is 25% of $160, which is $40, so the raised price is $200.
  2. The sale cut is 25% of the price at the time of the sale, $200. That is $50, so the sale price is 200 − 50 = $150.
  3. (a) The sale price is $150, which is $10 less than $160. The step that fails is 'up 25% and down 25% cancel': the rise was 25% of $160 and the cut was 25% of $200, a larger amount, so the cut takes off $10 more than the rise added.
  4. To return to $160, the cut must take off exactly the $40 that the rise added. As a percentage of the price being cut, that is 40200 × 100% = 20%.
  5. (b) A cut of 20% of the raised price brings the coat back to $160. Check: 20% of $200 is $40, and 200 − 40 = 160.

answer(a) $150, which is $10 less than before the season; the claim that the two changes cancel fails, because the cut is 25% of $200 and the rise was 25% of $160; (b) 20% of the raised price

techniqueFinding the Flaw in an Argument

Common pitfalls

  • Accepting that equal percentages up and down cancel. They cancel only when both are taken of the same amount; after the rise the price is larger, so the same percentage of it is a larger amount.
  • Answering (b) with 25% because the rise was 25%. The amount to remove is $40, but it is now taken from $200, and $40 is 20% of $200.
09

A Game Designer's Points for Each Level, and an Argument by Induction That They Split Among Three Players

methodCheck the Step and the Base Case of the Induction Separately, Then Test the Claim on the First Few Levels

A game designer awards 4n + 1 points for completing level n, for n = 1, 2, 3, …, and wants every award to split equally among the 3 players of a team. She argues: 'Suppose the award at level k is a multiple of 3. The award at level k + 1 is 4k+1 + 1 = 4(4k + 1) − 3, a multiple of 3 minus 3, so it is also a multiple of 3. By induction, every award splits equally.' (a) Which part of a proof by induction is missing from her argument, and what remainder does the award at each level leave on division by 3? (b) She changes the award to 4n + c points, where c is a positive whole number. What is the smallest c for which the same kind of argument, with every part in place, proves that every award splits equally among 3 players?

The step: if 4k+ 1 is a multiple of 3,4k+1+ 1 = 4(4k+ 1) − 3 is one too
The step is correct: 4k+1 + 1 = 4(4k + 1) − 3.
Check the step. If 4k + 1 is a multiple of 3, then 4k+1 + 1 = 4 × 4k + 1 = 4(4k + 1) − 3 is a multiple of 3 minus 3, which is again a multiple of 3. The step is correct.
step 1 of 5

A proof by induction has two parts: a base case, that the claim holds for the first level, and a step, that if it holds at a level k it holds at level k + 1. A flawed induction usually has one part right and the other wrong or missing, so check each part on its own, and test the claim on the first few levels.

  1. Check the step. If 4k + 1 is a multiple of 3, then 4k+1 + 1 = 4 × 4k + 1 = 4(4k + 1) − 3 is a multiple of 3 minus 3, which is again a multiple of 3. The step is correct.
  2. Check the base case, which she never stated. At level 1 the award is 4 + 1 = 5 points, and 5 is not a multiple of 3. The step only passes the claim on from one level to the next, so with nothing true at level 1 the argument proves nothing.
  3. (a) The base case is missing, and it is false. 4 leaves remainder 1 on division by 3, so every power 4n does too, and 4n + 1 leaves remainder 1 + 1 = 2 at every level. Check: 5 = 3 + 2, 17 = 15 + 2, 65 = 63 + 2 and 257 = 255 + 2.
  4. For 4n + c, the step holds for every whole number c: 4k+1 + c = 4(4k + c) − 3c, a multiple of 3 minus a multiple of 3.
  5. (b) So only the base case decides: 4 + c must be a multiple of 3. c = 1 gives 5, which is not, and c = 2 gives 6, which is. The smallest c is 2. Check: 4 + 2 = 6, 16 + 2 = 18 and 64 + 2 = 66 are all multiples of 3.

answer(a) The base case is missing: level 1 gives 5 points, which is not a multiple of 3; every award leaves remainder 2 on division by 3; (b) c = 2

techniqueFinding the Flaw in an Argument

Common pitfalls

  • Finding the step correct and accepting the proof. A correct step shows only that the claim passes from each level to the next; without a true base case there is nothing to pass on, and here the claim is false at every level.
  • Looking for the error in the algebra 4(4k + 1) − 3. That line is correct, since 4 × 4k + 4 − 3 = 4k+1 + 1; the flaw is the missing base case, not the step.
10

A Café That Broke Even, and a Nephew's Algebra That Ends in 2 = 1

methodPut the Café's Figures into Every Line to Find the First False One, Then Ask What Each Division Assumed

A café broke even last month: its revenue R equaled its costs C, and both were $8000. The owner's nephew writes: line 1, R = C; line 2, multiply both sides by R: R2 = RC; line 3, subtract C2 from both sides: R2 − C2 = RC − C2; line 4, factor both sides: (R + C)(R − C) = C(R − C); line 5, divide both sides by R − C: R + C = C; line 6, replace R by C: 2C = C, so 2 = 1. (a) Put R = C = 8000 into every line. Which is the first false line, and why is the move that produced it not allowed? (b) The nephew then says: 'Line 2 on its own proves a month broke even, because dividing R2 = RC by R gives R = C.' Give the revenue of a month with costs of $8000 for which R2 = RC holds but the café did not break even.

Line 1: R = C so 8000 = 8000Line 2: R2= RC so 64000000 = 64000000Line 3: R2− C2= RC − C2so 0 = 0Line 4: (R + C)(R − C) = C(R − C)Line 5: R + C = CLine 6: 2C = C, so 2 = 1
With R = C = 8000, lines 1, 2 and 3 are true.
Test the first lines with R = C = 8000. Line 1 reads 8000 = 8000. Line 2 reads 64000000 = 64000000. In line 3 both sides are 64000000 − 64000000 = 0.
step 1 of 5

When an argument reaches a false conclusion, some step was not earned. Putting real numbers into every line finds the first line that is false, and the move just before it is the flaw. Dividing both sides of an equation is allowed only by a number that is not zero, so every division must be checked for what it assumed.

  1. Test the first lines with R = C = 8000. Line 1 reads 8000 = 8000. Line 2 reads 64000000 = 64000000. In line 3 both sides are 64000000 − 64000000 = 0.
  2. Line 4: the left side is (8000 + 8000)(8000 − 8000) = 16000 × 0 = 0, and the right side is 8000 × 0 = 0. Lines 1 to 4 are all true.
  3. (a) Line 5 reads 8000 + 8000 = 8000, that is 16000 = 8000, so line 5 is the first false line. It came from dividing both sides by R − C, and R − C = 8000 − 8000 = 0. Dividing by 0 is not allowed: 16000 × 0 = 8000 × 0 is true only because both sides are 0, just as 1 × 0 = 2 × 0 is, and it says nothing about 16000 and 8000.
  4. The second argument divides R2 = RC by R, which is allowed only when R ≠ 0. So try R = 0: then R2 = 0 and RC = 0 × 8000 = 0, and the equation holds.
  5. (b) A month with revenue $0 and costs of $8000, such as a month the café was closed for repairs, has R2 = RC but made a loss of $8000, so it did not break even. The correct reading of line 2 is R(R − C) = 0, so R = 0 or R = C.

answer(a) Line 5, which reads 16000 = 8000; it divides both sides by R − C, which is 0, and dividing by 0 is not allowed; (b) revenue of $0: then R2 = RC = 0, but R ≠ C

techniqueFinding the Flaw in an Argument

Common pitfalls

  • Blaming line 6, where the 2 = 1 first appears. Line 6 follows correctly from line 5; the first false line is line 5, and the move that produced it is the division by R − C = 0.
  • Blaming line 2 for multiplying by R. Multiplying both sides by any number, zero included, keeps a true equation true; it is dividing by zero that turns a true line into a false one.
Mr. Chalk Read the guide