Paul Zeitz, I share with you my thoughts on the varieties of "deep structure" in mathematical "frames of mind". Your book has been profoundly helpful. I also share with Joanne Simpson Groaney ("Mathematics in Daily Life"), Alan Schoenfeld ("Learning to Think Mathematically..."), John Mason ("Thinking Mathematically"), Manuel Santos, and also Maria Druojkova and the where I am active.

I have been looking for the "deep ideas" in mathematics. George Polya's book "Mathematical Discovery" documents four patterns (Two Loci, the Cartesian pattern, recursion, superposition) of the kind I'm looking for (and which bring to mind architect Christopher Alexander's pattern languages). Your book documents dozens more. I've found Joanne Groaney's book helpful and I think the other writings I mention will also be in this regard.

You note in your "planet problem", pg.63, that "on the surface" it is a nasty geometrical problem but "at its core" it is an elegant logical problem. This distinction brings to mind linguist Noah Chomsky's distinction between the surface structure and the deep structure of a sentence. In general, what might that deep structure look like? George Polya ends his discussion of the pattern of "superposition" or "linear combination" to say that it imposes a vector space. In an example he gives, the problem of "finding a polynomial curve that interpolates N points in the plane" is solved by "discovering a set of particular solutions which are a basis for a vector space of linear combinations of them". The surface problem has a deep solution, and the deep solution is a mathematical structure!

I list below 24 such deep structures which characterize the mathematical "frames of mind" by which we solve problems. I note in parentheses the related patterns, strategies, tactics, tools, ideas or problems. I have included every such that I have found in your book, as well as Polya's four patterns, "total order" and "weighted average" that I observed in Joanne Growney's book, and a few more that I know of. Please start with the illustrative example of constructing an equilateral triangle.

Independent trials     

Blank sheets      Independent trials. We may think of our mind as blank sheets, as many as we might need for our work. We shouldn't get stuck, but keep trying something new, if necessary, keep getting out a blank sheet. We can work separately on different parts of a problem. This relates also to independent events (in probability), independent runs (in automata theory) and independent dimensions (in vector spaces). If something works well, then we should try it out in a different domain. Sarunas Raudys notes that we must add a bit of noise so that we don't overlearn.

          Avoid error-prone activity      Simplify .... We could multiply out all the terms, but it would take a long time, and we'd probably make a mistake. We need a strategy. pg.166 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Get your hands dirty      So we try another strategy, one of the best for beginning just about any problem: get your hands dirty. We try plugging in some numbers to experiment. If we are lucky, we may see a pattern. ... This is easy and fun to do. Stay loose and experiment. Plug in lots of numbers. Keep playing around until you see a pattern. Then play around some more, and try to figure out why the pattern you see is happening. It is a well-kept secret that much high-level mathematical research is the result of low-tech "plug and chug" methods. The great Carl Gauss ... was a big fan of this method. In one investigation, he painstakingly computed the number of integer solutions to x**2+y**2<=90,000. ... Don't skimp on experimentation! Keep messing around until you think you understand what is going on. Then mess around some more. pg.7, 30, 36 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Knowing when to give up      Sometimes you just cannot solve a problem. You will have to give up, at least temporarily. All good problem solvers will occasionally admit defeat. An important part of the problem solver's art is knowing when to give up. pg.16, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Mental toughness, confidence and concentration      But most beginners give up too soon, because they lack the mental toughness attributes of confidence and concentration. It is hard to work on a problem if you don't believe that you can solve it, and it is impossible to keep working past your "frustration threshold". ... You build upon your preexisting confidence by working at first on "easy" problems, where "easy" means that *you* can solve it after expending a modest effort. ... then work on harder and harder problems that continually challenge and stretch you to the limit ... Eventually, you will be able to work for hours single-mindedly on a problem, and keep other problems simmering on your mental backburner for days or weeks. ... developing mental toughness takes time, and maintaining it is a lifetime task. But what could be more fun than thinking about challenging problems as often as possible? pg.16, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Practice      Practice by working on lots and lots and lots of problems. Solving them is not as important. It is very healthy to have several unsolved problems banging around your conscious and unconscious mind. pg.25, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Toughen up      Toughen up by gradually increasing the amount and difficulty of your problem solving work. pg.24, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Vary the trials      The mouse in the trap ... threw himself violently against the bars, now on this side and then on the other, and in the last moment he succeeded in squeezing himself through ... We must try and try again until eventually we recognize the slight difference between the various openings on which everything depends. We must vary our trials so that we may explore all sides of the problem. Indeed, we cannot know in advance on which side is the only practicable opening where we can squeeze through. The fundamental method of mice and men is the same; to try, try again, and to vary the trials so that we do not miss the few favorable possibilities ... a man can vary his trials more and learn more from the failure of his trials than the mouse. pg.16, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc., quoting "Mice and Men" by George Polya, Mathematical Discovery, Volume II, 1965.

Space      A blank sheet is blank. We may or may not refer to that blankness. We may give it a name: identity, zero, one, empty set. The blankness is that origin point, that average, that center which is often unsaid but we may want to note as the natural, clever reference point, as in the case of the swimmer's hat that floated downstream (pg.64) Next, we can expand around the center by balancing positive and negative, numerator and denominator. We thereby introduce parity (Z2), odd or even, affirm or reject, where to reject rejection is to affirm. Next, we can expand terms as polynomials, as with "and" and "or", and thus create equations that construct and relate roots. Finally, we can consider a vector space in which any point can serve as the center for a basis. We thereby construct external "space". It is fully fledged in that it can define vectors, thus model time with arrows that have beginnings they come from and ends they go to.

Center      A blank sheet is blank. We may or may not refer to that blankness. We may give it a name: identity, zero, one, empty set. The blankness is that origin point, that average, that center which is often unsaid but we may want to note as the natural, clever reference point, as in the case of the swimmer's hat that floated downstream (pg.64) (Blank sheet, what is so central that it is often left unsaid, origin of a coordinate system, natural or clever point of view, symmetrize an equation, average principle, choice of notation, convenient notation)

          Simple form      Given any diophantine equation [an equation whose variables assume only integer values] ... Is the problem in "simple" form? Always make sure that you have divided out all common factors, or assume the variables share no common factors, etc. The purpose of math is to construct a simplification. pg.264 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

               Axiom of the empty set      Wikipedia: There is a set such that no set is a member of it.

               The decimal point      Dividing a number by 10, we are taught to move the decimal point to the left, but actually, it is the number that moves to the right. The decimal point is a fixed reference point. Similary, multiplying a number by 10, it may seem that the decimal point moves to the right, but actually, the number moves to the left.

               Zero is just a place holder      Note that zero is just a place holder and so we don't have to multiply or add by zero in the algorithms. Zero is a fiction (as a numerical value outside of the system) and those operations are placeholder operations (meaningful only with regard to the particular system). Gospel Math.

          Change your point of view      Changing your point of view is typically choosing the origin for a coordinate system. Changing the point of view is just another manifestation of peripheral vision. Sometimes a problem is hard only because we choose the "wrong" point of view. Spending a few minutes searching for the "natural" point of view can pay big dividends. pg. 64 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               The swimmer's hat      A person dives from a bridge into a river and swims upstream through the water for 1 hour at constant speed. She then turns around and swims downstream through the water at the same rate of speed. As the swimmer passes under the bridge, a bystander tells her that her hat fell into the river as she originally dived. The swimmer continues downstream at the same rate of speed, catching up with the hat at another bridge exactly 1 mile downstream from the first one. What is the speed of the current in miles per hour? ... what if we look at things from the hat's point of view? pg. 64 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Considering the simplest point in an arbitrary coordinate system      In the following problem, the "north pole" is the simplest point to consider, yet the coordinate system was arbitrary, and so the conclusion is valid for all points. 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? Without loss of generality, let x be at the "north pole". Clearly, the centers of all the other planets must lie on the south side of P's "equatorial" plane. But that renders the north poles of these planets public ... we have shown pretty easily that If location x is private on one planet, it is public on all the other planets. pg. 64 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Convenient notation      Think about convenient notation. pg.29, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Elegant solution      Algebra is commonly taught as a series of computational techniques. ... algebra is also an aesthetic subject. Sometimes one has to slog through messy thickets of algebraic expressions to solve a problem. But these unfortunate occasions are pretty rare. A good problem solver takes a more confident approach to algebraic problems. The wishful thinking strategy teaches her to look for an elegant solution. Cultivate this mindset: employ a light, almost delicate touch, keeping watch for opportunities that avoid ugly manipulations in favor of elegant, often symmetrical patterns. pg.162, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Invariant with respect to permutation of some of the roots of a polynomial      The substitution u:=x + 1/x, which helped solve x**4+x**3+x**2+x+1=0 worked because u is invariant with respect to a permutation of some of the roots. This idea is the germ of ... Galois theory. pg. 103, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Invariants      An invariant, as the name suggests, is merely some aspect of a problem - usually a numerical quantity - that does not change, even if many other properties do change. pg. 102, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               Euler's formula      Given a polyhedron without holes, the numbers of vertices, edges and faces satisfy V - e + f = 2, which is an invariant. See pg. 103, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Mean Value Theorem      If f(x) is continuous on [a,b] and differentiable on (a,b), then there is a point u in (a,b) at which f'(u) = (f(b) - f(a))/(b-a). ... the proof is just one sentence: Tilt the picture for Rolle's theorem! The mean value theorem connects a "global" property of a function (its values at the endpoints a and b) with a "local" property (the value of its derivative at a specific point) and is thus a deeper and more useful fact than is apparent at first glance. ... Suppose f is differentiable on all real numbers and there is a constant k < 1 such that |f'(x)|<=k for all real x. Show that f has a fixed point. ... Since the derivative is at most k in absolute value, and since k < 1, the graph of y=f(x) to the right of the y-axis will be trapped within the dotted line "cone" and will eventually "catch up" with the graph of y=x. The mean value theorem lets us prove this is a satisfying way. Suppose that for all x>=0, we have f(x) does not equal to x. Then by the Intermediate Value Theorem we must have f(x)> x. Pick b>0 (think large). By the mean value theorem, there is a u in (0,b) such that f'(u) = (f(b)-f(0))/(b-0) ... Since f(b) > b, we have ... f'(u) > 1 - v/b Since b can be arbitrarily large, we can arrange things so that f'(u) becomes arbitrarily close to 1. But this contradicts |f'(u)| <=k < 1 ... The satisfying thing about this argument was the role that the mean value theorem played in guaranteeing exactly the right derivative values to get the desired contradiction. pg.297-298 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Motel room paradox      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? ... The actual "invariant" here is not $30, but $27, the amount that the guests spend, and this will always equal the amount that the porter took ($2) plus the amount that went to the desk ($25). pg. 22, 102, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          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.

Balance      We can expand around the center by balancing positive and negative, numerator and denominator. We thereby introduce parity (Z2), odd or even, affirm or reject, where to reject rejection is to affirm. (Parity, Z2: affirm-reject, multiplication by one, addition of zero, union with empty set, expansion around center)

          Add zero creatively      Many [factoring] problems involve combinations of these formulas, along with basic strategies (for example, wishful thinking), awareness of symmetry, and the value add zero creatively tool. Zeitz gives the example of factoring x**4 + 4, thinking wishfully that it was the difference of two squares, and making more perfect squares appear by adding 0 = 4x**2 - 4x**2. pg. 163, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               Completing the square by adding zero      x**2 + a*x = x**2 + a*x + a**2/4 - a**2/4 = (x + a/2)**2 - (a/2)**2 One way to discover this completing-the-square formula is to add zero creatively, as above. pg. 163, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Appeal to Physical Intuition      Let x1, x2, ... xn be positive real numbers with product P and sum S. Prove that the largest value of P is attained when all the xi are equal. ... Imagine the n positive numbers as "physical" points on the number line, each with unit weight. The balancing point (center of mass) of these weights is located at the arithmetic mean value A = S/n. Notice that if we move the points around in such a way that they continue to balance at A, that is equivalent to saying that their sum stays constant. Our strategy, inspired by the symmetry-product principle, is to consider situation where the xi are not all equal and show that we can make them "more equal" and increase their product without changing their sum. If the points are not all clustering at A, then at least one will be to the left of A (call it L) and another will be to the right of A. Of these two points, move the one which is closest to A right up to A, and move the other so that the balancing point of the two points hasn't changed. ... This proof is called "algorithmic" ... pg.195-196 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Complement      Each selection of 10 winners from a group of 17 is simultaneously a selection of 7 losers from this group. ... The Symmetry Identity ... (n r) = (n n-r) ... The combinatorial argument shows why it is true, while algebra merely shows us how it is true. pg.209 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Counting the Complement      A particular application of [changing your point of view] in counting problems is If the thing you wish to count is confusing, try looking at its complement instead. How many n-bit strings contain at least 1 zero? ... an easier approach is to first note that there are 2**n possible n-bit strings, and then count how many of them contain no zeros. A complement is possible when there is a closed system, which is what polynomials define. pg.225 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Easy invariants      Be on the lookout for "easy" invariants. Check to see if you can rearrange your problem to get simple numbers such as zero or one. pg.106, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Homogeneous coloration      Parity is invoked by a coloration which is homogeneous or not. Is it possible to tile a 66 x 62 rectangle with 12 x 1 rectangles? ... Color the squares of the 66 x 62 rectangle with 12 colors in a cyclic "diagonal" pattern... This coloring has the nice property that any 12 x 1 rectangle in the tiling consists of 12 differently colored squares ... each color occurs in the same number of squares. We will call such a coloration "homogeneous". ... We can break it up into 4 sub-rectangles ... the entire large rectangle is not homogeneous... pg.111, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Make an expression uglier      Sometimes you may want to make an expression uglier because it then yields more information. ... Which is bigger 1998/1999 or 1999/2000? ... here is an argument that uses the define a function tool: Let f(x) = x/(x+1) ... How does this function grow? We have f(x) = x/(x+1) = 1/(1 + 1/x) and now it is easy to check that as x>0 increases, the 1/x term decreases, causing f(x) to increase ... "If the denominator increases, the fraction decreases, and vice versa." ... f(x) is monotonically increasing for positive x. ... Notice how we actually made an expression uglier... it is much easier to analyze the behavior of the function. pg.165, 191-192 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Modular arithmetic       Modular arithmetic arguments are typically parity arguments (divisible by N - not divisible by N). Let N be a 4-digit number with decimal representation abcd. Then n = 10**3 a + 10**2 b + 10 c + d. ... 10**k = 1**k = 1 (mod 9) ... n = 10**3 a + 10**2 b + 10 c + d = 1 a + 1 b + 1 c + d (mod 9) ... The important thing is to be aware of the possibility that an invariant may be a quantity modulo m for a properly chosen m. pg.110, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Multiply cleverly by one      The sister to the add zero creatively tool is the multiply cleverly by one. pg. 163, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Overcount and rectify      In explaining combinations and thus the coefficients of the binomial theorem... To count the number of ways a joint event occurs, multiply together the number of choices for each sub-event. To rectify uniform overcounting, divide by the overcounting factor. Such overcounting occurs, for example, when some of the objects are indistinguishable but we label them to make them easier to count, then take off the labels. In general, the number of ways you can select a subset of r distinct elements from a set of n distinct elements, where the order of selection doesn't matter, is P(n,r)/r! = (n r). This is called a combination. If the order does matter, then the number of ways is P(n,r) and it is called a permutation. Compare overcounting with the use of "negative numbers". pg.207-208 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Parity      Integers are divided into two parity classes: even and odd. The even integers are divisible by 2, the odds are not. Note that zero is even. ... The parity of a sum of a set of integers is odd if and only if the number of odd elements is odd. The parity of a product of a set of integers is odd if and only if there are no even elements in the set. ... knowledge of parity is sometimes all that is needed, especially if parity is involved in the statement of the problem. ... Whenever a problem involves integers, ask yourself if there are any parity restrictions. Experiment with different values than the given if necessary. ... Parity works amazingly well, but it is rather crude. After all, we are reducing the infinite universe of integers into a tiny world inhabited by just two entries, "even" and "odd". pg. 104, 106, 110 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               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.

               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.

          Parity of a sum or product      Let a1, a2, ..., aN represent an arbitrary arrangement of the numbers 1, 2, 3,...N. Prove that, if N is odd, the product (a1-1)(a2-2)...(aN-N) is an even number. ... The crux move: consider the sum (a1-1) + (a2-2) + ... + (aN-N) pg. 105 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Simplicity      You have been taught that "simplification" is to combine things in "like terms". This sometimes simplifies an expression, but the good problem solver has a more focused, task-oriented approach, motivated by the wishful thinking strategy. Avoid mindless combinations unless this makes your expressions simpler. Always move in the direction of greater simplicity and/or symmetry and/or beauty (the three are often synonymous). pg.165, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

Polynomials      We can equate different expansions in terms of units and equate their scalars.

               Addition means combine like units, list different units      We can practice this principle by considering "units", but also numbers used as units ("tens", "thousands", "millions", "sevenths", "percentages"), imaginary units ("zillions"), any numbers ("twos", (-1)), unknown numbers ("X"), squares of unknown numbers ("X**2"). We can mix units such as 2x + 3y -5x + 4y and likewise. Gospel Math.

          Symmetric functions of zeroes      we can get a series of expressions for the coefficients of a polynomial in terms of its zeros x**4 + a3x**3 + a2x**2 + a1x + a0 = (x-p)(x-q)(x-r)(x-s) ... Equating like terms, we have a3 = - (sum of all zeros), a2 = +(sum of all products of two different zeros), a1 = -(sum of all products of three different zeros), a0 = +(product of the zeros), where it is understood that "different" here has a purely symbolic meaning; i.e. we multiply only zeros with different labels, such as p and q, even if their numerical values are the same. ... we see, the pattern, and can write the formulas in general ... These formulas are very important, and should be committed to memory ... note the role that the power of -1 plays. pg.184-185 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

Vector space      We can consider a vector space in which any point can serve as the center for a basis. And we can construct a canonical basis, a list of basis elements. (Superposition, linear combination, duality)

          Indicator function      We shall now present a proof of the complement function of PIE, using the "binary" language of indicator functions. Recall that the indicator function of A is denoted by 1A and is a function with domain U (where U is a "universal set" containing A) and range {0,1} defined by 1A(x) = 0 if x not in A, =1 if x in A, for each x in U. ... 1A(x)1B(x) = 1 A-intersect-B(x). 1 - 1A(x) = 1 complement-of-A(x). ... the product of two indicator functions is the indicator function of the intersection of two sets and the indicator function of a set's complement is just one subtracted from the indicator function of that set. ... Define the function g(x) = (1 - 1A1(x))(1 - 1A2(x)) (1 - 1A3(x)) ... N0 = sum over x in U of g(x). pg.230-31 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Linear combination      ...the result was attained in two steps. First, we were lucky enough to spot a particularly accessible case, a special situation, and gave a solution well adapted, but restricted, to this special situation ... Then, by combining particular cases to which the restricted solution is applicable, we obtained the full, unrestricted solution, applicable to the general case... The first step deals with a particular case which is not only especially accessible, but also especially useful; we can appropriately call it a leading particular case: it leads the way to the general solution. The second step combines particular cases by a specific algebraic operation. ... n particular solutions, after being multiplied by given constants, are added to form the general solution. ... we add and subtract equations dealing with the special situation to obtain the general proof. Let us call the algebraic operation employed ... linear combination or superposition. We may use the terms introduced to outline our pattern: Starting from a leading special situation we attain the general solution by superposition of particular cases. "Mathematical Discovery: On Understanding, Learning and Teaching Problem Solving" by George Polya, 1962, John Wiley & Sons.

Time      C1) Sequence C2) Poset with maximal or minimal elements C3) Least upper bounds, greatest lower bounds C4) Limits The act of ever getting a new sheet (blank or otherwise) makes for a countably infinite list. That is what we need for mathematical induction. Next, we may prefer some sheets as more noteworthy than others, which we ignore, so that some are most valuable. Such extremes are assumed by the extreme principle. An example is the square as the rectangle of a given perimeter that yields the most area. Next, we construct monovariants which say, in effect, that the only results which count are those that beat the record-to-beat, which yields sequences of increasing minimums, thus a greatest lower bound, or alternatively, a least upper bound. Finally, we allow such a boxing-in or boxing-out process to continue indefinitely, yielding (or not) a limit that may very well transcend the existing system (as the reals transcend the rationals). We thereby construct internal "time" which is fully fledged in that the continuum without gaps may be used to model space.

Sequence      The act of ever getting a new sheet (blank or otherwise) makes for a countably infinite list. That is what we need for mathematical induction.

               Axiom of Infinity      Wikipedia: Let S(x) abbreviate x U {x}, where x is some set. Then there exists a set X such that the empty set {} is a member of X and, whenever a set y is a member of X, then S(y) is also a member of X. More colloquially, there exists a set X having infinitely many members. The minimal set X satisfying the axiom of infinity is the von Neumann ordinal ω, which can also be thought of as the natural numbers N.

          Mathematical induction     

                     Edward Cherlin: The defining characteristic of the standard natural numbers is induction.

• 0 is a natural number
• Every natural number has a unique successor that is a natural number.
• Every natural number except 0 has a unique predecessor among the natural numbers.
• If K is a set such that 0 is in K, and for every natural number n, if n is in K, then S(n) is in K, then K contains every natural number.

          Standard induction      This is a very powerful method for proving assertions that are "indexed" by integers... Each assertion can be put in the form, P(n) is true for all integers n >= n0, where P(n) is a statement involving the integer n, and n0 is the "starting point". In standard induction: 1. Establish the truth of P(n0). This is called the "base case" and is usually an easy exercise. 2. Assume that P(n) is true for some arbitrary integer n. This is called the inductive hypothesis. Then show that the inductive hypothesis implies that P(n+1) is also true. This is sufficient to prove P(n) for all integers n>=n0, since P(n0) is true by (1) ... pg.46, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               Prove n! > 2**n where integer n >= 3      Weitz, pg.51

               Prove that the sum of the interior angles of any n-gon is 180(n-2) degrees      Weitz, pg.50

          Transfinite induction      Edward Cherlin: Proofs by transfinite induction are entirely analogous to proofs by finite induction.

                     Edward Cherlin: A similar construction [to the natural numbers] and a similar inductive condition define the transfinite ordinals, but with some differences. If S is a set of ordinals with no largest member, then the union of its members is a larger ordinal. This allows us to define the first transfinite ordinal as the order type of the set of natural numbers. This ordinal is called omega. Then we get omega + 1, and so on. Taking all countable ordinals together gives us the first uncountable ordinal, and so on again.

Poset with maximal or minimal elements      We may prefer some sheets as more noteworthy than others, which we ignore, so that some are most valuable. Such extremes are assumed by the extreme principle. An example is the square as the rectangle of a given perimeter that yields the most area.

               Four times a right triangle is the difference of two squares      A right triangle rotated four times brings us back to where we were. This yields a difference of two squares from which the Pythagorean theorem follows. Note also that sin(x) and cos(x) are equal to their fourth derivatives. Gospel Math.

               Right triangles are more basic than circles      Consider a line segment of length AB and consider all of the right triangles with hypotenuse AB. Drop the altimeter Z so that the hypotenuse is X + Y. The radius is the average, the arithmetic mean (X+Y)/2 and the altimeter is the geometric mean of X and Y. This makes clear that the arithmetic mean is greater than the geometric mean because the radius is greater than the altimeter. It also shows that the square has greater area than other rectangles of the same perimeter. Then the right triangles form a semicircle without the two endpoints. Circles depend on distance and thus presume right triangles. Gospel Math.

          Arithmetic-Geometric Mean Inequality      1998 x 2000 ? 1999 x 1999 Your intuition probably tells you that the question mark should be replaced with "<", for the left-hand side is the area of a rectangle that is not quite a square, while the right hand side is the area of a square with the same perimeter as the rectangle (namely 4x1999). It makes sense that given a fixed amount of fencing, the rectangle of maximum area is a square. ... (x+y)/2 >= square-root of xy. ... The arithmetic mean of two positive real numbers is greater than or equal to the geometric mean, with equality only if the numbers are equal. ... Here is a nice geometric proof of AM-GM. Let AC be the diameter of a circle, and let B be any point on the circle. Recall that ABC will be a right triangle. Now locate point D so that BD is perpendicular to AC. Then triangles ABD and BCD are similar; hence x/g = g/y. Thus g = square root of xy, the geometric mean of x and y. Indeed, that's why it is called a geometric mean! pg.193-194 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Calculus of variations      Wikipedia: Calculus of variations is a field of mathematics that deals with extremizing functionals, as opposed to ordinary calculus which deals with functions. A functional is usually a mapping from a set of functions to the real numbers. Functionals are often formed as definite integrals involving unknown functions and their derivatives. The interest is in extremal functions that make the functional attain a maximum or minimum value - or stationary functions - those where the rate of change of the functional is precisely zero. Perhaps the simplest example of such a problem is to find the curve of shortest length, or geodesic, connecting two points. If there are no constraints, the solution is obviously a straight line between the points. However, if the curve is constrained to lie on a surface in space, then the solution is less obvious, and possibly many solutions may exist.

          Extremal arguments involving infinite sets      In more complicated problems, it is not always obvious what entities should be monotonized, and the Well-Ordering Principle is not always true for infinite sets. In situations involving infinite sets, sometimes extremal arguments work, but you need to be careful. .... Let f(x) be a polynomial with real coefficients of degree n such that f(x)>=0 for all x in R. Define g(x):= f(x) + f'(x) + f''(x) ... + f(n)(x). Show that g(x)>=0 for all x in R. pg.88, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Extreme principle      If possible, assume that the elements of your problem are "in order". Focus on the "largest" and "smallest" elements, as they may be constrained in interesting ways. ... Work by contradiction; assume that whatever you wish to prove is not true. Then look at the minimal (or maximal) element and develop an argument that creates a smaller (or larger) element, which is the desired contradiction. As long as a set of real numbers is finite, it will have a minimum and a maximum element. pg.82, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               When black and white points are interspersed...      Let B and W be finite sets of black and white points, respectively, in the plane, with the property that every line segment which joins two points of the same color contains a point of the other color. Prove that both sets must lie on a single line segment. ... The extreme principle comes to the rescue: Assume that the points do not all lie on a line. Then they form at least one triangle. Consider the triangle of smallest area. Two of its vertices are the same color, so between them is a point of the other color, but this forms a smaller triangle - a contradiction! pg.82, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Least squares      Wikipedia: The method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e. sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every single equation.

          Maximum      We conceive or find the maximum.

               Laffer Curve      Wikipedia: In economics, the Laffer curve is a theoretical representation of the relationship between government revenue raised by taxation and all possible rates of taxation. It is used to illustrate the concept of taxable income elasticity (that taxable income will change in response to changes in the rate of taxation). The curve is constructed by thought experiment. First, the amount of tax revenue raised at the extreme tax rates of 0% and 100% is considered. It is clear that a 0% tax rate raises no revenue, but the Laffer curve hypothesis is that a 100% tax rate will also generate no revenue because at such a rate there is no longer any incentive for a rational taxpayer to earn any income, thus the revenue raised will be 100% of nothing. If both a 0% rate and 100% rate of taxation generate no revenue, it follows that there must exist at least one rate in between where tax revenue would be a maximum.

          Monotonizing      Always be aware of order and maximum/minimum in a problem, and always assume, if possible, that the elements are arranged in order ... Think of this as "free information". pg.83, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Sign of the derivative      You certainly know that the derivative f'(x) of a function f(x) has two interpretations: a dynamic definition as rate of change [of f(x) with respect to x], and a geometric definition as slope of the tangent line to the graph y=f(x) at the point (x,f(x)). The rate-of-change definition is especially useful for understanding how functions grow. More elaborate information comes from the second derivative f''(x), which of course measures how fast the derivative is changing. Sometimes just simple analysis of the signs of f' and f'' is enough to solve fairly complicated problems. pg.294 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Sum of Squares      The Cauchy-Schwarz inequality states that [(the sum of aibi)**2 <= (sum of ai**2)(sum of bi**2)] with equality holding if and only if a1/b1 = a2/b2 = ... = an/bn. ... another way to prove [this] uses the simple but important tool that A sum of squares of real numbers is non-negative, and equal to zero if and only if all the numbers are zero. ... 0 <=(ay-bx)**2 + (az-cx)**2 + (bz-cy)**2. pg.198-199 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Symmetry-Product Principle      We can extract more information from our algebraic proof of AM-GM. ... S**2 - 4P = D**2, where S, P, D are respectively the sum, product and difference of x and y. ... As the distance between two positive numbers decreases, their product increases, provided that their sum stays constant. This agrees with our intuition: As a rectangle becomes more "squarish", i.e., more symmetrical, it encloses area more "efficiently". pg.193-194 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Tangent-line approximation      The tangent-line definition of the derivative stems from its formal definition as a limit. ... This suggests a useful, but less well-known, application of the derivative, the tangent-line approximation to the function. ... In general, analyzing f(a+h) with its tangent-line approximation f(a) + hf'(a) is very useful, especially when combined with other geometric information, such as convexity. ... Prove Bernoulli's Inequality (1 + x)**alpha >= 1 + alpha x for x>= -1 and alpha >= 1, with equality when x = 0. ... For integer alpha, this can be proven by induction ... But induction won't work for arbitrary real alpha. Instead, define f(u) = u**alpha, and note that f'(u) = alpha u**(alpha - 1) and f''(u) = alpha(alpha-1)u**(alpha-2). ... Thus the graph y=f(u) is concave up...Therefore, the graph of y=f(u) lies above the tangent line for all u>=0. ... f(1+x) is always strictly greater than its linear approximation 1+alpha x, except when x=0, in which case we have equality. pg.296-297 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          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.

          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.

               Division algorithm      The extreme principle in number theory ... Let a and b be positive integers, b>=a. Then there exist integers q,r satisfying q>=1 and 0<=r pg.92, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

Least upper bounds, greatest lower bounds      We construct monovariants which say, in effect, that the only results which count are those that beat the record-to-beat, which yields sequences of increasing minimums, thus a greatest lower bound, or alternatively, a least upper bound.

               Least-upper-bound assumes second-order logic      Wikipedia Second-order logic is more expressive than first-order logic. For example, if the domain is the set of all real numbers, one can assert in first-order logic the existence of an additive inverse of each real number by writing ∀x ∃y (x + y = 0) but one needs second-order logic to assert the least-upper-bound property for sets of real numbers, which states that every bounded, nonempty set of real numbers has a supremum. If the domain is the set of all real numbers, the following second-order sentence expresses the least upper bound property [...] In second-order logic, it is possible to write formal sentences which say "the domain is finite" or "the domain is of countable cardinality." To say that the domain is finite, use the sentence that says that every surjective function from the domain to itself is injective. To say that the domain has countable cardinality, use the sentence that says that there is a bijection between every two infinite subsets of the domain. It follows from the upward Löwenheim-Skolem theorem that it is not possible to characterize finiteness or countability in first-order logic.

          Algorithmic proof      AM-GM reformulated...We have managed to change two of the n numbers in such a way that

• one number that originally was not equal to A became equal to A;
• the sum of all n numbers did not change;
• the product of the n numbers increased.

          Bounded monotonic sequence      In practice, there are several possible methods of showing that a given sequence converges to a limit. ... Show that the sequence is bounded and monotonic. A sequence (an) is bounded if there is a finite number B such that |an|<=B for all n. The sequence is monotonic if it is either non-increasing or non-decreasing. ... Bounded monotonic sequences are good, because they always converge. To see this, argue by contradiction: if the sequence did not converge, it would not have the Cauchy property, etc. ... pg.285 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Convergence of upper and lower bounds      In practice, there are several possible methods of showing that a given sequence converges to a limit. ... Show that the terms of the sequence are bounded above and below by the terms of two convergent sequences that converge to the same limit. For example, suppose that for all n, we have 0 < xn < (0.9)**n. This forces the limit as n goes to infinity of xn to be zero. Conversely, if the terms of a sequence are greater in absolute value than the corresponding terms of a sequence that diverges (has infinite limit), then the sequence in question also diverges. pg.285 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

                Muchnik [1956] and Friedberg [1957] 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".

          Growth rates of functions      It is important to understand the hierarchy of growth rates for the most common functions. The best way to learn about this is to draw lots of graphs. Any quadratic function of x will dominate any linear function of x, provided that x is "large enough". ... x**a will eventually dominate x**b provided that a > b > 0. ...if a is any positive number, and b > 1, then b**x eventually dominates x**a ... exponential functions grow faster than polynomial functions ... if a is any positive number, and b > 1, then x**a eventually dominates log(b)x. In summary, the hierarchy of growth rates, from slowest to highest, is logarithms, powers, exponents. pg.190-191 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Limits and Colimits in Category Theory      In category theory, the limit of a diagram is the "least upper bound" for the diagram, in the sense that it is a cone (generalization) of the diagram such that it is more specific than any other such cone. Similarly, the colimit of a diagram is the "greatest lower bound" for the diagram, in the sense that it is a co-cone that is more general than any other such co-cone. Wikipedia: Limits are also referred to as universal cones, since they are characterized by a universal property (see below for more information). As with every universal property, the above definition describes a balanced state of generality: The limit object L has to be general enough to allow any other cone to factor through it; on the other hand, L has to be sufficiently specific, so that only one such factorization is possible for every cone. Limits may also be characterized as terminal objects in the category of cones to F. It is possible that a diagram does not have a limit at all. However, if a diagram does have a limit then this limit is essentially unique: it is unique up to a unique isomorphism. For this reason one often speaks of the limit of F.

          Massage      1 + 1/2 + 1/3 + 1/4 + 1/5 + ... Show that the harmonic series diverges ... 1/3 + 1/4 >= 1/2, 1/5+1/6+1/7+1/8 >= 1/2, etc. ... Therefore the entire harmonic series is greater than or equal to 1 + 1/2 + 1/2 + 1/2 + ... which diverges. The key idea used above combines the obvious fact that a>=b => 1/a <= 1/b with the nice trick of replacing a "complicated" denominator with a "simpler" one. This is an example of the many-faceted massage tool - the technique of fiddling around with an expression, with whatever method works (adding zero, multipying by one, adding or subtracting a bit, etc.) in order to make it more manageable. ... Yet another idea inspired by the Wishful Thinking strategy. ... The philosophy of massage is to "loosen up" an expression in such a way that it eventually becomes easier to deal with. ... Sometimes the first stage of massage seemingly worsens the difficulty. But that is temporary, much like physical massage, which can be rather painful until your muscles magically relax. Here is an instructive example which combines massage with its frequent partner, telescoping. ... pg.176-177, 197 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Monovariant      A monovariant is a quantity which may or may not change at each step of a problem, but when it does change, it does so monotonically (in only one direction). Another term used for monovariant is semi-invariant. Monovariants are often used in the analysis of evolving systems, to show that certain final configurations must occur, and/or determine the duration of the system. Many monovariant arguments also make use of the extreme principle (at least the well-ordering principle). pg.112, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               John Conway's Checker Problem      Put a checker on every lattice point ... in the plane with y-coordinates less than or equal to zero. The only legal moves are horizontal or vertical "jumping". By this we mean that a checker can leap over a neighbor, ending up 2 units up, down, right, or left of its original position, provided that the destination point is unoccupied. After the jump is complete, the checker that was jumped over is removed from the board. ... Is it possible to make a finite number of legal moves and get a checker to reach the line y=5? pg.114, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               Number of games in an elimination-style tournament      Find a formula for the number of games that must be played in an elimination-style tournament starting with n contestants. ... The number of people who are left in the tournament is clearly a monovariant over time. This number decreases by one each time a game is concluded. Hence if we start with n people, the tournament must end after exactly n-1 games! pg.112, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               Reversing cards in a deck      The n cards of a deck ... are labeled 1,...,n. Starting with the deck in any order, repeat the following operation: if the card on top is labeled k, reverse the order of the first k cards. Prove that eventually the first card will be 1 (so no further changes occur). pg.112, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

     Constraint optimization      Wikipedia: Constraint optimization (also called constrained optimization) seeks for a solution maximizing or minimizing a cost function. A constraint optimization problem can be defined as a regular constraint satisfaction problem in which constraints are weighted and the goal is to find a solution maximizing the weight of satisfied constraints. Alternatively, a constraint optimization problem can be defined as a regular constraint satisfaction problem augmented with a number of "local" cost functions. The aim of constraint optimization is to find a solution to the problem whose cost, evaluated as the sum of the cost functions, is maximized or minimized. The regular constraints are called hard constraints, while the cost functions are called soft constraints. Note that solutions of constraint optimization generally involve a series of maximums or minimums.

                     Tom Wayburn, 2011.04.28: Richard Tapia of Rice University math department suggests that Noah must have been one of the earliest practitioners of constrained optimization, as he had to house all the animals and in such a way that none got eaten.

          Branch and bound      Wikipedia: Constraint optimization can be solved by branch and bound algorithms. These are backtracking algorithms storing the cost of the best solution found during execution and use it for avoiding part of the search. More precisely, whenever the algorithm encounters a partial solution that cannot be extended to form a solution of better cost than the stored best cost, the algorithm backtracks, instead of trying to extend this solution.

          First-choice bounding functions      Wikipedia: In the branch and bound method, one way for evaluating this upper bound for a partial solution is to consider each soft constraint separately. For each soft constraint, the maximal possible value for any assignment to the unassigned variables is assumed. The sum of these values is an upper bound because the soft constraints cannot assume a higher value. It is exact because the maximal values of soft constraints may derive from different evaluations: a soft constraint may be maximal for x = a while another constraint is maximal for x = b.

          Russian doll search      Wikipedia: This method runs a branch-and-bound algorithm on n problems, where n is the number of variables. Each such problem is the subproblem obtained by dropping a sequence of variables x_1, ..., x_i from the original problem, along with the constraints containing them. After the problem on variables x_i+1, ..., x_n is solved, its optimal cost can be used as an upper bound while solving the other problems. In particular, the cost estimate of a solution having x_i+1, ..., x_n as unassigned variables is added to the cost that derives from the evaluated variables. Virtually, this corresponds on ignoring the evaluated variables and solving the problem on the unassigned ones, except that the latter problem has already been solved.

Limits      We allow a boxing-in or boxing-out process to continue indefinitely, yielding (or not) a limit that may very well transcend the existing system (as the reals transcend the rationals).

               Continuum hypothesis      Wikipedia: There is no set whose cardinality is strictly between that of the integers and that of the real numbers. ... The contributions of Kurt Gödel in 1940 and Paul Cohen in 1963 showed that this continuum hypothesis can neither be disproved nor be proved using the axioms of Zermelo-Fraenkel set theory, the standard foundation of modern mathematics, provided ZF set theory is consistent.

          Cauchy property      In practice, there are several possible methods of showing that a given sequence converges to a limit. ... Show that the ai eventually get arbitrarily close to one another. More precisely, a sequence (an) possesses the Cauchy property if for any (very tiny) epsilon > 0 there is a (huge) N such that |am - an| < epsilon for all m, n >= N. If a sequence of real numbers has the Cauchy property, it converges. The Cauchy property is often fairly easy to verify, but the disadvantage is that one doesn't get any information about the actual limiting value of the sequence. pg.285 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Convergence      We say that the real-valued sequence (an) converges to the limit L if ... That if we pick an arbitrary distance epsilon > 0, eventually, and forever after, the ai will get within epsilon of L. More specifically, for any epsilon > 0 (think of epsilon as a really tiny number), there is an integer N (think of it as a really huge number, one that depends on epsilon) such that all of the numbers aN, aN+1, aN+2, ... lie within epsilon of L. In other words, for all n >= N, |an - L| < epsilon. pg.285 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

                Shoenfield [1961] 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 [1973], which gave rise to the true stages method for infinite injury (refined in Chapter 8); and (3) the use trees in Lachlan [1975] 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 [1975] for a 0''' argument was very complicated, but the tree method with simplifications was presented in Soare [1985] 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".

          Integrals      The fundamental theorem of calculus gives us a method for computing definite integrals. ... There is a lot of interplay between summation, integration, and inequalities; many problems exploit this. Compute the limit as n approaches infinity of the sum from k =1 to n of n/(k**2 + n**2). The problem is impenetrable until we realize that we are not faced with a sum, but the limit of a sum; and that is exactly what definite integrals are. So let us try to work backwards and construct a definite integral whose value is the given limit. ... Even finite sums can be analyzed with integrals. If the functions involved are monotonic, it is possible to relate integrals and sums with inequalities... pg.301-302 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

Thread      T) Extend the domain F) Continuity R) Self-superimposed sequence These three frames are the cycle of the scientific method: take a stand (hypothesize), follow through (experiment), reflect (conclude). I imagine that they link B1, B2, B3, B4 with C1, C2, C3, C4 to weave all manner of mathematical ideas, notions, problems, objects.

Extend the Domain      Consider a constraint such as (2**X)(2**Y) = 2**(X+Y). It may make sense in one domain, such as integers X,Y > 2. If we hold true to the constraint, then we can extend the domain to see what it implies as to how 2**X must be defined for X=1,0,-1,... We can then think of the constraint (2**X)(2**Y) = 2**(X+Y) as stitching together unrelated domains. Such stitching I think allows us, in differential geometry, to stitch together open neighborhoods and thus define continuity for shapes like the torus.

          Apply calculus ideas to a discrete problem      For any sequence of real numbers A=(a1,a2,...) define delta-A to be the sequence (a2-a1, a3-a2, a4-a3,...) whose nth terms is a_n+1 - a_n. Suppose that all of the terms of the sequence delta-(delta-A) are 1, and that a19=a94=0. Find a1. Even though this is not a calculus problem - the variables are discrete, so notions of limit make no sense - we can apply calculus-style ideas. Think of A as a function on the subscript n. The delta operation is reminiscent of differentiation; thus the equation delta-(delta-A) = (1,1,1...) suggests the differential equation d2A/dn2 = 1. Solving this (pretending that it makes sense) yields a quadratic function for n. None of this was "correct", yet it inspires us to try guessing that an is a quadratic function of n. And this guess turns out to be correct! pg.313 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Appropriate new ideas      ...cultivating a confident attitude, so that when you see a beautiful solution, you no longer think, "I could never have done that", but instead think, "Nice idea! It's similar to ones I've had. Let's put it to work!" Learn to shamelessly appropriate new ideas and make them your own. There's nothing wrong with that; the ideas are not patented. If they are beautiful ideas, you should excitedly master them and use them as often as you can, and try to stretch them to the limit by applying them in novel ways. pg.20, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Complete set of solutions      Given any diophantine equation [an equation whose variables assume only integer values] ... Can we find all solutions? Once one solution is found, we try to understand how we can generate more solutions. It is sometimes quite tricky to prove that the solutions found are the complete set. pg.264 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Define a Function      Show, without multipying out, that (b-c)/a + (c-a)/b + (a-b)/c = (a-b)(b-c)(a-c)/abc. Even though it is easy to multiply out, let us try to find a more elegant approach. Notice how the right-hand side factors. We can deduce this factorization by defining f(x) = (b-c)/x + (c-x)/b + (x-b)/c. Notice that f(b) = f(c) = 0. By the factor theorem, if we write f(x) as a quotient of polynomials f(x) = P(x)/xbc, then P(x) must have x-b and x-c as factors. ... By symmetry, we could also define the function ... pg.167 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Eulerian mathematics      In the last few pages, we have been deliberately cavalier about rigor, partly because the technical issues involved are quite difficult, but mostly because we feel that too much attention to rigor and technical issues can inhibit creative thinking, especially at two times: The early stages of any investigation.; The early stages of any person's mathematical education. We certainly don't mean that rigor is evil, but we do wish to stress that lack of rigor is not the same as nonsense. A fuzzy, yet inspired idea may eventually produce a rigorous proof; and sometimes a rigorous proof completely obscures the essence of an argument. There is, of course, a fine line between a brilliant, non-rigorous argument and poorly thought-out silliness. To make our point, we will give a few examples of "Eulerian mathematics", which we define as non-rigorous reasoning which may even (in some sense) be incorrect, yet which leads to an interesting mathematical truth. We name it in honor of the 18th-century Swiss mathematician Leonard Euler, who was a pioneer of graph theory and generatingfunctionology, among other things. Euler's arguments were not always rigorous or correct by modern standards, but many of his ideas were incredibly fertile and illuminating. Most of Euler's "Eulerian" proofs are notable for their clever algebraric manipulations... Sometimes a very simple yet "wrong" idea can help solve a problem. ... They are excellent illustrations of the "bend the rules" strategy pg.312 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Existence of solutions      Given any diophantine equation [an equation whose variables assume only integer values] ... Do there exist solutions? Sometimes you cannot actually solve the equation, but you can show that at least one solution exists. pg.264 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Experimentation      When it comes to strategy, combinatorial problems are no different from other mathematical problems. The basic principles of wishful thinking, penultimate step, make it easier, etc. are all helpful investigative aids. In particular, careful experimentation with small numbers is often a crucial step. For example, many problems succumb to a three-step attack: experimentation, conjecture, proof by induction. pg.212 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Generalizing the scope of a problem      The define a function tool ... is part of a larger idea, the strategy of generalizing the scope of a problem before attacking it. pg. 98, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Guess the limit      Somehow guess the limit L, and then show that the ai get arbitrarily close to L. pg.285 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Inequalities      I think inequalities become relevant when we patch together different solution spaces. Inequalities are important because many mathematical investigations involve estimation, optimizations, best-case and worst-case scenarios, limits, etc. Equalities are nice, but are really quite rare in the "real world" of mathematics. ... Of the many ways of proving inequalities, the simplest is to perform operations that create logically equivalent but simpler inequalities. More sophisticated variants include a little massage, as well. pg.189-191 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Nonexistence of solutions      Given any diophantine equation [an equation whose variables assume only integer values] ... Are there no solutions? Quite frequently, this is the first question to ask. As with argument by contradiction, it is sometimes rather easy to prove that an equation has no solutions. It is always worth spending some time on this question when you begin your investigation. pg.264 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Substitute Convenient Values      If the polynomial P(x) is divided by x-a the remainder will be P(a). ... To see why the Remainder Theorem is true in general, divide the polynomial P(x) by x-a, getting Q(x) with remainder r. Using the division algorithm, we write P(x) = Q(x)(x-a) + r. The above equation is an identity; i.e., it is true for all values of x. Therefore we are free to substitute in the most convenient value of x, namely x=a. This yields P(a) = r, as desired. pg.181 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

Continuity      As in Polya's discussion of Descartes' universal method, we can apply continuity to consider the implications of a constraint or an equation. Polya asks about an iron ball floating in mercury, if we pour water on it, will the ball sink down or float up or stay the same? He answers this by first imagining that the water has no specific gravity (like a vacuum) and then increasing it continuously until it approaches and surpasses that of iron. Varying the variable is putting the constraint to the test, presuming that there is a solution point, just as we do and can in physical reality. At what points will the model break or hold? Continuity is the thread that we sew.

          Continuity      Informally, a function is continuous if it is possible to draw its graph without lifting the pencil. Of the many equivalent formal definitions, the following one is the easiest to use. Let f: D -> R and let a be an element of D. We say that f is continuous at a if the limit as n approaches infinity of f(x_n) = f(a) for all sequences (x_n) in D with limit a. ... Continuity is a condition that you probably take for granted. This is because virtually every function you have encountered (certainly most that can be written with a simple formula) are continuous. ... Consequently, we will concentrate on the many good properties that continuous functions possess. Here are two extremely useful ones. Intermediate-Value Theorem. If f is continuous on the closed interval [a,b], then f assumes all values between f(a) and f(b). ... Extreme-Value Theorem. If f is continuous on the closed interval [a,b], then f attains minimum and maximum values on this interval. ... The extreme-value theorem seems almost without content, but examine the hypothesis carefully. If the domain is not a closed interval, it may not be true. pg.288-289 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Intermediate-Value Theorem      If f is continuous on the closed interval [a,b], then f assumes all values between f(a) and f(b). ... the IVT, while "obvious"... has many practical applications. ... Let f:[0,1]->[0,1] be continuous. Prove that f has a fixed point; i.e., there exists x in [0,1] such that f(x) = x. ... Let g(x) = f(x)-x. Note that g is continuous and that g(0) = f(0) >=0 and g(1) = f(1)-1<=0. By the IVT, there exists u in [0,1] such that g(u) = 0. But this implies f(u)=u. pg.288-289 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Interpret dynamically      To understand what a moving curtain is, we shall explore, in some detail, the most important idea of elementary calculus. ... What is the fundamental theorem of calculus (FTC), what does it mean, and why is it true? ... We start with the very useful define a function tool .. Let g(t) = integral from a to to of f(x) with regard to x. We choose the variable t on purpose, to make it easy to visualize g(t) as a function of time. As t increases from a, the function g(t) is computing the area of a "moving curtain" ... Notice that g(a) = 0. ... Differentiation is not just about tangent lines - it has a dynamic interpretation as instantaneous rate of change. Thus g'(t) is equal to the rate of change of the area of the curtain at time t. ... The area grows fast when the leading edge of the curtain is tall, and it grows slowly when the leading edge is short. It makes intuitive sense that g'(t) = f(t) since in a small interval of time delta-t, the curtain's area will grow by approximately f(t)delta-t. ... The crux move was to interpret the definite integral dynamically, and then observe the intuitive relationship between the speed that the area changes and the height of the curtain. This classic argument illustrates the critical importance of knowing as many possible alternate interpretations of both differentiation and integration. Note that the variable "t" is understood here as time and that is part of the necessary implicit context for understanding. pg.282-284 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          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.

          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.

Self-superimposed sequence       We can formulate what we have learned in general. We do this by considering a local constraint on values as a recurrence relation (on values a1, a2, ..., aN) and then superimposing the resulting sequence upon itself, as with a generating function, yielding a global relationship of the function with itself. If the model holds, then it can be tested further. This automata is the hand that makes the stitch. (Recurrence relation as an automata, auto-associative memory of neurons as in Jeff Hawkins' "On Intelligence", generating function, telescoping tool, shift operator)

          Arithmetic Mean      An arithmetic sequence is a sequence of consecutive terms with a constant difference ... a, a+d, a+2d, ... An arithmetic series is a sum of an arithmetic sequence. The sum of an arithmetic sequence is a simple application of the Gaussian pairing tool ... Upon adding, we immediately deduce that S = n((A+L)/2), the intuitively reasonable fact that the sum is equal to the average value of the terms multiplied by the number of terms ... another term for "average" is arithmetic mean. pg.172-173 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Auto associative memory of neurons      Jeff Hawkins discusses auto-associative memory of neurons in his book "On Intelligence", where cortical columns use time-delay to relate patterns to themselves.

          Be on the lookout for new ideas      Always be on the lookout for new ideas. Each new problem that you encounter should be analyzed for its "novel idea" content. pg.20, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Be wary interchanging a “limit of a limit"      ...something disturbing happened. Each an(x) is continuous (in fact, differentiable), yet the infinite sum of these functions is discontinuous. This example warns us that infinite series of functions cannot be treated like finite series. There are plenty of other "pathologies", for example, a function f(x) defined to be the infinite sum of fi(x), yet f'(x) is not equal to the sum of the fi'(x). The basic reason behind these troubles is the fact that properties like continuity, differentiation, etc. involve taking limits, as does finding the sum of a series. It is not always the case that a "limit of a limit" is unchanged when you interchange the order. Luckily, there is one key property that prevents most of these pathologies: uniform convergence, which is defined in the same spirit as uniform continuity ... We say that the sequence of functions (fn(x)) converge uniformly to f(x) if the "N response" to the "epsilon challenge" is independent of x. pg.309 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Catalyst      Sometimes telescoping won't work with what you start with, but the introduction of a single new term will instantly transform the problem. We call this the catalyst tool. ... Simplify the product (1 + 1/a)(1 + 1/a**2)(1 + 1/a**4) ... (1 + 1/a**(2**100)). Call the product P and consider what happens when we multiply P by 1 - 1/a. The "catalyst" is the simple difference of two squares formula (x-y)(x+y) = x**2 - y**2. (1 - 1/a)P = (1 - 1/a)(1 + 1/a)(1 + 1/a**2)(1 + 1/a**4) ... (1 + 1/a**(2**100)) = (1 - 1/a**2)(1 + 1/a**2)(1 + 1/a**4) ... (1 + 1/a**(2**100)) etc. = (1 - 1/a**201). pg.175 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Define a function      The define a function tool ... is part of a larger idea, the strategy of generalizing the scope of a problem before attacking it. pg. 98, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Generating functions      The crossover tactic of generating functions owes its power to two simple facts.

• When you multiply x**m by x**n, you get x**(m+n).
• "Local" knowledge about the coefficients of a polynomial or power series f(x) often provides "global" knowledge about the behavior of f(x), and vice versa.

          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.

          Power series      A power series is a special case of a series of functions, namely one where each term has the form an(x-c)**n. ... What makes power series so useful is that they converge uniformly so long as you contract the radius of convergence a bit. ... Thus, once you are in possession of a uniformly convergent power series, you can abuse it quite a bit without fear of mathematical repercussions. You can differentiate or integrate term by term, multiply it by other well-behaving power series, etc. and be sure that what you get will behave as you think it should. ... Not only are they easy to manipulate, but they provide "ideal" information about the way the function grows. pg.311-312 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Recurrence      Many problems involving the natural numbers require finding a formula or algorithm that is true for all natural numbers n. If we are lucky, a little experimenting suggests the general formula, and we then try to prove our conjecture. But sometimes the problem can be so complicated that at first it is difficult to "globally" comprehend it. The general formula may not be at all apparent. In this case it is still possible to gain insight by focusing on the "local" solution, the transition from n=1 to n=2, and then, more generally, the transition from n to n+1. ... In how many ways can an nx2 rectangle be tiled by 1x2 dominos? ... we have the recurrence formula t_n+1 = t_n + t_n-1 for n=2, 3,... Have we solved the problem? Yes and no. [The formula], plus the boundary values t_1 = 1, t_2 = 2, completely determine t_n for any value of n, and we have a simple algorithm for computing the values: just start at the beginning and apply the recurrence formula! ... These values are precisely the Fibonacci numbers... So the problem is "solved", in that we have recognized that the tiling numbers are just Fibonacci numbers. Of course you may argue that the problem is not completely solved, as we do not have a "simple" formula for t_n (or f_n). ... While it is nice to have a "simple" formula that generates the Fibonacci sequence, knowing the recurrence formula is almost as good, and sometimes it is impossible or extremely difficult to get a "closed-form" solution to a recurrence. ... Compute the number of different triangulations of a convex n-gon ... t_n = sum over u+v = n+1 of t_u t_v ... known as the Catalan numbers ... Recurrence formulas ... may seem rather complicated, but they are really straightforward applications of standard computing ideas (partitioning and simple encoding). Algebraically, the sum should remind you of the rule for multiplying polynomials ... which in turn should remind you of generating functions ... Cn = (1/(n+1))(2n n) The purpose of math is to create models that simplify (which is, however, why they hold only tentatively). When there is no closed-form solution, then the recurrence relation may feel unsatisfactory because it has not led to the desired simplification, but has simply reproduced, redenoted the original problem. pg.233-239 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Restate      It pays to reread a problem several times. As you rethink classification, hypothesis and conclusion, ask yourself if you can restate what you have already formulated. For example, it may seem that the hypothesis is really trivial, and you just have to repeat it verbatim from the statement of the problem. But if you try to restate it, you may discover new information. Sometimes just reformulating hypothesis and conclusion with new notation helps ... Normally, one reads a problem silently. But for many people, reciting the sequence out loud is enough of a restatement to inspire the correct solution (as long as a number such as "1211" is read "one-two-one-one"...) pg.30, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Shifted sequence      Let f(x) = a0 + a1 x + a2 x**2 + ... be the generating function corresponding to the sequence (aN). Now look at x f(x) = a0x + a1 x**2 + a2 x**3 + ... This is the generating function of the original sequence, but shifted.... Now we make use of the relationship between aN and a(N-1)... [Then compare and subtract and rephrase the resulting infinite geometric series.] ... This method was technically messy, since it involved using the geometric-series tool repeatedly as well as partial fractions. But don't get overwhelmed by the technical details - it worked because multiplying a generating function by x produced the generating function for the "shifted" sequence. Likewise, dividing by x will shift the sequence in the other direction. These techniques can certainly be used for many kinds of recurrences. pg.146, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Solve for the limit      There is a simple but very productive tool that often works when a sequence is defined recursively. Let us apply it to the previous example: x_n+1 = 1/2(x_n + alpha/x_n) If xn approaches L, then for really large n, both xn and x_n+1 approach L. Thus, as n approaches infinity, the equation x_n+1 = (x_n + alpha/x_n)/2 becomes L = (1/2)(L + alpha/L), and a tiny bit of algebra yields L = square root of alpha. This solve for the limit tool does not prove that the limit exists, but it does show us what the limit must equal if it exists. pg.288 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Telescope      A geometric sequence is exactly like an arithmetic sequence except that now the consecutive terms have a common ratio ... a, ar, ar**2, ar**3... The Gaussian pairing tool is no help for summing geometric series, because the terms are not additively symmetric. However, the wonderful telescope tool comes to the rescue .... S = a + ar + ar**2 + ... + ar**(n-1) and rS = ar + ar**2 + ar**3 + ... + ar**n. Observe that S and rS are nearly identical, and hence subtracting the two quantities will produce something really simple ... all terms cancel except for the first and the last. (That's why it's called "telescoping", because the expression "contracts" the way some telescopes do.) We have S - rS = a - ar**n and solving for S yields S = (a - ar**n)/(1-r). ... The important thing is to be aware of the possibility for telescoping, which is really just an application of the adding zero creatively tool. And quite often, a telescoping attempt won't work perfectly, but will reduce the complexity of a problem. pg.173-174 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Telescoping tool     

          Zeta Function      The zeta function z(s) is defined by the infinite series z(s) = 1/1**s + 1/2**s + 1/3**s + ... pg.177 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

Symmetry      Symmetry group We unify internal and external points of view, link time and space, by considering a group of actions in time acting on space. Some aspects of the space are invariant, some aspects change. Actions can make the space more or less convoluted. At this point, we have arrived at a self-standing system, one that can be defined as if it was independent of our mental processes. Our problem has become "a math problem". Analogously, in real life, after projecting more and more what we mean in general by people, including ourselves and others, we finally take us for granted as entirely one and the same and instead make presumptions towards a universal language by which we might agree absolutely.

               Axiom schema of specification      Wikipedia: If z is a set, and P is any property which may characterize the elements x of z, then there is a subset y of z containing those x in z which satisfy the property. The "restriction" to z is necessary to avoid Russell's paradox and its variants. I think this relates to the idea that we can focus on the relevant symmetry and the relation between the locations affected or not by the symmetry group and the actions of that group.

               Designing algorithms with index cards      I have the student write on an index card, "I'm thinking of a number". Then they create subsequent index cards, each with their own instruction: "Double the number", "Add 5 to the number", "Halve the number", "Square the number" and so on. Then I have them input a number and get the output and write down all of the intermediate answers. They do this for several numbers. Then we can consider an abstract input X. We can discuss if the algorithm can be simplified, and can it be reversed. Basic Math.

          A bank of useful derivatives of "functions of a function"      We conclude our discussion of differentiation with two examples that illustrate a useful idea inspired by logarithmic differentiation. ... Logarithmic differentiation is not just a tool for computing derivatives. It is part of a larger idea: developing a bank of useful derivatives of "functions of a function" that you can recognize to analyze the original function. If a problem contains or can be made to contain the quantity f'(x)/f(x), then antidifferentiation will yield the logarithm of f(x), which in turn sheds light on f(x). pg.300 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Algebraic symmetry      Sequences can have symmetry, like this row of Pascal's Triangle: 1, 6, 15, 20, 20, 15, 6, 1 ... In just about any situation where you can imagine "pairing" things up, you can think about symmetry. pg.74, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Combination of techniques      We shall end the chapter with an exploration of the diophantine equation x**2 + y**2 = n ... where n is a prime p. Our exploration will use several old strategic and tactical ideas, including the pigeonhole principle, Gaussian pairing, and drawing pictures. The narrative will meander a bit, but please read it slowly and carefully, because it is a model of how many different problem-solving techniques come together in the solution of a hard problem. pg.274 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Complex Numbers      Complex numbers are the crossover artist's dream: like light, which exists simultaneously as wave and particle, complex numbers are both algebraic and geometric. You will not realize their full power until you become comfortable with their geometric, physical nature. This in turn will help you to become fluent at translating between the algebraic and the geometric in a wide variety of problems. ... We strongly urge you to read at least the first few chapters of our chief inspiration for this section, Tristan Needham's Visual Complex Analysis. This trail-blazing book is fun to read, beautifully illustrated, and contains dozens of geometric insights that you will find nowhere else. ... If z=a+bi, we define the conjugate of z to be z-bar = a-bi. Geometrically, z-bar is just the reflection of z about the real axis. Complex numbers add "componentwise" ... Geometrically, complex number addition obeys the "parallelogram rule" of vector addition ... Multiplication by the complex number rCisTheta is a counterclockwise rotation by Theta followed by stretching by the factor r. So we have a third way to think about complex numbers. Every complex number is simultaneously a point, a vector, and a geometric transformation, namely the rotation and stretching above! pg.131-134, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Exploit underlying symmetry in polynomials      Algebra problems with many variables or of high degree are often intractable unless there is some underlying symmetry to exploit. ... Solve x**4 + x**3 + x**2 + x**1 + 1 = 0 ... we will use the symmetry of the coefficients as a starting point to impose yet more symmetry, on the degrees of the terms. Simply divide by x**2 yielding x**2 + x + 1 + 1/x + 1/x**2 then make the substitution u := x + 1/x. pg. 75, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Fixed objects      When pondering a symmetrical situation, you should always focus briefly on the "fixed" objects which are unchanged by the symmetries. For example, if something is symmetric with respect to reflection about an axis, that axis is fixed and worthy of study (the stream in the previous problem played that role). pg. 72 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               Four bugs chasing each other      a classic problem which exploits rotational symmetry along with a crucial fixed point ... Four bugs are situated at each vertex of a unit square. Suddenly, each bug begins to chase its counterclockwise neighbor. If the bugs travel at 1 unit per minute, how long will it take for the four bugs to crash into one another? pg.71 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          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.

               Fetching water for Grandma      Your cabin is 2 miles due north of a stream which runs east-west. Your grandmother's cabin is located 12 miles west and 1 mile north of your cabin. Every day, you go from your cabin to Grandma's, but first visit the stream (to get fresh water for Grandma). What is the length of the route with minimum distance? pg.71 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               Square inscribed in circle inscribed in square      A square is inscribed in a circle which is inscribed in a square. Find the ratio of the areas of the two squares. pg.70 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Harmony      An informal alternate definition of symmetry is "harmony". ... If you can do something that makes things more harmonious or more beautiful, even if you have no idea how to define these two terms, then you are often on the right track. pg. 70 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          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.

          Not quite symmetrical      The strategic principles of peripheral vision and rule-breaking tell us to look for symmetry in unlikely places, and not to worry if something is almost, but not quite symmetrical. In these cases, it is wise to proceed as if symmetry is present, since we will probably learn something useful. pg. 70 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               Completing the square by trying to symmetrize      x**2 + a*x = x*(x + a) = (x + a/2 -a/2)*(x + a/2 + a/2) = (x + a/2)**2 - (a/2)**2 Above is a way to discover the completing-the-square formula by trying to symmetrize the terms, then adding zero creatively. pg. 163, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Roots of Unity      The zeros of the equation x**n = 1 are the nth roots of unity. These numbers have many beautiful properties that interconnect algebra, geometry and number theory. One reason for the ubiquity of roots of unity in mathematics is symmetry: roots of unity, in some sense, epitomize symmetry... pg.131-134, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Search for order      Many fundamental problem-solving tactics involve the search for order. Often problems are hard because they seem "chaotic" or disorderly; they appear to be missing parts (facts, variables, patterns) or the parts do not seem connected. ... we will begin by studying problem-solving tactics that help us find or impose order where there seemingly is none. pg. 69 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Substitution      Let a, b, c be positive real numbers such that abc=1. Prove that 1/(a**3(b+c)) + 1/(b**3(c+a)) + 1/(c**3(a+b)) >= 3/2. ... What is the worst thing about this problem? It is an inequality involving fairly ugly fractions. Wishful thinking tells us that it would be nicer if the fractions either were less ugly or did not exist at all. ... There is a pretty obvious substitution - but only obvious if you have the idea of substitution in the forefront of your consciousness. The substitution is x=1/a, y=1/b, z=1/c, which transforms the original inequality (use the fact that xyz=1) into x**2/(y+x) + y**2/(z+x) + z**2/(x+y) >= 3/2. This inequality is still not that easy to deal with, but the denominators are much less complicated, and the problem has been reduced in complexity. pg.170 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Symmetrize the coefficients      Solve the system of equations ... The standard procedure for solving systems of equations by hand is to substitute for and/or eliminate variables in a systematic (and tedious) way. But notice that each equation is almost symmetric, and that the system is symmetric as a whole. Just add together all five equations; this will serve to symmetrize all the coefficients ... Now we can subtract this quantity from each of the original equations to immediately get ... pg.166-167 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Symmetry      Symmetry involves finding or imposing order in a concrete way, for example, by reflection. ... We call an object symmetric if there are one or more non-trivial "actions" which leave the object unchanged. We call the actions that do this the symmetries of the object (Footnote: We are deliberately avoiding the language of transformations and automorphisms that would be demanded by a mathematically precise definition.) ... Why is symmetry important? Because it gives you "free" information. If you know that something is, say, symmetric with respect to 90-degree rotation about some point, then you only need to look at one-quarter of the object. And you also know that the center of rotation is a "special" point, worthy of close investigation. pg. 69-70 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          The Gaussian pairing tool      Gauss, as a child, added up the sum 1 + 2 + 3 + ... + 100, presumably by pairing up the number 1 and 100, 2 and 99, 3 and 98, ... 50 and 51, yielding 50 pairs of 101 for a total of 5,050. Paul Zeitz notes this as an example of symmetry and calls it the Gaussian pairing tool. pg. 75, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Tilt the picture      we will present, with a "hand-waving" proof, one important theoretical tool which will allow you to begin to think more rigorously about many problems involving differentiable functions. We begin with Rolle's theorem, which certainly falls into the "intuitively obvious" category. If f(x) is continuous on [a,b] and differentiable on (a,b), and f(a) = f(b), then there is a point u in (a,b) at which f'(u) = 0. The "proof" is a matter of drawing a picture. There will be a local minimum or maximum between a and b, at which the derivative will equal zero. Rolle's theorem has an important generalization, the mean value theorem. If f(x) is continuous on [a,b] and differentiable on (a,b), then there is a point u in (a,b) at which f'(u) = (f(b) - f(a))/(b-a). ... the proof is just one sentence: Tilt the picture for Rolle's theorem! pg.297-298 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Transformation      The pattern of superposition points out a path from a leading special case (or from a few such cases) to the general case. There is a very different connecting path between the same endpoints with which the ambitious problem-solver should be equally acquainted: it is often possible to reduce the general case to a leading special case by an appropriate transformation. ... For a suggestive discussion of this topic see J. Hadamard, Lecons de geometrie elementaire. Geometrie plane, 1898; Methodes de transformation, pp. 272-278. "Mathematical Discovery: On Understanding, Learning and Teaching Problem Solving" by George Polya, 1962, John Wiley & Sons.

Truth      0 Truth, 1 Model, 2 Implication, 3 Variable We now think of the problem as relating two sheets, one of which has a wider point of view because it includes what may vary, not just what is fixed. There are four ways to relate two such sheets. They are given by the questions Whether it is true? What is true? How is it true? Why is it true? Truth is what is evident, what can't be hidden, what must be observed, unlike a cup shut up in a cupboard. The fixed sheet is the level of our problem and the varying sheet is our metalevel from which we study it.

Truth: Whether it is true?      Truth: Whether it is true? The two sheets may be conflated in which case we may interpret the problem as statements that we ourselves are making which may be true or false and potentially self-referential. Together they allow for proofs-by-contradiction where true and false are kept distinct in the level, whereas the metalevel is in a state of contradiction where all statements are both true and false. In my thinking, contradiction is the norm (the Godly all-things-are-true) and non-contradiction is a very special case that takes great effort, like segregating matter and anti-matter. Deep structure "solution spaces" allow us, as with Euclid's equilateral triangle, to step away from the "solution" and consider the candidate solutions, indeed, the failed solutions.

          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.

               Square root of 2 is not rational      A classic example of proof by contradiction. pg.46, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

                Edward Cherlin, 2011.04.05: Yale Professor Fred B. Fitch's book, Symbolic Logic presents a system of logic that can be proven consistent. Dropping the law of Excluded Middle was essential to the construction. Gödel's theorem depends on Excluded Middle, so it doesn't apply to this proof of consistency. If R is the set of all sets that are not members of themselves (with further precision required that does not concern us here), then R is a member of R if and only if R is not a member of R. In the presence of Excluded Middle, this results in contradiction. In its absence, it is merely undecidable both in terms of provability and of truth.

Model: What is true?      The metalevel may simplify the problem at the level. Such a relationship may develop over stages of "wishful thinking" so that the metalevel illustrates the core of the problem. Ultimately, the metalevel gives the solution's deep structure and the level gives the problem's surface structure.

               A right triangle is half a rectangle      This morphism is the basis for the area of a right triangle, but also for all of trigonometry, and shows that a function need not be a formula, and shows how two domains - angles and ratios - can be linked, as by shapes. Gospel Math.

               Recasting geometry/combinatorics as parity      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.

          Apply algebra ideas to a calculus problem      Our final example is also due to Euler. Here the tables are turned: ideas from polynomial algebra are inappropriately applied to a calculus problem, resulting in a wonderful and correct evaluation of an infinite series (although in this case, complete rigorization is much more complicated). ... Is there a simple expression for zeta(2) = 1 + 1/2**2 + 1/3**2 + ... ? Euler's wonderful, crazy idea was inspired by the relationship between zeros and coefficients which says that the sum of the zeros of the monic polynomial x**n + a_n-1 x**n-1 + ... + a1 x + a0 is equal to - a_n-1; this follows from an easy argument that examines the factorization of the polynomial into terms of the form (x-ri), where each ri is a zero. Why not try this with functions that have infinitely many zeros? A natural candidate to start with is sin x ... pg.315 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Crossover      A crossover ... is an idea that connects two or more different branches of math, usually in a surprising way. ... perhaps the three most productive crossover topics: graph theory, complex numbers, and generating functions. pg.119, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Deliberately misleading presentation      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? ... This problem is deliberately trying to mislead the reader into thinking that the profit that the porter makes plus the amount that the guests spend *should* add up to $30. pg. 22, 102, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          e      Determine, with proof, the largest number which is the product of positive integers whose sum is 1976. ... Once again, we shall inappropriately apply calculus to a discrete problem. It makes intuitive sense for the numbers whose sum is 1976 to be equal (see the discussion of the AM-GM inequality...) But how large should these parts be? Consider the optimization question of finding the maximum value of f(x) = (S/x)**x, where S is a positive constant. An exercise in logarithmic differentiation (do it!) shows that S/x = e. Thus, if the sum is S each part should equal e and there should be S/e parts. Now this really makes no sense if S=1976 and the parts must be integers, and having a non-integral number of parts makes even less sense. But at least it focuses our attention on parts whose size is close to e=2.71828... Once we start looking at parts of size 2 and 3, the problem is close to a solution... pg.313 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Encoding      In contrast [to partitioning], the encoding tactic attempts to count something in one step, by first producing a bijection (a fancy term for a 1-1 correspondence) between each thing we want to count and the individual "words" in a simple "code". ... Instead of partitioning the collection of subsets into many classes, look at this collection as a whole and encode each of its elements (which are subsets) as a string of symbols. Imagine storing information in a computer. How can you indicate a particular subset of S = {a,b,c}? There are many possibilities, but what we want is a uniform coding method that is simple to describe and works essentially the same for all cases. That way it will be easy to count. For example, any subset of S is uniquely determined by the answers to the following yes/no questions. Does the subset include a? Does the subset include b? Does the subset include c? We can encode the answers to these questions by a three-letter string which uses only the letters y and n. For example, the string yyn would indicate the subset {a,b}. Likewise, the string nnn indicates the empty set and yyy indicates the entire set S. Thus There is a bijection between strings and subsets. ... And it is easy to count the number of strings; two choices for each letter and three letters per string mean 2**3 different strings in all. ... Proper encoding demands precise information management. ... try to think carefully about "freedom of choice": ask yourself what has already been completely determined from previous choices ... Beginners are often seduced by the quick answers provided by encoding and attempt to convert just about any counting problem into a simple multiplication or binomial coefficient Note that strings have an additional structure which makes the counting easy: the strings presume a total order of positions, from left to right, whereas the elements of a set need not be ordered. This ordering comes for free and makes the bijection work. pg.213-214 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Fantasize an answer      When looking at the conclusion of the problem, especially for a "to find" problem, sometimes it helps to "fantasize" an answer. Just make something up, and then reread the problem. Your fantasy answer is most likely false, and rereading the problem with this answer in mind may help you to see why the answer is wrong, which may point out some of the more important constraints of the problem. pg.30, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Interpreting algebraic variables as coordinates      Whenever a problem involves several algebraic variables, it is worth pondering whether some of them can be interpreted as coordinates. pg. 59 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          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.

          Recast an inequality as an optimization problem      AM-GM reformulated ... we altered our point of view and recast an inequality as an optimization problem. pg.195-196 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Recasting      [In combinatorics,] the strategy of recasting is especially fruitful: to counteract the inherent dryness of counting, it helps to creatively visualize problems (for example, devise interesting "combinatorial arguments") and look for hidden symmetries. Many interesting counting problems involve very imaginative multiple viewpoints ... to see if a combinatorial identity is true, examine how each side of the equation counts a representative element pg.212, 228 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Recasting geometry as algebra      Descartes' idea of recasting geometric questions in a numeric/algebraic form led to the development of analytic geometry, which then led to calculus. pg. 60 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

                Edward Cherlin: Proving that two seemingly unrelated, even apparently incompatible objects are equivalent in some way, or can model each other, is one of the deepest ideas in math.

                     Edward Cherlin: Mathematicians lost interest in Brouwer's Intuitionistic logic and set theory when it was shown that it and the more usual non-constructive logics and set theories can model each other.

                     Edward Cherlin: The fact that each of elliptic/Riemannian, Euclidean, and hyperbolic/Lobachevskian geometries contain models of each other shows that all three are equally valid. For example, a Clifford's surface in Riemannian space and a horosphere in Lobachevskian space both have locally Euclidean geometry.

               Galois theory      Galois theory maps the roots of a given polynomial equation (in field theory) to the Galois group of permutations of the roots.

                     Edward Cherlin: At one time it was thought that there was a vast space of possible String Theories in physics. It turns out that all of them are maps of each other.

                     Edward Cherlin: The proof of Fermat's Last Theorem depends on the Taniyama-Shimura Theorem that all elliptic functions are modular, that is, that there is a structure-preserving mapping between elliptic functions and modular forms.

          Two different ways       Keeping a flexible point of view is a powerful strategy. This is especially true with counting problems where often the crux move is to count the same thing in two different ways. To help develop this flexibility, you should practice creating "combinatorial arguments". This is just fancy language for a story that rigorously describes in English how you count something. ... Pay attention to the building blocks of "algebra to English" translation, and in particular, make sure you understand when and why multiplication rather than addition happens, and vice versa. Examples include addition (or), multiplication (and), exponentiation, combination, permutation, distinct members, products of choices, sums of choices, complements of combinations. pg.208 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

     Make it easier      The easier problem may actually be the more informative, relevant, natural, instructive problem. If the given problem is too hard, solve an easier one. ... For example, if the problems involves big, ugly numbers, make them small and pretty. If a problem involves complicated algebraic fractions or radicals, try looking at a similar problem without such terms. At best, pretending that the difficulty isn't there will lead to a bold solution... At worst, you will be forced to focus on the key difficulty of your problem, and possibly formulate an intermediate question, whose answer will help you with the problem at hand. And eliminating the hard part of a problem, even temporarily, will allow you to have some fun and raise your confidence. pg.18, 31 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

     Wishful thinking       It is helfpul to try to loosen up, and not worry about rules or constraints. Wishful thinking is always fun, and often useful. For example, in this problem, the main difficulty is that the top boxes labeled A and C are in the "wrong" places. So why not move them around to make the problem trivially easy? ... Ask yourself, "What is it about the problem that makes it hard?" Then, make the difficulty disappear! You may not be able to do this legally, but who cares? Temporarily avoiding the hard part of a problem will allow you to make progress and may shed light on the difficulties. pg.18, 31 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

Implication: How is it true?      Implication: How is it true? The metalevel may relate to the level as cause and effect by way of a flow of implications. The metalevel has us solve the problem, typically by working backwards. The level presents the solution, arguing forwards.

          Deduction      Also known as "direct proof", deduction is merely the simplest form of argument in terms of logic. A deductive argument takes the form "If P, then Q" or "P=>Q" or "P implies Q". Sometimes the overall structure of an argument is deductive, but the smaller parts use other styles. pg.46, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Penultimate step      Once you know what the desired conclusion is, ask yourself, "What will yield the conclusion in a single step?" Sometimes a penultimate step is "obvious", once you start looking for one. And the more experienced you are, the more obvious the steps are. For example, suppose that A and B are weird, ugly expressions that seem to have no connection, yet you must show that A = B. One penultimate step would be to separately argue that A ≥ B AND B ≥ A. Perhaps you want to show instead that A ≠ B. A penultimate step would be to show that A is always even, while B is always odd. pg. 30, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Recast geometry as logic      ...a problem that is geometric on the surface, but not at its core ... We are given n planets in space, where n is a positive integer. Each planet is a perfect sphere and all planets have the same radius R. Call a point on the surface of a planet private if it cannot be seen from any other planet. ... We conjecture that the total private area is always exactly equal to the area of one planet, no matter how the planets are situated. It appears to be a nasty problem in solid geometry, but must it be? The notions of "private" and "public" seem to be linked with a sort of duality; perhaps the problem is really not geometric, but logical. ... If location x is private on one planet, it is public on all other planets. After this nice discovery, the penultimate step is clear: to prove that Given any location x, it must be private on some planet. ... pg. 63 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

Variable: Why is it true?       The metalevel and the level may be distinct in the mind, as complements. Given the four levels (why, how, what, whether), the metalevel is associated with the wider point of view (why being the widest) and the level with a narrower point of view. We may think of them concretely in terms of the types of signs: symbol, index, icon, thing. The pairs of four levels are six ways to characterize the relationship. I believe that each way manifests itself through the relationship that we suppose for our variables: dependent vs. independent, known vs. unknown, given vs. arbitrary, fixed vs. varying, concrete vs. abstract, defined vs. undefined, evaluated vs. unevaluated, specialized vs. generalized, domain given or not, determined vs. undetermined (as in the problem of measuring the shortest distance to the river and grandmother's) and so on. I need to study the variety that variables can express. I suppose that, mentally, the varying variables are active in both levels, whereas the fixed variables are taken to be in the level. The levels become apparent when, for example, we draw a picture because that distinguishes the aspects of our problem that our iconic or indexical or symbolic. Likewise, our mental peripheral vision picks up on aspects specific to a particular level.

               Free variables and Bound variables      Wikipedia: In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation that specifies places in an expression where substitution may take place. The idea is related to a placeholder (a symbol that will later be replaced by some literal string), or a wildcard character that stands for an unspecified symbol. The variable x becomes a bound variable, for example, when we write 'For all x, (x + 1)2 = x2 + 2x + 1.' or 'There exists x such that x2 = 2.' In either of these propositions, it does not matter logically whether we use x or some other letter. However, it could be confusing to use the same letter again elsewhere in some compound proposition. That is, free variables become bound, and then in a sense retire from being available as stand-in values for other values in the creation of formulae.

          Bend the rules      Don't let self-imposed, unnecessary restrictions limit your thinking. Whenever you encounter a problem, it is worth spending a minute (or more) asking the question, "Am I imposing rules that I don't need to? Can I change or bend the rules to my advantage?" pg.23, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          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.

          Draw pictures      In practice, there are several possible methods of showing that a given sequence converges to a limit. ... Draw pictures whenever possible. Pictures rarely supply rigor, but often furnish the key ideas that make an argument both lucid and correct. ... consider the sequence (xn) defined by x0=alpha and x_n+1 = 1/2(x_n + alpha/x_n) ... In the picture below... Notice that the y-coordinate of the midpoint of the line segment AB is the average of these two numbers, which is equal to x_1 ... To show convergence with this picture, we would need to carefully argue why we will never "bounce" away from the convergence point. .... The picture suggests two things: that the sequence decreases monotonically, and that it decreases to square root of alpha. ... The trickiest part in the example above was guessing that the limit was alpha. What if we hadn't been lucky enough to have a nice picture? pg.285-288 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          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.

          Invent a font      The next example combines "Complement PIE" with other ideas, including the useful encoding tool, invent a font, whereby we temporarily "freeze" several symbols together to define a single new symbol. ... Four young couples are sitting in a row. In how many ways can we seat them so that no person sits next to his or her "significant other?" Define Ai to be the set of all seatings for which bi and gi sit together. To compute |Ai|, we have two cases: either bi is sitting to the left of gi or vice versa. For each case, there will be 7! possibilities, since we are permuting 7 symbols: the single symbol bigi (or gibi), plus the 6 other people... Note that alphabetical order in a Spanish language dictionary treats "ch" and "ll" as letters so that "ch" comes after "cz" and "ll" comes after "lz". pg.230 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Loosen up      Loosen up by deliberately breaking rules and consciously opening yourself to new ideas (including shamelessly appropriating them!) Don't be afraid to play around, and try not to let failure inhibit you. pg.24, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Peripheral vision      One way to heighten your receptiveness to new ideas is to stay "loose", to cultivate a sort of mental peripheral vision. ... Likewise, when you begin a problem solving investigation, you are "in the dark". Gazing directly at things won't help. You need to relax your vision and get ideas from the periphery. Like Polya's mouse, constantly be on the lookout for twists and turns and tricks. Don't get locked into one method. Try to consciously break or bend the rules. pg.20, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Without loss of generality      Note the use of the phrase "without loss of generality" in the following problem. The color "white" is chosen arbitrarily, yet its value is fixed. This is one way that variables can be employed. 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.

          Create notation      You can make progress on a math problem simply by creating a relevant notation for it, which allows you to think about it in a new way, in a new level.

     Hard and soft constraints      Wikipedia: The aim of constraint optimization is to find a solution to the problem whose cost, evaluated as the sum of the cost functions, is maximized or minimized. The regular constraints are called hard constraints, while the cost functions are called soft constraints.

      10 Tree of variations, 20 Adjacency graph, 21 Total order, 32 Powerset lattice, 31 Decomposition, 30 Directed graph The structures above are graph-like geometries. They are six ways that we visualize structure. We visualize by restructuring a sequence, hierarchy or network. We don't and can't visualize such structures in isolation, but rather, we visualize the restructuring of, for example, a network which becomes too robust so that we may restructure it with a hierarchy of local and global views, which we visualize as an Atlas, or we may restructure it with a sequence, which we visualize as a Tour that walks about the network. Here are the six visualizations, accordingly: ("Hierarchy => Sequence" means "Hierarchy restructured as Sequence", etc.)

• 10 Evolution: Hierarchy => Sequence (for determining weights)
• 20 Atlas: Network => Hierarchy (for determining connections)
• 21 Canon: Sequence => Network (for determining priorities)
• 32 Chronicle: Sequence => Hierarchy (for determining solutions)
• 31 Catalog: Hierarchy => Network (for determining redundancies)
• 30 Tour: Network => Sequence (for determining paths)

               Graph      The concept of a graph is very simple: merely a finite collection of vertices and edges. ... Just about any situation involving "relationships" between "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.

           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 )

Tree of variations      Model truth (can distinguish possibilities). Weighted averages, moves in games. 10 Evolution: Hierarchy => Sequence (for determining weights). Examination of cases.

               Axiom of pairing      Wikipedia: If x and y are sets, then there exists a set which contains x and y as elements. This relates to evolution perhaps as a notion of "counting up" or "sorting out".

               Multiplication, division by 10 moves the number      One example of fractal multiplication that comes to mind is multiplication by 10. I noticed this year that the decimal point is not logically positioned. It should be at (under or over) the "ones" place. Then the system would be symmetric. The space to the left would be the "tens" and the space to the right would be the "tenths". A little (video) essay could explain that when we multiply or divide by 10, it is the number that actually moves, not the decimal point. It's like the fact that the Sun is at (or near) the center of the solar system and the Earth revolves around it, not the other way around, as it may seem. The way that the decimal point is placed is very destructive pedagogically, it makes people (like me) think that there is something between the digit; that there is some mysterious difference between the whole numbers and the fractional numbers; and most sadly, that (jaded) teachers don't see that there's something wrong with the system, as I remember thinking as a child; and that there's no reason to care. I suspected that the decimal point is where it is for typographical reasons; maybe because it arose along with printing? or derived from accounting notation? My point being that an adult who appreciates what I've just written (and more along these lines) would appreciate some thing very deep about math (including how to calculate 10% discounts by shifting numbers to the right). Gospel Math.

          Algorithmic Proof      ... the argument below can easily be rewritten as an induction proof. But it is much more instructive to present a new type of argument, an algorithmic proof where we give a general recipe for the construction of an Eulerian path. Consider first a graph with exactly two odd-degree vertices, which we will call s and f. Let us try to naively draw an Eulerian path, starting from s. We will travel randomly ... But this doesn't quite work ... We would be stuck at vertex f, with no way to "backtrack" and traverse the other edges. In this case, let us temporarily remove the edges that we have traveled. We are left with the subgraph ... Since the original graph was connected, the subgraph "intersected" some of the edges that we removed ... Now let us apply the "naive" algorithm to the subgraph ... So now we can perform "reconstructive surgery" on our original path and get an Eulerian path for the entire graph. ... This method will work in general. We may have to repeat the "remove the traveled edges and travel the subgraph" step several times ... but since the graph is finite, eventually we will finish. pg.124-125, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Dividing into cases      Sometimes you can reduce the number of pigeonholes by dividing into cases. pg.96, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Examination of cases      One of the methods of proof is examination of cases, for example, considering odd and even separately, as in a proof of 1+2+3+...+ n = n(n+1)/2.

          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.

               Repeatedly folding paper     

• If a rectangular paper is folded in half, and half again, and yet again, and so on, and they are all considered repeatedly applied transformations of the same whole, then that is fractal multiplication, "recopying the whole", as with your paper snowflake.
• If a paper is folded once, and then again, and again, but those actions are thought as taking place separately, and especially, if I'm focused on the labelled components (rather than the repeating whole), then it is label multiplication, "redistributing the multiple", as with your pie halves sliced in five slices each.

Adjacency graph      Imply truth (can determine connectedness) (Connectedness, coloring, triangulation of polygon) 20 Atlas: Network => Hierarchy (for determining connections)

               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.

               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.

          Coloring      The use of coloring is related to parity and modular arithmetic, except that we are not constrained by the algebraic properties of integers. pg.111, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Divisibility      Given two natural numbers a, b, their greatest common factor (a,b) ... is defined to be the largest integer which divides both a and b. ... If the GCD of two numbers is 1, we say that the two numbers are relatively prime. ... If g divides a and g divides b, then g divides ax + by, where x and y can be any integers ... An important consequence of the division algorithm, plus [the last fact], is that The greatest common divisor of a and b is the smallest positive linear combination of a and b. ... a great showcase for the use of the extreme principle plus argument by contradiction. Define u to be the smallest positive linear combination and let g=(a,b) ... certainly g divides u ... suppose that u does not divide a. Then by the division algorithm, there exists a quotient k>=1 and positive remainder r < u such that a = ku+r. But then r = a-ku is positive and less than u. This is a contradiction, because r is also a linear combination of a and b ... Consequently, u divides a, and likewise u divides b. So u is a common divisor; thus u=g. ... This linear combination characterization of the GCD is really quite remarkable, for at first one would think that PPF's are needed to compute the GCD of two numbers. But in fact, computing the GCD does not rely on PPF's ... but we can use [instead the fact that if there exists x, y such that ax + by = 1, then a and b are relatively prime]. ... we do not need to assume the truth of the FTA in order to compute the GCD. The GCD is the grid size that results on a number line from taking steps back and forth of size a and b. We are thus thinking not in terms of primes as components, but of grids (the numbers they divide) that can be included or not in each other, and are thus organized by a lattice of conditions (of which points can be reached or not), where satisfying all conditions means including all points and being relatively prime and writing a ratio in reduced form. pg.245 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          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.

               Handshake Lemma      In any graph, the sum of the degrees of all the vertices is equal to twice the number of edges. pg.121, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               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.

          Least Common Multiple      ...we define the least common multiple, or LCM, of a and b to be the least positive integer which is a multiple of both a and b. pg.245 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Proportion multiplication: Rescaling the whole      A whole can be rescaled. This is proportion, as with your teddy bear projected on a screen. The rescalings are actions that can be composed, magnifying and shrinking. They are all multiplying against some unknown, acting upon it, yielding actions x actions x (object with units). They can be reorganized and canceled away. I sometimes talk to my students about "magnifying drops" (each drop multiplying by 10) and "shrinking drops" (each drop dividing by 10) and ask what happens when we add one drop after another drop. Also, actions can be decomposed into component actions, into primes. I relate this to the adjacency graph and the Atlas view because it consists of a hierarchy of global and local views upon a network, thus the same relation can appear at different scales.

               Bicycle gearing      Bicycle gears are given by the formula: (number of front teeth / number of back teeth) x circumference of wheel = distance traveled per revolution. That's an example of the proportional scaling ("rescaling the whole", like with projecting a teddy bear ). You could imagine starting out with two gears (the gear fixed to the wheel, and the gear you are pedaling) each the size of the back wheel. Replacing those giant gears with smaller gears is an action of magnifying or shrinking the distance traveled. You could add more gears to further magnify or shrink that ratio. Adding teeth to the gears is changing the units (and that aspect could be considered "rescaling the multiple", as with skip counting, but that is the correspondence of the number of teeth to the circumference of the gear, NOT the relationship between the two gears). The fact that multiplication is taking place at two different levels makes it challenging to think about because the gear ratio is "abstract" and not concretely, directly related to the size of the wheel.

          The Two Men of Tibet      Two men are located at opposite ends of a mountain range, at the same elevation. If the mountain range never drops below this starting elevation, is it possible for the two men to walk along the mountain range and reach each other's starting place while always staying at the same elevation? ... As long as it is legal to walk backward, it is pretty easy... But why does it work? ... define a graph G whose vertices are all ordered pairs (x,y) where x,y [are the "interesting" places] and x and y are at the same elevation. ... the vertices of G consist of all possible legal configurations of where the two dots could be ...we shall join two vertices by an edge if it is possible to travel between the two configurations in one "step" ... if we can show that there is a path from (a,s) to (s,a) we'd be done. ... by the handshake lemma, the sum of the degrees of the vertices of this subgraph must be even. Since the only two vertices with odd degree are (a,s) and (s,a), this subraph must contain (s,a) as well. ... we solved this hard problem with a very simple parity analysis. Of course, we first needed the insight of constructing a graph, and the crux move of defining the vertices and edges in a very clever way. pg.126-128, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Triangulating, then coloring      The walls of a museum gallery form a polygon with n sides, not necessarily regular or even convex. Guards are placed at fixed locations inside the gallery. Assuming that guards can turn their heads, but do not walk around, what is the minimum number of guards needed to assure that every inch of wall can be observed? ... A coloring reformulation comes to the rescue: Triangulate the gallery polygon. pg. 43, 61 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

Total order      Imply model (can order procedures) (Strong induction, decision making, total ranking, integers) 21 Canon: Sequence => Network (for determining priorities)

               Well-ordering theorem      Wikipedia: Axiom 9: For any set X, there is a binary relation R which well-orders X. This means R is a linear order on X such that every nonempty subset of X has a member which is minimal under R. ... Given Zermelo-Fraenkel axioms 1-8, there are many statements provably equivalent to axiom 9, the best known of which is the axiom of choice (AC), which goes as follows. Let X be a set whose members are all non-empty. Then there exists a function f from X to the union of the members of X, called a "choice function", such that for all Y element of X one has f(Y) element of Y. Since the existence of a choice function when X is a finite set is easily proved from axioms 1-8, AC only matters for certain infinite sets. AC is characterized as nonconstructive because it asserts the existence of a choice set but says nothing about how the choice set is to be "constructed." The Well-ordering theorem seems tightly related to the concept of a total order. It's interesting that it's related to the axiom of choice.

          If you can count it, it's an integer      Show that the product of k consecutive integers is divisible by k! ... simply observe that m(m+1)...(m+k-1)/k! = (m+k-1 k) and binomial coefficients are integers! The moral of the story: Keep your point of view flexible. Anything involving integers is fair game for combinatorial reasoning. pg.273 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Permutations      Permutations are the ways of reordering a collection of objects, all distinct. A permutation labels a total order.

          Strong induction      Strong induction gets its name because we use a "stronger" inductive hypothesis. After establishing the base case, we assume that for some n, all of the following are true: P(n0), P(n0+1), P(n0+2), ... , P(n), and we use this assumption to prove that P(n+1) is true. Sometimes strong induction will work where standard induction doesn't. ... Behind the idea of strong induction is the notion that one should stay flexible when it comes to defining hypotheses and conclusions. pg.52, 54, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Tally multiplication: Rescaling the multiple      A multiple can be rescaled. This is like skip counting or repeated addition. Note that here the numbers added are cardinals, which is to say, we don't care in each subgroup what order they had, it's not relevant, we're simply adding up the sums. This 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. 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) => (Number x Value) x Unit.

               Cutting a stack of cheese slices      If I have a stack of 10 slices of cheese and I slice them all in two, then:

• if I'm simply changing the units, so that I'm thinking now of 20 small slices rather than 10 large slices, so that 1 large slice = 2 small slices, then I'm skip counting, "rescaling the multiple".
• if I'm thinking of each large slice as consisting of a left piece and a right piece, (a first piece and a second piece, distinguishable or "labelled" with a child's ID 10x2), then I'm "redistributing the multiple", as with "sets, per each".

          Bucket elimination      Wikipedia: Bucket elimination is a satisfiability algorithm. It can be defined as a reformulation of adaptive consistency. Its definitions uses buckets, which are containers for constraint, each variable having an associated bucket. A constraint always belongs to the bucket of its highest variable. The bucket elimination algorithm proceeds from the highest to the lowest variable in turn. At each step, the constraints in the buckets of this variable x_i are considered. By definition, these constraints only involve variables that are lower than x_i. The algorithm modifies the constraint between these lower variables (if any, otherwise it creates a new one). In particular, it enforces their values to be extendible to x_i consistently with the constraints in the bucket of x_i. This new constraint, if any, is then placed in the appropriate bucket. Since this constraint only involves variables that are lower than x_i, it is added to a bucket of a variable that is lower than x_i. This algorithm is equivalent to enforcing adaptive consistency. Since they both enforce consistency of a variable with all its parents, and since no new constraint is added after a variable is considered, what results is an instance that can be solved without backtracking. Since the graph of the instance they produce is a subgraph of the induced graph, if the induced width is bounded by a constant the generated instance is of size polynomial in the size of the original instance. As a result, if the induced width of an instance is bounded by a constant, solving it can be done in polynomial time by the two algorithms.

Powerset lattice      Vary implication (can satisfy various conditions) 32 Chronicle: Sequence => Hierarchy (for determining solutions)

               Axiom of power set      Wikipedia: In mathematics, the axiom of power set is one of the Zermelo-Fraenkel axioms of axiomatic set theory. Given any set A, there is a set P(A) such that, given any set B, B is a member of P(A) if and only if B is a subset of A.

               Distributing with box mathematics      We can distribute 23 x 15 using grid paper as (20 + 3) x (10 + 5). We can change the tens to hundreds or thousands or millions. Likewise we can distribute (2X + 3) x (X + 5). Compare with two digit multiplication. Gospel Math.

          Box multiplication: Redistributing the set      A set can be redistributed. A set is anything which can be thought as multiple units, where each element is distinct. A set can be the rows of a chessboard or an array. It can be the breakdown of a length, for example, 2 feet and 1/2 foot. We multiply the set by applying the distributive law and multiplying each element of the set separately. And that multiplication can be noncommutative, which is to say, we can make sure that the element is followed by the action. Such multiplication typically looks like a set matched with another set, yielding "box multiplication", as when we multiply (3 feet + 1/4 foot)(2 feet + 1/2 foot) and get 4 products which we then sum up. This is also the standard computation of multiplication, for example, multiplying 2 digit numbers together. Multiplication thus gives 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. Here the units are all known, they form sets, thus there are distinct terms in expressions with multiple units.

          Infinitely many primes      There are infinitely many primes ... We start by assuming that there are only finitely many primes p1, p2, ... , pN. Now (the ingenious crux move!) consider the number Q = (p1p2...pN) + 1. Either it is prime, or it is composite. ... We construct a value p1p2...pN that satisfies all conditions exactly and then adjust it ever so slightly +1 so that it satisfies none of them. In other words, we create a model p1p2...pN that satisfies all and then we force that model to break down. We design this value with regards to the closed system as a whole. pg.244 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Multiply in a particular order      Simplify .... We could multiply out all the terms, but it would take a long time, and we'd probably make a mistake. We need a strategy. If this expression is to simplify, we will probably be able to eliminate radicals. If we multiply any two terms, we can use the difference of two squares formula and get expressions which contain only one radical. pg.166 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Polya's pattern of two loci     

                     Euclid's first problem in his Elements is: In drawing an equilateral triangle, given the first side AB, how do we draw the other two? The solution is: to draw a circle c(A) around A of length AB and to draw a circle c(B) around B of length AB. The third point C of the equilateral triangle will be at a point where the two circles intersect. (There are two such points, above and below the line segment.) Polya notes that this solution is a particular example of a general pattern of "two locii", which is to say, we can often find a desired point by imagining it as the intersection of two curves. I note further that each curve may be thought of as a condition (X="points within a distance AB of A", Y="points within a distance AB of B"). The solution created four regions:

• Solutions to both X and Y.
• Solutions to X.
• Solutions to Y.
• Solutions to the empty set of conditions.

          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.

          Constraint satisfaction      Wikipedia: In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that satisfies all constraints.

     Creative rethinking      Many creative methods have us rethink, reorganize, untangle, recombine the conditions that define a problem.

               The two ropes      Paul Zeitz gives the following problem that can be solved (the two ropes can be retrieved) by teasing out the conditions that the solution must satisfy and organizing them thoughtfully. You are locked in a 50 x 50 x 50-foot room which sits on 100-foot stilts. There is an open window at the corner of the room, near the floor, with a strong hook cemented into the floor by the window. So if you had a 100-foot rope, you could tie one end to the hook, and climb down the rope to freedom. (The stilts are not accessible from the window.) There are two 50-foot lengths of rope, each cemented into the ceiling, about 1 foot apart, near the center of the ceiling. You are a strong, agile rope climber, good at tying knots, and you have a sharp knife. You have no other tools (not even clothes). The rope is strong enough to hold your weight, but not if it is cut lengthwise. You can survive a fall of no more than 10 feet. How do you get out alive? pg. 27, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

Decomposition      Vary model (can variously combine factors) (Pigeonhole principle, partitions, factorizations, encoding, full range of outputs, principle of inclusion-exclusion). We can interpret factorizations in terms of "and" and "or", and thus create equations that construct and relate roots. (Or, And, method of undetermined coefficients, expansion, construction) 31 Catalog: Hierarchy => Network (for determining redundancies)

               Axiom of union      Wikipedia: For any set F there is a set A containing every set that is a member of some member of F

               Reorganizing addition to do it in your head      Adding 256 + 256 in your head is easier to do from left to right than from right to left because the intermediate response (500) is simpler because there is nothing to carry. Gospel Math.

               Reorganizing multiplication to do it in your head      Given a problem 5,000 x 50,000, we can break it down in different ways such as 5 x 50 x 1,000 x 1,000 so that we can do it in our head. Gospel Math.

          And      Simple multiplication. If there are a varieties of soup and b varieties of salad, then there are ab possible ways to order a meal of soup and salad. pg.205 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Binomial theorem      Pascal's Triangle contains all of the binomial coefficients. ... We derived the binomial theorem above by observing that the coefficients in the multiplication of the polynomial (x+y)**k by (x+y) obeyed the summation formula. Here is a more direct "combinatorial" approach, one where we think about how multiplication takes place in order to understand why the coefficients are what they are. Consider the expansion... notice how we can read off the "history" of each term...Now let us think about combining like terms... pg.211 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Combinatorial tactics      But mostly, combinatorics is a tactical game. You have already learned the fundamental tactics of multiplication, division, addition, permutations, and combinations. pg.212 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Complement PIE      The combination of PIE with counting the complement is so common, it is worth noting (and verifying) the following alternative formulation of PIE [principle of inclusion-exclusion] ... Given N items, and k sets A1, A2, ..., Ak, the number of these items which lie in none of the Aj is equal to N-S1+S2-S3+...+-Sk, where the Si is the sum of the cardinalities of the intersections of the Aj's taken i at a time, and the final sign is plus or minus, depending on whether k is even or odd. pg.230 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Complete the square     

          Conspicuous ceiling      41 rooks are placed on a 10x10 chessboard. Prove that there must exist 5 rooks, none of which attack each other. ... When you see the number 41 juxtaposed with 10, you know that the pigeonhole principle is lurking about, since 41 is just one more than 4x10. Once attuned to the pigeonhole principle, we cannot help but notice that [41/10] = 5, which is encouraging, for this is the number of rooks we seek. pg.95, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Eliminate radicals      Assume that you can make good progress. What will the result look like? If this expression is to simplify, we will probably be able to eliminate radicals. If we multiply any two terms, we can use the difference of two squares formula and get expressions which contain only one radical. pg.166 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Extracting squares      The tactic of extracting squares includes many tools in addition to completing the square. ... It is easy enough to see how this works, but why is another matter. For now, hindsight will work: remember that many useful squares lurk about and come to light when you manipulate "cross-terms" appropriately (making them cancel out or making them survive as you see fit). pg.164-165, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Factor Theorem      A reinterpretation of this theorem from a problem solver's perspective is To know the zeros of a polynomial is to know the polynomial. In other words, if you don't know the zeros of the polynomial under consideration, either expend some effort to find them, or shift your focus to a new polynomial whose zeros are apparent. pg.182 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          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, Inc

          Fundamental Theorem of Arithmetic      ...every natural number greater than 1 can be factored completely into primes. ... In fact, this factorization is unique, up to the order that we write the primes. This property of unique factorization is called the Fundamental Theorem of Arithmetic (FTA). We call the grouping of factors into primes the prime-power factorization (PPF). An ugly, but necessary, notation is sometimes to write a number n in "generic" PPF: n = (p1**e1)(p2**e2)...(pt**et). ... If p is a prime and p divides ab, then p divides a or p divides b ... is the key idea that we need ... Here is a simple example of FTA-style reasoning ... Prove that if a monic polynomial has a rational zero, then this zero must in fact be an integer. ... Let u/v be a zero of this polynomial. The crux move: without loss of generality, assume that u and v are relatively prime. ... get rid of fractions, by multiplying both sides by v**n ... This gives us ... u**n = [a multiple of v] ... we must conclude that v = 1 or -1, ie., u/v is an integer. The assumption that u and v are relatively prime means that they taken to be distinct as atoms. pg.244-248 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Halt or repeat      If there are only finitely many states as something evolves, either a state will repeat, or the evolution will eventually halt. pg.113, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          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.

          Label multiplication: Redistributing the multiple      A multiple can be redistributed. This is similar to skip counting but it is counting collections, and so it is counting everything up as if we were counting up each item in each collection. Thus it is recounting ordinals. We can think of it as a labeling process, where each group and subgroup is counted and labeled. Thus it proceeds from whole to parts, in the opposite direction as tallying, which proceeds from parts to whole.

          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, Inc

          Or      Simple addition. If there are a varieties of soup and b varieties of salad, then there are a+b possible ways to order a meal of soup or salad (but not both soup and salad). pg.205 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Partitioning      Partitioning is a tactic that deliberately focuses our attention on addition, by breaking a complex problem into several smaller and simpler pieces. [Often used in tandem with encoding]. ... A partition of a set is a division of S into a union of mutually exclusive (pairwise disjoint) sets. ... if S has been partitioned by the Ai, we must have [the cardinality of S equals the sum of the cardinalities of the Ai] ... This leads to a natural combinatorial tactic: Divide the thing that we want to count into mutually exclusive and easy-to-count pieces. ... For example ... the number of subsets of S must be (n 0) + (n 1) + (n 2) + ... + (n n) ... The partitioning tactic makes a pretty utopian assumption, namely that the thing we wish to count can be nicely broken down into pairwise disjoint subsets. Reality is often messier... pg.213-214, 225 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          Partitions      Given a positive integer n, a partition of n is a representation of n as a sum of positive integers. The order of the summands does not matter, so they are conventionally placed in increasing order. pg.151, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Pigeonhole principle      If you have more pigeons than pigeonholes, and you try to stuff them into the holes, then at least one hole must contain at least two pigeons. ....sometimes also called the Dirichlet principle. pg.92, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               n+1 positive integers      Show that among any n+1 positive integers, there must be two whose difference is a multiple of n. ... The penultimate step ... is realizing that the two desired numbers must have same remainder upon division by n. Since there are only n possible remainders, we are done. pg. 93, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

               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.

          Repeated application of pigeonhole principle      ...This rather elaborate problem was a good illustration of both the pigeonhole principle and the wishful thinking strategy, i.e., not giving up. When you think that the problem can be attacked with the pigeonhole principle, first try to do the job neatly. Look for a way to define pigeons and holes that yields a quick solution. If that doesn't work, don't give up! Use the pigeonhole principle once again to gain a foothold, then try to use it again. Keep extracting information! pg.95, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          The Factor Tactic      Multiplication rarely simplifies things. Instead you should Factor relentlessly. pg. 163, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          The Fundamental Theorem of Algebra      The Factor Theorem above tells us that x-a is a factor of polynomial P(x) if a is a zero. But how do we know if a polynomial even has a zero? The Fundamental Theorem of Algebra guarantees this: Every polonomial in C[x} has at least one complex zero. pg.182 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          The principle of inclusion-exclusion      The partitioning tactic makes a pretty utopian assumption ... We shall explore a number of ways of dealing with situations where sets overlap and overcounting is not uniform ... Sometimes the complement counting tactic fails us, because the complement is just as complicated as the original set. The principle of inclusion-exclusion (PIE) is a systematic way to handle these situations. In simplest form, PIE states that the number of elements in the union of two sets is equal to the sum of the number of elements in the sets minus the number of elements in their intersection. ... It is easy to see why this is true: Adding |A| and |B| overcounts the value of |A union B|. This overcounting is not uniform; we did not count everything twice, just the elements of A intersection B. Consequently, we can correct by subtracting |A intersect B|. ... In general, we conjecture The cardinality of the union of n sets = + (sum of the cardinalities of the sets) - (sum of the cardinalities of all possible intersections of two sets) + (sum of the cardinalities of all possible intersections of three sets) ... + [if n is odd] or - [if n is even] (the cardinality of the intersection of all n sets). It is pretty easy to see why the formula is true in an informal way. For example, consider the following [Venn] diagram, which illustrates the three-set situation ... It makes sense that in the general case, we would alternate between adding and subtracting ... We have reduced PIE, then, to proving the identity ... (r 0) - (r 1) + (r 2) - ... + (-1)**r (r r) = 0. ... Just expand 0 = (1-1)**r with the binomial theorem and you immediately get [it]! ... Whenever you see the words "at least" you should be alerted to the possibility of counting complements (1-1)**r is the binomial theorem expressing the Venn diagram of conditions acting on parity/balance. pg.226-229 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          x**2 + y**2 = 13      This is a diophantine equation, so we should try factoring. "But it doesn't factor", you say. Sure it does! We can write (x+yi)(x-yi) = 13, where i is of course equal to the square root of -1, The only problem, and it is a huge one, is that i is not an integer. But let's stay loose, bend the rules a bit, and make the problem easier. It is true that the square root of -1 is not an integer, but what if we looked at the problem in Z13? Notice that 5**2 = 25 == -1 (mod 13). In other words, i "makes sense" modulo 13. pg.274-275 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

Directed graph      Vary truth (can add or remove circular behavior) (With or without cycles) 30 Tour: Network => Sequence (for determining paths)

               Axiom of regularity      Wikipedia: Every non-empty set x contains a member y such that x and y are disjoint sets. This eliminates, for example, the possibility of there being a set X which is its own element X = {X}. (Note that the empty set has no members). This allows us to think of set inclusion relations in terms of directed graphs because then it is clear which is the element of which, although there can be cycles. Thus the axiom of regularity may be thought to allow directed graphs to make sense. Wikipedia: The axiom of regularity is arguably the least useful ingredient of Zermelo-Fraenkel set theory, since virtually all results in the branches of mathematics based on set theory hold even in the absence of regularity ... However, it is used extensively in establishing results about well-ordering and the ordinals in general.

          Connectivity and Cycles      By [cycle] we mean a closed path that "travels" along the edges. ... A graph is connected if every pair of vertices has a path between them. If a graph is not connected, one can always decompose the graph into connected components. ... A connected graph that contains no cycles is called a tree. ... For trees, the number of edges is exactly one less than the number of vertices. ... If a graph has e edges and v vertices and e>=v, then the graph must contain a cycle. pg.120-123, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Divide out Multiplication: Redistributing the whole      A whole can be redistributed. This is long division. We can focus on cases where the remainder is zero, or we can simply keep dividing forever. This is like children (or pirates) "dividing out" money, "counting out" money ("one for me, one for you, ..."). Most of the whole is divided out; then more of it; then more and so on. This yields multiple units. (Number of cycles) x (Number of people x Units )

          Division Algorithm      Let f(x) and g(x) be polynomials in K[x], where K is one of Z, Q, R, C or Zn. Then f(x) = Q(x)g(x) + R(x) where Q(x), R(x) are elements of K[x] and the degree of R(x) is less than the degree of g(x). ... For example ... by doing "long division" we get ... The important thing is that the quotient Q(x) is also in Z[x], i.e., also has integer coefficents. pg.180 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          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.

          Hamiltonian Path      The "dual" of an Eulerian path is a Hamiltonian path ... a path that visits each vertex exactly once. If the path is closed, it is called a Hamiltonian cycle. While Eulerian paths possess a "complete theory", very little is known about Hamiltonian paths. At present, the necessary and sufficient conditions for Hamiltonians paths are unknown. This is unfortunate, because many practical problems involve Hamiltonian paths. ... Many problems involving scheduling and optimization of network paths can be recast as searches for Hamiltonian paths. pg.125, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Handshake Lemma      In any graph, the sum of the degrees of all the vertices is equal to twice the number of edges. pg.121, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.

          Modulo n filtering      Another essential tactic [in analyzing diophantine equations] is to "filter" the problem modulo n for a suitably chosen n. This tactic often helps to show that no solutions are possible, or that all solutions must satisfy a certain form. (Use of the division algorithm is closely related to the factor tactic.) ... the complete theory of Pythagorean triples: Find all solutions to x**2 + y**2 = z**2 ... we can assume that our solution is not just primitive, but relatively prime in pairs ... Next, a little parity analysis; ie., let's look at things modulo 2. Always begin with parity. You never know what you will discover. ... exactly one of x and y is even... pg.265-267 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc

          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, Inc

Context      O Context If you read the problem carefully, if you understand and follow the rules, then you can also relax them, bend them. You can thus realize which rules you imposed without cause. You can also change or reinterpret the context. These are the holes in the cloth that the needle makes. I often ask my new students, what is 10+4? When they say it is 14, then I tell them it is 2. I ask them why is it 2? and then I explain that it's because I'm talking about a 12-hour clock. This example shows the power of context so that we probably can't write down all of the context even if we were to know it all. We can just hope and presume that others are like us and can figure it out just as we do. Analogously, in real life, it's vital to obey God, or rather, to make ourselves obedient to God. (Or if not God, then our parents, those who love us more than we love ourselves, who want us to be alive, sensitive, responsive more than we ourselves do.) If we are able to obey, then we are able to imagine God's point of view and even make sense of it.

               10 + 4 = 2      I ask my students, What is 10+4? and they answer 14, and then I say, No, it is 2! Do you know why? Because I'm thinking about a clock. 10 o'clock plus 4 o'clock is 2 o'clock on a clock. What the example shows is that meaning ultimately depends on the context which we interpret. Any explanations that we write may also be misinterpreted. Thus there is no way to explicitly assure that somebody means what we mean. However, the context may indeed coincide in all that is relevant to us, either explicitly or implicitly. That's why existentialism is important, because it's important for us that our words and concepts be grounded in the questions relevant to our existence. Gospel Math.

               Axiom schema of replacement      Wikipedia: Less formally, this axiom states that if the domain of a definable function f is a set, and f(x) is a set for any x in that domain, then the range of f is a subclass of a set, subject to a restriction needed to avoid paradoxes. I think this relates to the idea that context allows us to "substitute variables" in different ways and perhaps with different results, different meanings, thus yielding flexibility of interpretation.

Other ways: Math     

                     Edward Cherlin: There are proofs that depend on the algebraic or topological nature of other mathematical structures, where you can't do induction because the underlying sets are not well-ordered. This is the essence of category theory and much of model theory.

          Epsilon induction      Wikipedia: In mathematics,-induction (epsilon-induction) is a variant of transfinite induction, which can be used in set theory to prove that all sets satisfy a given property P[x]. If the truth of the property for x follows from its truth for all elements of x, for every set x, then the property is true of all sets. ... This principle, sometimes called the axiom of induction (in set theory), is equivalent to the axiom of regularity.

          Forcing (in set theory)      Wikipedia In the mathematical discipline of set theory, forcing is a technique invented by Paul Cohen for proving consistency and independence results. It was first used, in 1962, to prove the independence of the continuum hypothesis and the axiom of choice from Zermelo-Fraenkel set theory. Forcing was considerably reworked and simplified in the 1960s, and has proven to be an extremely powerful technique both within set theory and in other areas of mathematical logic such as recursion theory. ... Perhaps more clearly, the method can be explained in terms of Boolean-valued models. In it, any statement is assigned a truth value from some infinite Boolean algebra, rather than just a true/false value. Then an ultrafilter is picked in this Boolean algebra, which assigns values true/false to statements of our theory. The point is that the resulting theory has a model which contains this ultrafilter, which can be understood as a model obtained by extending the old one with this ultrafilter. By picking a Boolean-valued model in appropriate way, we can get a model that has the desired property. In it, only statements which must be true (are "forced" to be true) will be true, in a sense (since it has this extension/minimality property).

     Thought experiments in Computer Science      Wikipedia's list of thought experiments in Computer science: Halting problem (limits of computability), Turing machine (limits of computability), Two Generals' Problem, Dining Philosophers (computer science)

     Thought experiments in Mathematics      Thought experiments in Mathematics: Balls and vase problem (infinity and cardinality), Gabriel's Horn (infinity), Infinite monkey theorem (probability), Lottery paradox (probability), Sleeping beauty paradox (probability)