Applications: Proof Techniques

A direct proof starts from what is given and reaches the claim by steps that each follow from the one before. Every odd number is one more than an even number, so one letter describes all four house numbers at once, and a total with a factor of 8 is a multiple of 8 whatever the letter stands for.

1. Write the smallest house number as 2n + 1, where n is a whole number with n ≥ 0. Neighboring houses on the north side differ by 2, so the four numbers are 2n + 1, 2n + 3, 2n + 5 and 2n + 7.
2. Add them. The four 2n terms give 8n, and the numbers left over give 1 + 3 + 5 + 7 = 16, so the total is 8n + 16.
3. (a) Take out the common factor 8: the total is 8n + 16 = 8(n + 2). Since n + 2 is a whole number, the total is a multiple of 8 for every choice of four neighboring houses, which proves the claim.
4. For a total of 136, solve 8(n + 2) = 136. Divide both sides by 8 to get n + 2 = 17, so n = 15 and the smallest number is 2 × 15 + 1 = 31. The houses are 31, 33, 35 and 37.
5. (b) The player picked houses 31, 33, 35 and 37. A total of 100 cannot be right, because every total is a multiple of 8 and 100 ÷ 8 = 12.5 is not a whole number. Check: 31 + 33 + 35 + 37 = 136.

answer(a) The total is 8n + 16 = 8(n + 2), a multiple of 8 for every whole number n; (b) houses 31, 33, 35 and 37; a total of 100 cannot be right, since 100 is not a multiple of 8

techniqueDirect Proof

examsGCSE Higher

A statement and its contrapositive are true or false together, so proving one proves the other. The conclusion here is "at least one invoice is large", which is awkward to reach directly, while its negation, "every invoice is small", gives inequalities that can simply be added.

1. The statement is: if the total is $10000 or more, then at least one invoice is $5000 or more. The contrapositive swaps the two parts and negates both: if both invoices are under $5000, then the total is under $10000.
2. Prove the contrapositive. Let the invoices be a and b dollars, with a < 5000 and b < 5000. Adding the two inequalities gives a + b < 10000, so the total is under $10000. This proves the contrapositive, and with it the original statement.
3. (a) In dollars and cents, the largest amount under $5000 is $4999.99, so the largest total two such invoices can have is 2 × 4999.99 = $9999.98. That is under $10000, as the contrapositive says.
4. The same argument works for any number k of invoices: if every invoice is under $2500, the total is under 2500k dollars. With k = 4 that is under $10000, so a purchase of $10000 split into 4 invoices always has an invoice of $2500 or more, and that invoice is reviewed.
5. (b) With k = 5 every invoice can be under $2500: five invoices of $2000 make 5 × 2000 = $10000. So the smallest number of invoices is 5. Check: four invoices of at most $2499.99 make at most 4 × 2499.99 = $9999.96, which is short of $10000.

answer(a) Both under $5000 means a total under $10000; the largest such total is $9999.98; (b) 5 invoices

techniqueProof by the Contrapositive · Direct Proof

examsGCSE Higher

A proof by exhaustion splits every possible case into a few kinds and settles each kind. Every whole number leaves a remainder of 0, 1 or 2 when divided by 3, and adding a strip of 3 keeps the remainder the same, so it is enough to buy the smallest size of each kind.

1. Every n ≥ 8 leaves a remainder of 0, 1 or 2 when divided by 3, so these three cases cover every group size. Find the smallest size from 8 up in each case: 9 = 3 + 3 + 3 has remainder 0, 10 = 5 + 5 has remainder 1, and 8 = 5 + 3 has remainder 2.
2. Every larger size in the same case is that smallest size plus some strips of 3. For example, a size n = 3q + 1 with n ≥ 10 is 5 + 5 with q − 3 strips of 3 added. So all three cases are covered for every n ≥ 8, which completes the proof.
3. (a) For the fewest strips, use as many strips of 5 as possible. Nine strips of 5 would be 45 tickets, too many, and eight leave 43 − 40 = 3, one strip of 3. The club buys 8 strips of 5 and 1 strip of 3, which is 9 strips.
4. Test each size below 8. Sizes 3, 5 and 6 = 3 + 3 can be bought. Sizes 1 and 2 are smaller than either strip, and 4 is neither 3 nor 5 and too small for two strips. Taking a strip of 5 from 7 leaves 2, and taking strips of 3 leaves 4 or 1, none of which can be bought, so 7 cannot be bought either.
5. (b) The club cannot buy exactly 1, 2, 4 or 7 tickets, and the largest of these is 7. Check: the proof in (a) covers every size from 8 up, so no larger size is missing from the list.

answer(a) 8 strips of 5 and 1 strip of 3, which is 9 strips; (b) 1, 2, 4 and 7; the largest is 7

techniqueProof by Exhaustion

examsGCSE Higher

The claim is about every pair of agents, so one pair that breaks it is enough to disprove it. A pair breaks it when one agent has the higher percentage on each type of call but not the higher percentage overall, and each percentage is worked out from its own counts.

1. A counterexample needs an agent who is ahead on easy calls and on hard calls but behind on all calls together. Work out each percentage from the counts.
2. Ava resolved 1820 = 90% of her easy calls and 3080 = 37.5% of her hard calls. Ben resolved 6880 = 85% and 720 = 35%. So Ava is ahead on both types of call.
3. Over all calls, Ava resolved 18 + 30 = 48 of 100, which is 48%, and Ben resolved 68 + 7 = 75 of 100, which is 75%. (a) Ava is ahead on each type and behind overall, so the figures are a counterexample and the claim is false. It happens because most of Ava's calls were hard and most of Ben's were easy.
4. Let Ben resolve x of his 80 easy calls. Ava is still ahead on easy calls when x80 < 90%, that is x < 72; the hard calls are unchanged, 37.5% against 35%. Ben is still ahead overall when x + 7 > 48, that is x > 41.
5. (b) Both hold when 42 ≤ x ≤ 71, so the smallest number is 42. Check: with 42, Ben's easy percentage is 4280 = 52.5%, below Ava's 90%, and he resolves 49 of 100 calls in all, above Ava's 48.

answer(a) Ava: 90% of easy calls, 37.5% of hard calls, 48% overall; Ben: 85%, 35%, 75%; so the claim is false; (b) 42

techniqueDisproof by Counterexample

The pigeonhole principle: if more objects are put into boxes than the boxes can hold at a given number each, some box holds more. Here the codes are the boxes and the addresses are the objects, and the number of codes comes from multiplying the choices for each character.

1. Each of the 4 characters is one of 26 letters or 10 digits, which is 36 choices, and the choices multiply: 36 × 36 × 36 × 36 = 1679616 codes.
2. With 1679616 addresses the rule could give every address its own code, so a shared code is not yet certain. With 1679617, if no code held two addresses there would be room for only 1679616, so two addresses share a code. (a) There are 1679616 codes, and 1679617 addresses make a shared code certain.
3. Suppose no code were shared by 3 or more of the 5000000 addresses. Then each code would hold at most 2, and all the codes together at most 2 × 1679616 = 3359232 addresses. That is fewer than 5000000, so some code is shared by at least 3.
4. In the same way, up to 3 × 1679616 = 5038848 addresses could be spread with at most 3 to a code, so a code shared by 4 is certain only from 5038849 addresses.
5. (b) That needs 5038849 − 5000000 = 38849 more addresses. Check: 50000001679616 ≈ 2.98, which rounds up to 3, the number of addresses on one code that is certain now.

answer(a) 1679616 codes; 1679617 addresses; (b) 2 × 1679616 = 3359232 is less than 5000000, so some code is shared by at least 3; 38849 more addresses

techniqueThe Pigeonhole Principle

The pigeonhole principle says that if more objects than boxes are placed in the boxes, some box holds at least two. The boxes here are small squares, chosen so that any two points in one square are close enough together.

1. Divide the plot into a 4 by 4 grid of squares, each 40 ÷ 4 = 10 m by 10 m. A sensor on an edge shared by two squares is counted in just one of them, so every sensor belongs to exactly one square.
2. There are 17 sensors and 16 squares. If each square held at most one sensor, there would be at most 16 sensors, so some square holds at least two.
3. Two points in a 10 m square are at most as far apart as opposite corners. By Pythagoras the diagonal is √10² + 10² = √200 ≈ 14.14 m. (a) The two sensors in one square are at most 14.14 m apart, which is within 15 m, so they can pass readings.
4. Suppose every square held at most 2 sensors. Then there would be at most 2 × 16 = 32 sensors. So 33 sensors force some square to hold at least 3, while with 32 the farmer could place exactly 2 in each square.
5. (b) The smallest number is 33. The three sensors in one square are each within 14.14 m of the other two, so one sensor can reach two others. Check: 3316 ≈ 2.06, which rounds up to 3.

answer(a) Some small square holds two sensors, which are at most 14.14 m apart; (b) 33 sensors

techniqueThe Pigeonhole Principle

To prove that something exists and is unique, show that at least one exists and then that there cannot be two. Here the gap between the hikers changes sign between the start and the end, so it is zero somewhere, and it only ever grows, so it is zero only once.

1. Measure both hikers from the foot of the trail. Ben is 12 − 3h km from the foot, so the gap, Ana's distance minus Ben's, is g(h) = 3.5h − h²4 − (12 − 3h) = 6.5h − h²4 − 12. They are at the same place exactly when g(h) = 0.
2. At 6:00 am, g(0) = −12: Ben is 12 km higher, at the hut. At 10:00 am, g(4) = 26 − 4 − 12 = 10: Ana is 10 km from the foot and Ben is at the foot, so Ana is 10 km higher. Neither can jump along the trail, so the gap changes from −12 to 10 without a break and must pass through 0: they meet at least once.
3. Ana only moves up the trail and Ben only moves down it, so Ana's distance from the foot only increases and Ben's only decreases. The gap therefore only increases and can be 0 at most once. (a) They are 12 km apart at 6:00 am with Ben higher and 10 km apart at 10:00 am with Ana higher, and they pass exactly once.
4. Solve g(h) = 0. Multiply by −4: h² − 26h + 48 = 0, which factorizes as (h − 2)(h − 24) = 0. The root h = 24 is long after Ben's 4 hours of walking, so it is rejected, which agrees with the single meeting found in (a).
5. (b) They pass at h = 2, which is 8:00 am. Ana is then 3.5 × 2 − 2²4 = 7 − 1 = 6 km from the foot. Check: Ben has walked 3 × 2 = 6 km down from the hut, so he is 12 − 6 = 6 km from the foot as well.

answer(a) 12 km apart at 6:00 am with Ben higher, and 10 km apart at 10:00 am with Ana higher, so they pass exactly once; (b) at 8:00 am, 6 km from the foot

techniqueProving Existence and Uniqueness

Existence and uniqueness are proved separately. A shortage at one price and a surplus at another show that the two amounts are equal somewhere between them. Assuming two such prices and reaching a contradiction shows there is only one, and solving the equation then finds it.

1. Let the shortage be the amount wanted minus the amount brought: E(p) = 720p − (15p + 30). The two amounts are equal exactly when E(p) = 0.
2. At $2 per kg, E(2) = 360 − 60 = 300: shoppers want 300 kg more than growers bring. At $12 per kg, E(12) = 60 − 210 = −150: growers bring 150 kg more than shoppers want. E changes without jumps for positive prices, so it passes through 0 between $2 and $12, and at least one such price exists.
3. Suppose two prices p₁ < p₂ both made the amounts equal. The higher price brings more, 15p₂ + 30 > 15p₁ + 30, and is wanted less, 720p₂ < 720p₁. Then 720p₂ < 720p₁ = 15p₁ + 30 < 15p₂ + 30, so the amounts are not equal at p₂, a contradiction. (a) There is a shortage of 300 kg at $2 and a surplus of 150 kg at $12, and exactly one such price.
4. Solve 720p = 15p + 30. Multiply both sides by p: 15p² + 30p − 720 = 0. Divide by 15: p² + 2p − 48 = 0, so (p + 8)(p − 6) = 0. A price cannot be negative, so p = −8 is rejected and p = 6.
5. (b) The price is $6 per kg, and the amount sold is 15 × 6 + 30 = 120 kg. Check: shoppers want 7206 = 120 kg, the same amount.

answer(a) A shortage of 300 kg at $2 and a surplus of 150 kg at $12; exactly one price; (b) $6 per kg, with 120 kg sold

techniqueProving Existence and Uniqueness

A bijection pairs the members of two collections one to one, with nothing left over on either side, so the two collections are the same size. The matches are hard to count round by round because of the byes, but each match can be paired with something that is easy to count.

1. Every match has exactly one loser. In a knockout a player loses at most once, because a loss ends that player's tournament, so different matches are paired with different players.
2. Every player except the champion loses exactly once, because play goes on until only the champion is left. So the players paired with a match are exactly the 37 − 1 = 36 who are knocked out, and each of them is paired with exactly one match.
3. (a) The pairing is a bijection between the matches and the 36 players knocked out, so 36 matches are played, however the byes fall. Check: with 32 players and no byes the rounds have 16 + 8 + 4 + 2 + 1 = 31 matches, one fewer than the number of players.
4. In the double-elimination tournament, pair each match with the loss it hands to its loser. Every match hands out exactly one loss, and every loss comes from exactly one match, so the number of matches equals the total number of losses.
5. (b) The 36 players who leave have lost 2 matches each, and the champion lost 1. The total number of losses is 36 × 2 + 1 = 73, so 73 matches are played.

answer(a) 36 matches; (b) 73 matches

techniqueCounting by a Bijection

A bijection between two collections shows they are the same size, so a count that is hard to do directly can be done on a collection that is easier to count. A box is fixed by four numbers that add up to 12, and a row of dots and dividers records exactly those four numbers.

1. Write a box as a row: a dot for each glazed donut, a divider, a dot for each chocolate one, a divider, the jam, a divider, and the cinnamon. For example, 3 glazed, 0 chocolate, 5 jam and 4 cinnamon is 3 dots, two dividers side by side, 5 dots, a divider and 4 dots.
2. This is a bijection. Each box gives exactly one row, and each row of 12 dots and 3 dividers gives back exactly one box: count the dots before the first divider, between the first and second, between the second and third, and after the third. So the number of boxes equals the number of rows.
3. A row has 12 + 3 = 15 places, and it is fixed by choosing which 3 of them hold the dividers. (a) The number of boxes is 153 = 15 × 14 × 133 × 2 × 1 = 455.
4. For a box with every flavor, put one donut of each flavor in first. That leaves 12 − 4 = 8 donuts to choose freely, so these boxes match one to one with boxes of 8 donuts that may leave out a flavor.
5. (b) A row of 8 dots and 3 dividers has 11 places, so there are 113 = 11 × 10 × 93 × 2 × 1 = 165 boxes with every flavor. Check: these boxes also match cutting a line of 12 dots at 3 of the 11 gaps between them, which again gives 165.

answer(a) 455 boxes; (b) 165 boxes

techniqueCounting by a Bijection