Links and Support Files for

Discrete Mathematics with Ducks

by dr. sarah-marie belcastro

GeoGebra files:

3.5 Graphs: Definitions and Examples
Fig. 3.8 bipartite graph

3.6 Isomorphisms
Fig. 3.11 graphs
Fig. 3.12 graphs

3.8 Try This! More Graph Problems
Fig. 3.21 graphs
Fig. 3.22 graphs
Fig. 3.23 graphs
Fig. 3.24 graphs

Bonus Graph Isomorphism exercises available only here on the web!

11.2 Try This! Planarity Explorations
Fig. 11.1 left graph
Fig, 11.1 right graph

Additional Problems
6. graphs
51. graph
52. graph

Mathematica Demonstration: (for Chapter 9) Cutting Space into Regions with Four Planes

Mathematical links mentioned in the text:

Frontmatter

• The Art of Problem Solving

Chapter 2 (Sets and Logic)

• Click to shade parts of an Interactive Venn Diagram (requires Mathematica or free CDF Player) and the demonstration shows the set notation for the corresponding set and its complement.
• The Venn Game applet has you click on a set-notation description and then shades the corresponding regions of a Venn diagram.
• This "quiz" shows a 3-set Venn diagram and a symbolic description of a set. You have to figure out which regions should be shaded. The interface doesn't actually shade the diagram; on the other hand, it does give you feedback, and reloading the page produces a new problem each time.
• This short quiz asks you to decide whether the given statements are true. Reloading gives a new quiz for even more practice.
• The Propositional Logic Puzzle Generator (requires Mathematica or free CDF Player) shows some polygons along with a list of statements about the polygons in logic notation. (The logic notation is not quite the same as used in Discrete Mathematics with Ducks, but there is a `help' option that explains it.) Each statement is marked as true or false. The trick is that the polygons are not labeled but referred to in the statements as A, B, C, etc. and you get to match the labels with the polygons.
• The puzzles Logic with Letters, 2D Logic Game with Letters, and Logic with Logicians (all require Mathematica or free CDF Player) do not use formal logic notation but give practice in logical thinking.
• Here you are presented with a mostly blank truth table---it just has headers and a few beginning columns. Fill in the truth table by clicking, and then hit buttons that check your work, clear the table, and reveal answers if you so choose. Reloading the page produces a new blank truth table. Warning: this "quiz" uses a single arrow for implies instead of the double arrow we use in Discrete Mathematics with Ducks.
• For a good survey of what's known about Venn diagrams, go here.
• The logic puzzle generators Knights and Knaves Puzzle Generator, Knights, Knaves, and Normals Puzzle Generator, and Another Knights and Knaves Puzzle Generator (all require Mathematica or free CDF Player) generate collections of statements. You decide which speakers are knights (who tell the truth) and which are knaves (who lie). The software has options to translate each statement into logic notation and to reveal the solution to each puzzle.
• In this clever text-adventure game, the player has to solve logic puzzles in order to travel through a labyrinth and to advance game levels.

Chapter 3 (Graphs and Functions)

• Play the dot game.
• Experiment with different 2-colorings of the edges of various complete graphs at Graphs and Their Complements (requires Mathematica or free CDF Player).
• As you draw some vertices/edges, this applet produces the graph complement in real time.
• As you draw the graph vertex by vertex and edge by edge, this applet constructs the corresponding adjacency matrix.

Chapter 4 (Induction)

• Applets that allow you to tile 8 x8 and M x N grids with L-shaped tiles.

Chapter 5 (Algorithms with Ciphers)

• Practice basic modular arithmetic with this quiz, which tells you if you are correct or not, but doesn't reveal answers; reloading the page produces a new quiz.
• Collatz Problem gives a summary of the history, current state of knowledge, and related generalizations of the Collatz Conjecture.
• Computational Verification of the 3x+1 Conjecture
• Automate encryption/decryption for shift ciphers
• Automate encryption/decryption for the standard Vigenere cipher
• Information on public key cryptography by RSA Labs
• Graph Searching Breadth First and Depth First (requires Mathematica or free CDF Player) gives you a slider to control how many steps of the search have been done.
• The Pigeonhole Principle Repunits (requires Mathematica or free CDF Player) lets you explore which numbers divide numbers like 111, 1111, 11111, etc.

Chapter 6 (Binomial Coefficients and Pascal's Triangle)

• Find Math Curse at your local library.
• This BubbleSort applet shows the eponymous algorithm in action and highlights lines of code as it goes.
• Download (.pdf) Donald E. Knuth's The Computer as Master Mind. (.pdf) J. Recreational Mathematics, 9 (1) (1976-77), 1--6.

Chapter 8 (Recurrence)

• MacTutor History of Mathematics Archive biography of Fibonacci
• OEIS lookup service and overall description
• The Fibonacci Quarterly (back issues freely downloadable) publishes the latest research and exposition on Fibonacci numbers.
• The Journal of Integer Sequences (free) is devoted to research involving integer sequences.
• Play with theTower of Hanoi.

Chapter 9 (Counting and Geometry)

• David Eppstein's Geometry in Action page is an extensive directory of applications of discrete and computational geometry.
• Play a solitaire version of SET
• Lots of information about the physical card game SET
• Preprint of The card game Set (.pdf) by Ben Davis and Diane Maclagan, published in The Mathematical Intelligencer, Vol. 25, No. 3 (Fall 2003), pp. 33--40.

Chapter 10 (Trees)

• This applet shows Kruskal's algorithm executed step-by-step on a single graph.
• This applet generates a variety of graphs with step-by-step executions of Kruskal's algorithm.
• This applet generates graphs on which Prim's algorithm is worked step-by-step.
• This applet allows you to generate a large graph and then will find a minimum spanning tree of that large graph in real time.
• For an example of the branch-and-bound algorithm, go here and choose option 10. This opens two windows: one holds the tree and the other shows blocks that can be used to fill a bag. You can have the software step through the algorithm, or you can explore the tree via the (show entire tree) button.

Chapter 11 (Euler’s Formula)

• Planarity. (No more need be said.)
• At least 19 proofs of Euler's Formula.
• Play with Proving Eulers Polyhedral Formula by Deleting Edges (requires Mathematica or free CDF Player).
• Toroidal Wrapping (requires Mathematica or free CDF Player).
• A summary of the classification of topological surfaces.
• Details of the classification of topological surfaces (.pdf).

Chapter 12 (Traversals)

• Practice finding Euler paths and Hamilton paths at this site.
• Recent research and results related to TSP.
• An example of Dijkstra's algorithm in action
• Generate a variety ofstep-by-step examples of Dijkstra's algorithm
• Some decent approximations to TSP solutions (requires Mathematica or free CDF Player).
• This applet will help you generate a large graph and then demonstrate a variety of algorithms for TSP on this graph.
• Optimizing Dispersal Corridors for the Cape Proteaceae Using Network Flow (.pdf) by Steven J. Phillips, Paul Williams, Guy Midgley, and Aaron Archer, in \emph{Ecological Applications}, 18(5), 2008, pp. 1200--1211.

Chapter 13 (Coloring)

• Practice coloring the vertices of graphs properly.
• A detailed account of the use of vertex coloring to solve a mechanical drilling problem.
• A brief history of the Four Color Theorem and a somewhat technical explanation of the 1995 proof
• Four-color some graphs (requires Mathematica or free CDF Player) and maps (warning: uses Flash!).

Backmatter and References

• MacTutor History of Mathematics biography of Pascal
• Discrete Mathematics with Algorithms by Michael O. Albertson and Joan P. Hutchinson, Wiley, 1988.
• Combinatorics Through Guided Discovery (.pdf) by Kenneth P. Bogart, 2004.
• Book of Proof by Richard Hammack, Department of Mathematics & Applied Mathematics
  Virginia Commonwealth University Mathematics Textbook Series, 2009.
• Discrete Mathematics (Lecture Notes, Yale University, Spring 1999) by László Lovász and Katalin Vesztergombi}.
• MIT OpenCouseWare

Less- and Non-mathematical links:

• Find Ducks! at your local library.
• Minimal Criminal is a band.
• WEBS is a real store.
• At Chicago O'Hare International Airport, there are an average of 1,042 flights per day.
• The mean age at which a child-bearing woman has her first child is 25 (as of 2007).
• An upper bound estimate for the cumulative population of the world for the last 1000 years can be made using this data.
• How to know how many ---- you can shake a stick at.
• They really do grow rice on Iki Island. And historically, there really were pirates (use google translate) inhabiting the island!
• Dijkstra's algorithm is fairly efficient, and so is often used in practice for applications such as IP routing\dots but it is not actually fast enough to be used in Google Maps.
• A game was marketed with the board for the Icosian game, but laid out over the head of a mushroom-like object.
• The Egg Yolk Wasn't Here building.
• Terry Moore's Kixie
• The Donuts.
• Cake Wrecks blog.
• Big Bird singing the abcdefghi... song.
• A Doctor Who clip (from The Pyramids of Mars) containing a truth-tellers problem that starts about 9.5 minutes in (if you want more context, start at 8 minutes).

Errata for the first printing:

page 136, second box, the last three numbers in the last line should be 8 18 1.

page 200, Example 7.4.8, PARALLELOGRAM should have 13!/(3!2!3!) anagrams.

page 217, problem 15, the course Physics-with-Calculus II should just be Physics II.

page 237, step 10 should read a_n = (1/6)3ⁿ + (1/2)(-1)ⁿ .

page 353, proof of Theorem 12.4.2, the Hamilton path should be P = v_b-...-v_n-v₁-v₂-...-v_a and the parenthetical remark in the following paragraph should read: (V_a lists the subscripts for the vertices adjacent to v_a, and V_b lists the subscripts for the vertices following those adjacent to v_b.) Notice that neither V_anor V_bcontains v_a because v_a is not adjacent to itself and no vertex follows v_a in the path (and even using the labeling order, v_b is not adjacent to itself).

page 416, Theorem 14.7.3 only holds for graphs with at least 4 vertices.

page 493, answer to Section 3.6 Check-Yourself problem 2: the list should include P₄.

page 500, answer to Section 6.7 Check-Yourself problem 2: 4³ should be (-4)³ so that the answer is -1,280.

page 514, answer to Section 14.3 Check-Yourself problem 1: When using the Lemma, we have only one state (seeing all four ducks) so E[W] = 4x1=4 white ducks and E[WH] = 1x1 = 1 white duck.

page 515, answer to Section 14.3 Check-Yourself problem 2(b): The black duck appears in 8 of the subsets, so E[B] = 1/2.

Errata for the first and second printings:

page 121, step 4 should read "If k=10, output k, and stop; otherwise, go to step 2."