Axiom of the empty set Wikipedia: There is a set such that no set is a member of it.1162
Notation Adding notation is typically referencing everything with regard to an origin, a reference point. We need some "notation". Let us assume that there is a universal coordinate system, such as longitude and latitude, so that we can refer to the "same" location on any planet. For example, if the planets were little balls floating in a room, the location "north pole" would mean the point on a planet which was closest to the ceiling. Given such a universal coordinate system, what can we say about a planet P which has a private point at location x? pg. 64 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1520
127 people in a tennis tournament If 127 people play in a singles tennis tournament, prove that at the end of the tournament, the number of people who have played an odd number of games is even. ... each game has exactly two people playing it... the sum counts every game that has been played exactly twice! ... the sum above is even, and is a sum of an odd number (127) of elements. If an odd number of them were odd, the sum would not be even... pg. 102, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1644
Parity problem: Dominos on a chessboard Remove the two diagonally opposite corner squares of a chessboard. Is it possible to tile this shape with thirty-one 2 x 1 "dominos"? ... At first, it seems like a geometric/combinatorial problem with many cases and subcases. But it is really just a question about counting colors. The two corners that were removed wre both (without loss of generality) white, so the shape we are interested in contains 32 black and 30 white squares. Yet any domino, once it is placed, will occupy exactly one black and one white square. The 31 dominos thus require 31 black and 31 white squares, so tiling is impossible. pg. 60 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1509
Prove that the sum of the interior angles of any n-gon is 180(n-2) degrees Weitz, pg.501499
Use of extreme principle with induction Often, problems involve the extreme principle plus a particular argument style, such as contradiction or induction. A common tactic is to use the extremes to "strip down" a problem into a smaller version ... The formal argument then uses induction. ... Several positive integers are written on a blackboard. One can erase any two distinct integers and write their greatest common divisor and least common multiple instead. Prove that eventually the numbers will stop changing. pg.85, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1633
Well-Ordering Principle Every non-empty set of positive integers has a least element. pg.83, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1631
Finite Injury Priority Method Muchnik  and Friedberg  invented a computable approximation to this forcing argument, called the finite injury method , where they allow a requirement to finitely often be injured (i.e, previous progress to be destroyed), and then they begin again to satisfy the given requirement, until after it is finally satisfied and never injured thereafter. We present finite injury priority arguments and a solution to Post's problem of c.e. sets A and B of incomparable Turing degree. Robert Soare's upcoming book, "Computability Theory and Applications: The Art of Classical Computability".1660
Infinite Injury Priority Method Shoenfield  and Sacks independently [1963a,b,c] invented the infinite injury method for computable constructions in which a given requirement may be injured infinitely often, but only computably so, and still somehow succeed. Yates, Martin, and Lachlan extended and refined this method and added others such as the minimal pair construction of a pair of noncomputable c.e. sets A and B whose degree have infimum degree 0 the degree of the computable sets. By the end of the initial period of computability 1930--1970 the constructions and proofs had become so complicated that it had become very difficult to obtain any intuition about them. Fortunately, Lachlan introduced: (1) the method of games in computability Lachlan [1970a] (see Chapter on Lachlan Games); (2) the topology of priority arguments Lachlan , which gave rise to the true stages method for infinite injury (refined in Chapter 8); and (3) the use trees in Lachlan  to divide a strategy for a priority argument into a collection of strategies, one assigned to each node of the tree, and each equipped with a guess about the outcome of higher priority strategies. Lachlan's original use of trees  for a 0''' argument was very complicated, but the tree method with simplifications was presented in Soare  and is further refined in this book in Chapters 9 and 10. It has been used very extensively in computability theory ever since. These three improvements and their refinements allow the reader of this book to help keep in mind what Leo Harrington calls the mountain top view of the proof: a small number of key elements, their interaction, how we resolve conflicts between conflicting requirements, and the underlying beauty of the proof. Robert Soare's upcoming book, "Computability Theory and Applications: The Art of Classical Computability".1661
Stretching things Three women check into a motel room which advertises a rate of $27 per night. They each give $10 to the porter, and ask her to bring back 3 dollar bills. The porter returns to the desk, where she learns that the room is actually only $25 per night. She gives $25 to the motel desk clerk, returns to the room, and gives the guests back each one dollar, deciding not to tell them about the actual rate. Thus the porter has pocketed $2, while each guest spent 10-1 = $9, a total of 2 + 3 x 9 = $29. What happened to the other dollar? ... try stretching things a bit: what if the actual room rate had been $0? Then the porter would pocket $27 and the guests would spend $27, which adds up to $54! pg. 22, 102, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1649
Topologically equivalent ... the original problem was almost immediately equivalent to the modified easier version. That happened for a mathematical reason: the problem was a "topological" one. This "trick" of mutating a diagram into a "topologically equivalent" one is well worth remembering. pg.19, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1418
Geometric series tool Let 1=a0=a1=a2=... Then the corresponding generating function is just 1 + x + x**2 + x**3 + ... This is an infinite geometric series which converges to 1/(1-x), provided that |x|<1
pg.144, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2165
Geometric symmetry The simplest geometric symmetries are rotational and reflectional. pg. 71 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1582
Invariant with respect to transformations this topic [symmetry] is logically contained within the concept of invariants. If a particular object (geometrical or otherwise) contains symmetry, that is just another way of saying that the object itself is an invariant with respect to some transformation or set of transformations. For example, a square is invariant with respect to rotations about its center of 0, 90, 180 and 270 degrees. pg. 103, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1646
Argument by contradiction Instead of directly trying to prove something, we start by assuming that it is false, and show that this assumption leads us to an absurd conclusion. A contradiction argument is usually helpful for proving directly that something cannot happen. ... When you begin thinking about a problem, it is always worth asking, What happens if we negate the conclusion? Will we have something that is easier to work with? If the answer is "yes", then try arguing by contradiction. pg.46, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1439
Recast a problem from one domain into another domain The powerful idea of converting a problem from words to pictures is just one aspect of the fundamental peripheral vision strategy. Open your mind to other ways of reinterpreting problems. ... what appeared to be a sequence of numbers was actually a sequence of descriptions of numbers ... Another example was the locker problem in which a combinatorial problem metamorphosed into a number theory lemma. "Combinatorics <=> Number Theory" is one of the most popular and productive such "crossovers", but there are many other possibilities. Some of the most spectacular advances in mathematics occur when someone discovers a new reformulation for the first time. pg. 60 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1507
Draw a picture I imagine that drawing a picture brings out its inner logic at the level of "icon" or "what". Central to the open-minded attitude of a "creative" problem solver is an awareness that problems can and should be reformulated in different ways. Often, just translating something into pictorial form does wonders. pg.59, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1502
Drawing the monk problem A monk climbs a mountain. He starts at 8 am and reaches the summit at noon. He spends the night on the summit. The next morning, he leaves the summit at 8am and descends by the same route he used the day before, reaching the bottom at noon. Prove that there is a time between 8 am and noon at which the monk was at exactly the same spot on the mountain on both days One solution is to draw the paths on a distance-time graph, which makes it clear that the paths must cross and so they must meet. The pictures brings out the two conditions and shows how they come together. pg.19, 59 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1504
Models of Multiplication Six ways of thinking of multiplication: Fractal, Proportion, Tally, Box, Label, Divide out. (Andrius thinking out loud) I think that the six pairs of levels, six kinds of variables, six Zermelo-Frankel axioms of set theory can be illustrated by models of multiplication as Maria Droujkova has been studying. Question: What does it mean to cancel out units as physicists do?
- The addition rule is at work, adding exponents. Multiplying by 10 or dividing by 10 shifts the number with regard to the decimal point, although it looks like the decimal point is moving. We may think of this as simply changing the units, the base unit.
- I think of rescaling as a product of actions that either make bigger (numerator) or make smaller (denominator). They are all multiplying against some unknown, acting upon it. I call the actions "multiplication drops", either "magnifying drops" (say, multiplying by 10) or "shrinking drops" (dividing by 10). So these are actions x actions x (object with units). Thus magnifying and shrinking can cancel out. Also, actions can be decomposed into component actions, into primes.
- Repeated addition is a recounting, a shift from larger units to smaller units. 3 x (23 x dollars) becomes (3 x 23) x dollars. Amount x (large unit) becomes action x (amount x small unit) becomes (action x amount) x small unit becomes amount x small unit.
- Multiplication can give the ways of matching units, multiple units times multiple units, as in box multiplication, accounting for all possibilities. Units times units means that conditions are satisfied, thus generating all of the solutions.
- Multiplication can be thought of as counting items that have been grouped where each group has the same number of items. For example, we can count coins by grouping together the pennies, nickels, dimes, quarter, placing them in rows or groups of 4 or 5 or 10. Number x (Value x Unit).
- Dividing out, for example, money per person. This is like multiple units. (Number of cycles) x (Number of people x Units )
Fractal multiplication: Recopying the whole A whole can be recopied (however many copies), then again, then again.
This is like fractal multiplication, as with your five-legged starfish
whose each leg holds another five-legged starfish. It is like multiplying
by powers of 10. The addition rule is at work, adding exponents as in (10**2)(10**3) = 10**5. Multiplying by 10 or dividing by 10 shifts the number with regard to the decimal point, although it looks like the decimal point is moving. We may think of this as simply changing the units, the base unit, which may be unknown.1526
All parabolas have the same shape I've found in teaching the quadratic equations (and searching for a use for them) that the parabola is arguably an ideal curve for learning to graph. That's because all parabolas have one and the same shape, if you discount zooming in and out. Each parabola, if you zoom in, will look flat, and if you zoom out, will look
narrow, in exactly the same proportions. You can see this if you substitute x -> ax and y->ay and thereby you can transform x = y**2 to xa = y**2 a**2 so x = a y**2 effectively where a can be as you like. This means that all parabolas look the same and their graphs differ only in how you move them around, up and down, left or right, negative or positive, zoom in or zoom out. Also, I teach my students to draw too graphs because most never realize how the parabola completely flattens out at the bottom where -1 < x < 1. It's a bit like filming a movie where you have to combine full length shots of people with head shots. One shot won't do it. Gospel Math.1841
Axiom of extensionality Wikipedia: Two sets are equal (are the same set) if they have the same elements. Note that there are thus two levels of equality. Equality is a bidirectional relationship. And the two levels are like levels of an atlas. An atlas defines, at different levels, what can be consider the "same" point or location from far away, though may be different from close up. The "equivalence" and equivalence classes may be "turned on or off" selectively in the atlas.1164
Graph Just about any situation involving "relationships" and "objects" can be recast as a graph, where the vertices are the "objects" and we join vertices with edges if the corresponding objects are "related". pg.120, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc. 1752
Sleeping mathematicians During a certain lecture, each of five mathematicians fell asleep exactly twice. For each pair of these mathematicians, there was some moment when both were sleeping simultaneously. Prove that, at some moment, some three of them were sleeping simultaneously. pg.120, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc. 1753
Reimagining the monk problem A monk climbs a mountain. He starts at 8 am and reaches the summit at noon. He spends the night on the summit. The next morning, he leaves the summit at 8am and descends by the same route he used the day before, reaching the bottom at noon. Prove that there is a time between 8 am and noon at which the monk was at exactly the same spot on the mountain on both days One solution is to allow for two monks traveling, one up and the other down, so that it is clear they must meet. In this way the solution is where the two conditions are both satisfied. pg.19, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1503
Axiom of union Wikipedia: For any set F there is a set A containing every set that is a member of some member of F1163
Two points a mile away Every point on the plane is colored either red or blue. Prove that no matter how the coloring is done, there must exist two points, exactly a mile apart, which are the same color. ... imagine the vertices of an equilateral triangle with side length one mile. There are three vertices, but only two colors available! The pigeonhole principle tells us that two vertices must be the same color! pg.93, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1636
Factoring Here is a simple problem with a "complete" solution, illustrating one of the most important tactics: factoring. ... Find all right triangles with integer sides such that the perimeter and area are equal. ... xy/2 = x + y + square root of (x**2 + y**2) ... xy - 4x - 4y + 8 = 0 ... Now we do something clever: add 8 to both sides to make the left-hand side factor. We now have (x-4)(y-4) = 8, and since the variables are integers, there are only finitely many possibilities ... The only tricky step was finding the factorization. But this wasn't really hard, as it was clear that the original left-hand side "almost" factored. As long as you try to factor, it usually won't be hard to find the proper algebraic steps. The factor tactic is essential for finding solutions.
pg.264-265 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2225
Intermediate pigeonhole If you have p pigeons and h holes, then at least one of the holes contains at least [p/h] pigeons. pg.94, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1638
Number theoretic functions Of the infinitely many functions with domain N, we will single out a few that are especially interesting. Most of these functions are multiplicative ... f(ab) = f(a)f(b) whenever a and b are relatively prime ... Define sigma_r(n)= sum over divisors d of n of d**r ... Let F(n) = sum over divisors d of n of f(d). If f is multiplicative, then F will be multiplicative as well. Define phi(n) to be the number of positive integers less than or equal to n which are relatively prime to n. ... We can use the principle of inclusion-exclusion to evaluate phi(n) ... We define [the Mobius function] mu(n) = 1 if n=1, =0 if p**2 divides n for some prime p, = (-1)**r if n = p1p2...pr, each p a distinct prime. This is a rather bizarre definition, but it turns out that the Mobius function very conveniently "encodes" PIE. ... show that sum over divisors d of n of mu(d) = 1 if n=1; =0 if n>1. The values of mu(n) alternate sign depending on the parity of the number of prime factors of n. This is what makes the Mobius function related to PIE. ... phi(n) = sum over divisors d of n of mu(d)(n/d).
pg.257-261 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2221
Eulerian Path Find the conditions on a connected graph (or multigraph) for which it is possible to travel a path that traverses every edge exactly once. Such paths are called Eulerian ... A connected graph (or multigraph) possesses an Eulerian path if and only if it has zero or exactly two odd-degree vertices. In the former case, the path is a closed path. In the latter, the path must begin and end at the odd-degree vertices.
pg.123-124, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2158
Viewing a problem modulo m Viewing a problem modulo m for a suitably chosen m is a wonderful simplification tactic because it reduces the infinite universe of integers to the finite world of Zm. You have encountered this idea before with parity ... which is just the case m=2 ... Often (but not always) we turn to prime values of m, since primes are simpler, more "fundamental" objects which are generally easier to understand. In general, When beginning a number theory investigation, assume that the variables are prime or at least relatively prime. Often the general case follows from the prime case, with just a few "technical" details. ... Fermat's Last Theorem. Let n>=3. Prove that the equation x**n + y**n = z**n has no non-zero integer solutions. ... we shall point out two simplifications ... Without loss of generality, n is prime ... we may assume that ... x, y, z have no common factor (other than 1). ... One reason that primes are so convenient is that unique "multiplicative inverses" exist. Viewing modulo m emphasizes the closed nature of a system.
pg.252-253 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2219