Introduction E9F5FC

Questions FFFFC0

• View
• Edit
• History
• Print

Math Discovery Examples

Math Discovery Four Levels: 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

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

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

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

• A right triangle is half a rectangle* This morphism is the basis for the area of a right triangle, but also for all of trigonometry, and shows that a function need not be a formula, and shows how two domains - angles and ratios - can be linked, as by shapes. Gospel Math. 1846
• Recasting geometry/combinatorics as parity* Remove the two diagonally opposite corner squares of a chessboard. Is it possible to tile this shape with thirty-one 2 x 1 "dominos"? ... At first, it seems like a geometric/combinatorial problem with many cases and subcases. But it is really just a question about counting colors. The two corners that were removed wre both (without loss of generality) white, so the shape we are interested in contains 32 black and 30 white squares. Yet any domino, once it is placed, will occupy exactly one black and one white square. The 31 dominos thus require 31 black and 31 white squares, so tiling is impossible. pg. 60 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1508

• Apply algebra ideas to a calculus problem* Our final example is also due to Euler. Here the tables are turned: ideas from polynomial algebra are inappropriately applied to a calculus problem, resulting in a wonderful and correct evaluation of an infinite series (although in this case, complete rigorization is much more complicated). ... Is there a simple expression for zeta(2) = 1 + 1/2**2 + 1/3**2 + ... ? Euler's wonderful, crazy idea was inspired by the relationship between zeros and coefficients which says that the sum of the zeros of the monic polynomial x**n + a_n-1 x**n-1 + ... + a1 x + a0 is equal to - a_n-1; this follows from an easy argument that examines the factorization of the polynomial into terms of the form (x-ri), where each ri is a zero. Why not try this with functions that have infinitely many zeros? A natural candidate to start with is sin x ... pg.315 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2251
• Crossover* A crossover ... is an idea that connects two or more different branches of math, usually in a surprising way. ... perhaps the three most productive crossover topics: graph theory, complex numbers, and generating functions. pg.119, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2154
• 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
• e* Determine, with proof, the largest number which is the product of positive integers whose sum is 1976. ... Once again, we shall inappropriately apply calculus to a discrete problem. It makes intuitive sense for the numbers whose sum is 1976 to be equal (see the discussion of the AM-GM inequality...) But how large should these parts be? Consider the optimization question of finding the maximum value of f(x) = (S/x)**x, where S is a positive constant. An exercise in logarithmic differentiation (do it!) shows that S/x = e. Thus, if the sum is S each part should equal e and there should be S/e parts. Now this really makes no sense if S=1976 and the parts must be integers, and having a non-integral number of parts makes even less sense. But at least it focuses our attention on parts whose size is close to e=2.71828... Once we start looking at parts of size 2 and 3, the problem is close to a solution... pg.313 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2250
• Encoding* In contrast [to partitioning], the encoding tactic attempts to count something in one step, by first producing a bijection (a fancy term for a 1-1 correspondence) between each thing we want to count and the individual "words" in a simple "code". ... Instead of partitioning the collection of subsets into many classes, look at this collection as a whole and encode each of its elements (which are subsets) as a string of symbols. Imagine storing information in a computer. How can you indicate a particular subset of S = {a,b,c}? There are many possibilities, but what we want is a uniform coding method that is simple to describe and works essentially the same for all cases. That way it will be easy to count. For example, any subset of S is uniquely determined by the answers to the following yes/no questions. Does the subset include a? Does the subset include b? Does the subset include c? We can encode the answers to these questions by a three-letter string which uses only the letters y and n. For example, the string yyn would indicate the subset {a,b}. Likewise, the string nnn indicates the empty set and yyy indicates the entire set S. Thus There is a bijection between strings and subsets. ... And it is easy to count the number of strings; two choices for each letter and three letters per string mean 2**3 different strings in all. ... Proper encoding demands precise information management. ... try to think carefully about "freedom of choice": ask yourself what has already been completely determined from previous choices ... Beginners are often seduced by the quick answers provided by encoding and attempt to convert just about any counting problem into a simple multiplication or binomial coefficient Note that strings have an additional structure which makes the counting easy: the strings presume a total order of positions, from left to right, whereas the elements of a set need not be ordered. This ordering comes for free and makes the bijection work. pg.213-214 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2208
• Fantasize an answer* When looking at the conclusion of the problem, especially for a "to find" problem, sometimes it helps to "fantasize" an answer. Just make something up, and then reread the problem. Your fantasy answer is most likely false, and rereading the problem with this answer in mind may help you to see why the answer is wrong, which may point out some of the more important constraints of the problem. pg.30, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1428
• Interpreting algebraic variables as coordinates* Whenever a problem involves several algebraic variables, it is worth pondering whether some of them can be interpreted as coordinates. pg. 59 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1505
• 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
• Recast an inequality as an optimization problem* AM-GM reformulated ... we altered our point of view and recast an inequality as an optimization problem. pg.195-196 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2195
• Recasting* [In combinatorics,] the strategy of recasting is especially fruitful: to counteract the inherent dryness of counting, it helps to creatively visualize problems (for example, devise interesting "combinatorial arguments") and look for hidden symmetries. Many interesting counting problems involve very imaginative multiple viewpoints ... to see if a combinatorial identity is true, examine how each side of the equation counts a representative element pg.212, 228 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2205
• Recasting geometry as algebra* Descartes' idea of recasting geometric questions in a numeric/algebraic form led to the development of analytic geometry, which then led to calculus. pg. 60 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1506
• Structural equivalence* Edward Cherlin: Proving that two seemingly unrelated, even apparently incompatible objects are equivalent in some way, or can model each other, is one of the deepest ideas in math.813
  • Brouwer's Intuitionistic logic and set theory* Edward Cherlin: Mathematicians lost interest in Brouwer's Intuitionistic logic and set theory when it was shown that it and the more usual non-constructive logics and set theories can model each other. 817
  • Equivalence of geometries* Edward Cherlin: The fact that each of elliptic/Riemannian, Euclidean, and hyperbolic/Lobachevskian geometries contain models of each other shows that all three are equally valid. For example, a Clifford's surface in Riemannian space and a horosphere in Lobachevskian space both have locally Euclidean geometry. 816
  • Galois theory* Galois theory maps the roots of a given polynomial equation (in field theory) to the Galois group of permutations of the roots. 818
  • String theories are maps of each other* Edward Cherlin: At one time it was thought that there was a vast space of possible String Theories in physics. It turns out that all of them are maps of each other. 815
  • Taniyama-Shimura Theorem* Edward Cherlin: The proof of Fermat's Last Theorem depends on the Taniyama-Shimura Theorem that all elliptic functions are modular, that is, that there is a structure-preserving mapping between elliptic functions and modular forms. 814
• Two different ways* Keeping a flexible point of view is a powerful strategy. This is especially true with counting problems where often the crux move is to count the same thing in two different ways. To help develop this flexibility, you should practice creating "combinatorial arguments". This is just fancy language for a story that rigorously describes in English how you count something. ... Pay attention to the building blocks of "algebra to English" translation, and in particular, make sure you understand when and why multiplication rather than addition happens, and vice versa. Examples include addition (or), multiplication (and), exponentiation, combination, permutation, distinct members, products of choices, sums of choices, complements of combinations. pg.208 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2201

• Make it easier* The easier problem may actually be the more informative, relevant, natural, instructive problem. If the given problem is too hard, solve an easier one. ... For example, if the problems involves big, ugly numbers, make them small and pretty. If a problem involves complicated algebraic fractions or radicals, try looking at a similar problem without such terms. At best, pretending that the difficulty isn't there will lead to a bold solution... At worst, you will be forced to focus on the key difficulty of your problem, and possibly formulate an intermediate question, whose answer will help you with the problem at hand. And eliminating the hard part of a problem, even temporarily, will allow you to have some fun and raise your confidence. pg.18, 31 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1417
• Wishful thinking* It is helfpul to try to loosen up, and not worry about rules or constraints. Wishful thinking is always fun, and often useful. For example, in this problem, the main difficulty is that the top boxes labeled A and C are in the "wrong" places. So why not move them around to make the problem trivially easy? ... Ask yourself, "What is it about the problem that makes it hard?" Then, make the difficulty disappear! You may not be able to do this legally, but who cares? Temporarily avoiding the hard part of a problem will allow you to make progress and may shed light on the difficulties. pg.18, 31 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1416

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

• 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
• Work backwards UCL problem solving technique 4 of 5.
• Restate the problem UCL problem solving technique 5 of 5.
• 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

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

• 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
• Draw pictures UCL problem solving technique 3 of 5
• Draw pictures* In practice, there are several possible methods of showing that a given sequence converges to a limit. ... Draw pictures whenever possible. Pictures rarely supply rigor, but often furnish the key ideas that make an argument both lucid and correct. ... consider the sequence (xn) defined by x0=alpha and x_n+1 = 1/2(x_n + alpha/x_n) ... In the picture below... Notice that the y-coordinate of the midpoint of the line segment AB is the average of these two numbers, which is equal to x_1 ... To show convergence with this picture, we would need to carefully argue why we will never "bounce" away from the convergence point. .... The picture suggests two things: that the sequence decreases monotonically, and that it decreases to square root of alpha. ... The trickiest part in the example above was guessing that the limit was alpha. What if we hadn't been lucky enough to have a nice picture? pg.285-288 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2236
• 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
• Invent a font* The next example combines "Complement PIE" with other ideas, including the useful encoding tool, invent a font, whereby we temporarily "freeze" several symbols together to define a single new symbol. ... Four young couples are sitting in a row. In how many ways can we seat them so that no person sits next to his or her "significant other?" Define Ai to be the set of all seatings for which bi and gi sit together. To compute |Ai|, we have two cases: either bi is sitting to the left of gi or vice versa. For each case, there will be 7! possibilities, since we are permuting 7 symbols: the single symbol bigi (or gibi), plus the 6 other people... Note that alphabetical order in a Spanish language dictionary treats "ch" and "ll" as letters so that "ch" comes after "cz" and "ll" comes after "lz". pg.230 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2212
• 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
• Create notation* You can make progress on a math problem simply by creating a relevant notation for it, which allows you to think about it in a new way, in a new level.2256

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