Math 4 Wisdom. "Mathematics for Wisdom" by Andrius Kulikauskas.

Math Discovery Six Pairs: 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

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

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 )

Tree of variations

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

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

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.2159
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
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.1640
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
- 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

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

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
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, Inc2216
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
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, Inc2217
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
- 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. See also Dmitri's game!1763
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.2161
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.1512

Total order

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

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

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, Inc2228
Permutations* Permutations are the ways of reordering a collection of objects, all distinct. A permutation labels a total order. 2199
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
- 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".

1764

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

Powerset lattice

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

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

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.1529
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.2174
Polya's pattern of two loci* 899
- Illustrative example* 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.

The solver's thought process leveraged a deep math structure: the powerset lattice of conditions: {{X,Y}, {X}, {Y}, {}}. The solver envisaged the solution as the union of two conditions. In this deep structure, there is no reference to triangles, circles, lengths, continuity or the plane, all of which turn out to be of superficial importance. Here the crux, the mental challenge of the problem, is expressed exactly by the powerset lattice. And, notably, that is a mathematical structure! Math is the deep structure of math! 900

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

Creative rethinking* Many creative methods have us rethink, reorganize, untangle, recombine the conditions that define a problem.909
- 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

Mind Your Decisions. Can you crack these 2 logical puzzles? Each picks whole number 1 to 30. A: Is your number double mine? B: I don't know. Is your number double mine? A: I don't know. Is your number half mine? B: I don't know. Is your number half mine? A: I don't know. B: I know your number.

The way to solve this is to actually consider each of the possibilities specifically. Then we see that certain possibilities are forbidden. They would lead to an answer "no" rather than "I don't know". If a number is odd, then it can't be double. If a number is greater than 15, then it can't be half. As the conditions grow, we find that the number is 4. This is in the spirit of examination of cases.

Decomposition

Decomposition* Vary model (can variously combine factors) (Pigeonhole principle, partitions, factorizations, encoding, full range of outputs, principle of inclusion-exclusion) 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

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
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, Inc2211
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
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
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.1392
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, Inc2207
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
- 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.1637
- 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
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, Inc2210

Directed graph

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

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

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
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 )1530
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
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.2156