How do you figure things out?78 ways
Choose from the domains above.
Write to Andrius (MS@MS.LT) to add more ways!
Research & Culture & Business

          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.1412

          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.1414

          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.1423

          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.1424

        Space

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.10

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

               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.1645

          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.1522

               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.1523

          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.1521

          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.1650

          Notation      Adding notation is typically referencing everything with regard to an origin, a reference point. We need some "notation". Let us assume that there is a universal coordinate system, such as longitude and latitude, so that we can refer to the "same" location on any planet. For example, if the planets were little balls floating in a room, the location "north pole" would mean the point on a planet which was closest to the ceiling. Given such a universal coordinate system, what can we say about a planet P which has a private point at location x? pg. 64 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1520

          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. 1378

               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. 1380

          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. 1742

          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. 1746

          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. 1744

          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. 1379

          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.1511

               127 people in a tennis tournament      If 127 people play in a singles tennis tournament, prove that at the end of the tournament, the number of people who have played an odd number of games is even. ... each game has exactly two people playing it... the sum counts every game that has been played exactly twice! ... the sum above is even, and is a sum of an odd number (127) of elements. If an odd number of them were odd, the sum would not be even... pg. 102, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1644

               Parity problem: Dominos on a chessboard      Remove the two diagonally opposite corner squares of a chessboard. Is it possible to tile this shape with thirty-one 2 x 1 "dominos"? ... At first, it seems like a geometric/combinatorial problem with many cases and subcases. But it is really just a question about counting colors. The two corners that were removed wre both (without loss of generality) white, so the shape we are interested in contains 32 black and 30 white squares. Yet any domino, once it is placed, will occupy exactly one black and one white square. The 31 dominos thus require 31 black and 31 white squares, so tiling is impossible. pg. 60 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1509

          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.1743

        Sequence

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.17

               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.1161

          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.1440

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

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

          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. 1739

          Use of extreme principle with induction      Often, problems involve the extreme principle plus a particular argument style, such as contradiction or induction. A common tactic is to use the extremes to "strip down" a problem into a smaller version ... The formal argument then uses induction. ... Several positive integers are written on a blackboard. One can erase any two distinct integers and write their greatest common divisor and least common multiple instead. Prove that eventually the numbers will stop changing. pg.85, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1633

          Well-Ordering Principle      Every non-empty set of positive integers has a least element. pg.83, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1631

               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. 1748

          Finite Injury Priority Method      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".1660

        Limits

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). 20

          Infinite Injury Priority Method      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".1661

          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.1642

          Stretching things      Three women check into a motel room which advertises a rate of $27 per night. They each give $10 to the porter, and ask her to bring back 3 dollar bills. The porter returns to the desk, where she learns that the room is actually only $25 per night. She gives $25 to the motel desk clerk, returns to the room, and gives the guests back each one dollar, deciding not to tell them about the actual rate. Thus the porter has pocketed $2, while each guest spent 10-1 = $9, a total of 2 + 3 x 9 = $29. What happened to the other dollar? ... try stretching things a bit: what if the actual room rate had been $0? Then the porter would pocket $27 and the guests would spend $27, which adds up to $54! pg. 22, 102, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1649

          Topologically equivalent      ... the original problem was almost immediately equivalent to the modified easier version. That happened for a mathematical reason: the problem was a "topological" one. This "trick" of mutating a diagram into a "topologically equivalent" one is well worth remembering. pg.19, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1418

          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.1641

          Geometric series tool      Let 1=a0=a1=a2=... Then the corresponding generating function is just 1 + x + x**2 + x**3 + ... This is an infinite geometric series which converges to 1/(1-x), provided that |x|<1 pg.144, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2165

          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.1427

               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.1170

               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.1586

          Geometric symmetry      The simplest geometric symmetries are rotational and reflectional. pg. 71 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1582

               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.1584

               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.1583

          Invariant with respect to transformations      this topic [symmetry] is logically contained within the concept of invariants. If a particular object (geometrical or otherwise) contains symmetry, that is just another way of saying that the object itself is an invariant with respect to some transformation or set of transformations. For example, a square is invariant with respect to rotations about its center of 0, 90, 180 and 270 degrees. pg. 103, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1646

          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.1581

          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.1524

          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.1579

        Truth

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.14

          Argument by contradiction      Instead of directly trying to prove something, we start by assuming that it is false, and show that this assumption leads us to an absurd conclusion. A contradiction argument is usually helpful for proving directly that something cannot happen. ... When you begin thinking about a problem, it is always worth asking, What happens if we negate the conclusion? Will we have something that is easier to work with? If the answer is "yes", then try arguing by contradiction. pg.46, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1439

               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.1438

          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.1648

          Recast a problem from one domain into another domain      The powerful idea of converting a problem from words to pictures is just one aspect of the fundamental peripheral vision strategy. Open your mind to other ways of reinterpreting problems. ... what appeared to be a sequence of numbers was actually a sequence of descriptions of numbers ... Another example was the locker problem in which a combinatorial problem metamorphosed into a number theory lemma. "Combinatorics <=> Number Theory" is one of the most popular and productive such "crossovers", but there are many other possibilities. Some of the most spectacular advances in mathematics occur when someone discovers a new reformulation for the first time. pg. 60 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1507

          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.1437

          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. 1383

          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.1519

               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.1165

          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.1422

          Draw a picture      I imagine that drawing a picture brings out its inner logic at the level of "icon" or "what". Central to the open-minded attitude of a "creative" problem solver is an awareness that problems can and should be reformulated in different ways. Often, just translating something into pictorial form does wonders. pg.59, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1502

          Drawing the monk problem      A monk climbs a mountain. He starts at 8 am and reaches the summit at noon. He spends the night on the summit. The next morning, he leaves the summit at 8am and descends by the same route he used the day before, reaching the bottom at noon. Prove that there is a time between 8 am and noon at which the monk was at exactly the same spot on the mountain on both days One solution is to draw the paths on a distance-time graph, which makes it clear that the paths must cross and so they must meet. The pictures brings out the two conditions and shows how they come together. pg.19, 59 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1504

          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.1425

          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.1421

          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.1510

        Restructuring

Restructuring      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)
I expect that they relate 0 Truth, 1 Model, 2 Implication, 3 Variable as follows ... I expect that each geometry reflects a particular way that we're thinking about a variable. I expect them to illustrate the six qualities of signs... Consider the geometry suggested by (6 of the 8) axioms of Zermelo-Fraenkel set theory, for example, the power set axiom. These are axioms for restructuring.15

     Models of Multiplication      Six ways of thinking of multiplication: Fractal, Proportion, Tally, Box, Label, Divide out. (Andrius thinking out loud) I think that the six pairs of levels, six kinds of variables, six Zermelo-Frankel axioms of set theory can be illustrated by models of multiplication as Maria Droujkova has been studying. Question: What does it mean to cancel out units as physicists do?

  • The addition rule is at work, adding exponents. Multiplying by 10 or dividing by 10 shifts the number with regard to the decimal point, although it looks like the decimal point is moving. We may think of this as simply changing the units, the base unit.
  • I think of rescaling as a product of actions that either make bigger (numerator) or make smaller (denominator). They are all multiplying against some unknown, acting upon it. I call the actions "multiplication drops", either "magnifying drops" (say, multiplying by 10) or "shrinking drops" (dividing by 10). So these are actions x actions x (object with units). Thus magnifying and shrinking can cancel out. Also, actions can be decomposed into component actions, into primes.
  • Repeated addition is a recounting, a shift from larger units to smaller units. 3 x (23 x dollars) becomes (3 x 23) x dollars. Amount x (large unit) becomes action x (amount x small unit) becomes (action x amount) x small unit becomes amount x small unit.
  • Multiplication can give the ways of matching units, multiple units times multiple units, as in box multiplication, accounting for all possibilities. Units times units means that conditions are satisfied, thus generating all of the solutions.
  • Multiplication can be thought of as counting items that have been grouped where each group has the same number of items. For example, we can count coins by grouping together the pennies, nickels, dimes, quarter, placing them in rows or groups of 4 or 5 or 10. Number x (Value x Unit).
  • Dividing out, for example, money per person. This is like multiple units. (Number of cycles) x (Number of people x Units )
1531

               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".1168

          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.1639

          Fractal multiplication: Recopying the whole      A whole can be recopied (however many copies), then again, then again. This is like fractal multiplication, as with your five-legged starfish whose each leg holds another five-legged starfish. It is like multiplying by powers of 10. The addition rule is at work, adding exponents as in (10**2)(10**3) = 10**5. Multiplying by 10 or dividing by 10 shifts the number with regard to the decimal point, although it looks like the decimal point is moving. We may think of this as simply changing the units, the base unit, which may be unknown.1526

               All parabolas have the same shape      I've found in teaching the quadratic equations (and searching for a use for them) that the parabola is arguably an ideal curve for learning to graph. That's because all parabolas have one and the same shape, if you discount zooming in and out. Each parabola, if you zoom in, will look flat, and if you zoom out, will look narrow, in exactly the same proportions. You can see this if you substitute x -> ax and y->ay and thereby you can transform x = y**2 to xa = y**2 a**2 so x = a y**2 effectively where a can be as you like. This means that all parabolas look the same and their graphs differ only in how you move them around, up and down, left or right, negative or positive, zoom in or zoom out. Also, I teach my students to draw too graphs because most never realize how the parabola completely flattens out at the bottom where -1 < x < 1. It's a bit like filming a movie where you have to combine full length shots of people with head shots. One shot won't do it. Gospel Math.1841

               Axiom of extensionality      Wikipedia: Two sets are equal (are the same set) if they have the same elements. Note that there are thus two levels of equality. Equality is a bidirectional relationship. And the two levels are like levels of an atlas. An atlas defines, at different levels, what can be consider the "same" point or location from far away, though may be different from close up. The "equivalence" and equivalence classes may be "turned on or off" selectively in the atlas.1164

          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. 1745

          Graph      Just about any situation involving "relationships" and "objects" can be recast as a graph, where the vertices are the "objects" and we join vertices with edges if the corresponding objects are "related". pg.120, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc. 1752

               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. 1754

               Sleeping mathematicians      During a certain lecture, each of five mathematicians fell asleep exactly twice. For each pair of these mathematicians, there was some moment when both were sleeping simultaneously. Prove that, at some moment, some three of them were sleeping simultaneously. pg.120, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc. 1753

          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. 1527

          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.1501

          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.1528

               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.1160

               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. 1382

          Reimagining the monk problem       A monk climbs a mountain. He starts at 8 am and reaches the summit at noon. He spends the night on the summit. The next morning, he leaves the summit at 8am and descends by the same route he used the day before, reaching the bottom at noon. Prove that there is a time between 8 am and noon at which the monk was at exactly the same spot on the mountain on both days One solution is to allow for two monks traveling, one up and the other down, so that it is clear they must meet. In this way the solution is where the two conditions are both satisfied. pg.19, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1503

        Decomposition

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)72

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

               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.1843

               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.1842

          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.2198

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

          Complete the square      2185

          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. 1740

          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.2173

          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.2169

          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.2176

          Factoring      Here is a simple problem with a "complete" solution, illustrating one of the most important tactics: factoring. ... Find all right triangles with integer sides such that the perimeter and area are equal. ... xy/2 = x + y + square root of (x**2 + y**2) ... xy - 4x - 4y + 8 = 0 ... Now we do something clever: add 8 to both sides to make the left-hand side factor. We now have (x-4)(y-4) = 8, and since the variables are integers, there are only finitely many possibilities ... The only tricky step was finding the factorization. But this wasn't really hard, as it was clear that the original left-hand side "almost" factored. As long as you try to factor, it usually won't be hard to find the proper algebraic steps. The factor tactic is essential for finding solutions. pg.264-265 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2225

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

          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. 1749

          Intermediate pigeonhole      If you have p pigeons and h holes, then at least one of the holes contains at least [p/h] pigeons. pg.94, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1638

          Number theoretic functions      Of the infinitely many functions with domain N, we will single out a few that are especially interesting. Most of these functions are multiplicative ... f(ab) = f(a)f(b) whenever a and b are relatively prime ... Define sigma_r(n)= sum over divisors d of n of d**r ... Let F(n) = sum over divisors d of n of f(d). If f is multiplicative, then F will be multiplicative as well. Define phi(n) to be the number of positive integers less than or equal to n which are relatively prime to n. ... We can use the principle of inclusion-exclusion to evaluate phi(n) ... We define [the Mobius function] mu(n) = 1 if n=1, =0 if p**2 divides n for some prime p, = (-1)**r if n = p1p2...pr, each p a distinct prime. This is a rather bizarre definition, but it turns out that the Mobius function very conveniently "encodes" PIE. ... show that sum over divisors d of n of mu(d) = 1 if n=1; =0 if n>1. The values of mu(n) alternate sign depending on the parity of the number of prime factors of n. This is what makes the Mobius function related to PIE. ... phi(n) = sum over divisors d of n of mu(d)(n/d). pg.257-261 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2221

          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.2197

          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.2167

          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.1635

               Two points a mile away      Every point on the plane is colored either red or blue. Prove that no matter how the coloring is done, there must exist two points, exactly a mile apart, which are the same color. ... imagine the vertices of an equilateral triangle with side length one mile. There are three vertices, but only two colors available! The pigeonhole principle tells us that two vertices must be the same color! pg.93, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1636

          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. 1741

          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. 1377

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

        Directed graph

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

          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.2157

          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.2184

          Eulerian Path      Find the conditions on a connected graph (or multigraph) for which it is possible to travel a path that traverses every edge exactly once. Such paths are called Eulerian ... A connected graph (or multigraph) possesses an Eulerian path if and only if it has zero or exactly two odd-degree vertices. In the former case, the path is a closed path. In the latter, the path must begin and end at the odd-degree vertices. pg.123-124, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2158

          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.2160

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

          Viewing a problem modulo m      Viewing a problem modulo m for a suitably chosen m is a wonderful simplification tactic because it reduces the infinite universe of integers to the finite world of Zm. You have encountered this idea before with parity ... which is just the case m=2 ... Often (but not always) we turn to prime values of m, since primes are simpler, more "fundamental" objects which are generally easier to understand. In general, When beginning a number theory investigation, assume that the variables are prime or at least relatively prime. Often the general case follows from the prime case, with just a few "technical" details. ... Fermat's Last Theorem. Let n>=3. Prove that the equation x**n + y**n = z**n has no non-zero integer solutions. ... we shall point out two simplifications ... Without loss of generality, n is prime ... we may assume that ... x, y, z have no common factor (other than 1). ... One reason that primes are so convenient is that unique "multiplicative inverses" exist. Viewing modulo m emphasizes the closed nature of a system. pg.252-253 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2219

               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.1840

               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.1169

        Other ways: Math

Other ways: Math      819

               Alternatives to mathematical induction      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.812

          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.1578

          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).1159

     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)857