Arthur Benjamin – Discrete Mathematics

A good friend of the Metroplex Math Circle, Dr. Arthur Benjamin, has just released a new lecture course through the Teaching Company titled “Discrete Mathematics.” We have our pre-ordered copy and its seems to have the unique combination of humor and depth that we know from Dr. Benjamin’s excellent “mathemagic” presentations.

For any students just starting with Math Circles, they will benefit greatly from becoming familiar with the topics on these DVDs: number theory,  combinatorics and graph theory.

Here is the description of the course from the Teaching Company:

Welcome to Discrete Mathematics, a subject that is off the beaten track that most of us followed in school but that has vital applications in computer science, cryptography, engineering, and problem solving of all types.

Most of the mathematics taught after elementary school is aimed at preparing students for one subject—calculus, which is the mathematics of how things grow and change continuously, like waves in the water or clouds in the sky. Discrete mathematics, on the other hand, deals with quantities that can be broken into neat little pieces, like pixels on a computer screen, the letters or numbers in a password, or directions on how to drive from one place to another.

While continuous mathematics resembles an old-fashioned analog clock, whose second hand sweeps continuously across a dial, discrete mathematics is like a digital watch, whose numbers proceed one second at a time. As a result, discrete mathematics achieves fascinating mathematical results using relatively simple means, such as counting.

Explore this modern realm of digital math in Discrete Mathematics, 24 mind-expanding lectures by veteran Teaching Company Professor Arthur T. Benjamin, an award-winning educator and mathemagician who has designed a course that is mathematically rigorous and yet entertaining and accessible to anyone with a basic knowledge of high school algebra.

“Hairy Circles” – Recap

Dr. Paul Stanford departed from our recent lectures on applied mathematics and contest preparation to give our students a glimpse into the fascinating world of pure mathematics.  Dr. Stanford is particularly skilled at teaching deep ideas without the need to resort to complex algebra, I’ll attempt in this recap to do his lecture a small bit of justice.

Dr. Stanford began with one of the simplest concepts, points on a plane and arrows connecting those points.  Many of these arrows considered together and connecting a set of points yield all sorts of interesting directed graphs or “digraphs.“  This idea becomes more interesting when restrictions are imposed such as the rule that no two arrows can originate from the same point.  When a sequence of arrows loop back upon themselves they form a shape like a “hairy circle” from the title of the lecture.

Dr. Stanford further restricted the cases with the following rules:  no two arrows can connect to the same point and no symmetry is allowed.    These restrictions yielded only four possibilities including those with only a single point connecting back on itself and the possibility of having no points or arrows at all.

Dr. Stanford then proceeded to show how basic arithmetic could be carried out in each of these four systems by shifting along the chains of arrows and by considering the very special case of the arrow that points back to its own origin.

In the second half of the lecture, Dr. Stanford built upon this foundation as he introduced the Collatz Problem:

Think of a number.

If it is even, divide by two.

Otherwise, triple it and add one.

Repeat.

Does this always reach one?

Dr. Stanford lead the students through multiple examples using positive integers, some of which filled both whiteboards but eventually came back to one.  In fact Dr. Stanford told us that while this process always yields one for numbers from 1 to ,  nobody has proven that it is true of all positive integers!  Dr. Stanford reminded the students that for mathematicians multiple examples are not “proof” and that numbers even as large as 23 thousand, trillion are not especially large to mathematicians.

However, when Dr. Stanford started the Collatz problem with negative integers, it was common that loops would appear.  Drawn on the board, the chain of calculations was strangely similar to the hairy circles from the previous lecture.  This lead to a discussion of how one could detect when loops appear in an algorithm.  At this point the lecture began to  bridge between pure mathematics and some real problems in computer science.

One method for detecting a loop would be to track and remember every point in the path but this would burden even the most powerful computer.  A more clever method is the “tortoise and the hare” strategy.  This involves sending two runners through the system, one moving twice as quickly as the other.

Dr. Stanford proved how this method would eventually prove the existence of a loop and how a second tortoise could confirm the exact point where the loop begins.

The two lectures formed an exciting and satisfying trip through the world of numbers.  If I have misrepresented or ignored pertinent points from the lecture please feel free to mention them in the comments section below.

Happy October 23

What is so special about October “23″? Well, as Dr. Paul Stanford has proven in his lectures there are interesting facts about every number! Here is what he has to say about the number 23. If you have any other facts to add or if you see any mistakes in my transcription of Dr. Stanford’s notes please use the comments below.

23 is…

The largest number not the sum of distinct powers.

With 23 people in a room, odds are that two share a birthday (better than 50:50.)

Prime, smallest odd prime not a twin.

Woodall number.

One of the only two numbers that need 9 cubes. (The other is 239.)

If negatives allowed,

23 is the smallest number of rigid rods that brace a square.

First prime where 23rd roots of unity form cyclotomic integers without unique factorization.

Number of trees with eight nodes.

Factor of

is composite:

Sophie Germain prime: 2(23)+1 also prime.

Wedderburn-Etherington number.

The first pillar prime.

Dr. Bennette Harris Recap

The second lecture of the season provided lessons in both applied mathematics and number theory. Dr. Bennette Harris began with an easy to follow introduction to binary and computer operations including XOR. He then defined the terms “encoding” and “encryption” and gave several examples of early encryption methods.

Dr. Harris described the difference between “strong” and “weak” encryption methods. This led to a deep dive into the popular RSA encryption method which depends on extremely large prime numbers. Dr. Harris used this as an opportunity to give the students a sense for mind-boggling large numbers and some of the very creative and efficient ways of determining whether or not a given number is a prime.

In this part of the discussion, Dr. Harris taught the students various techniques in modular arithmetic. Modular arithmetic is a tool that is not just useful in encryption but is critical for success in math contests and other pursuits.

Dr. Harris used several techniques to engage students including a series of 10 problems that he worked into the lecture for the students to solve. He also demonstrated the UBASIC program which very quickly found tremendously large prime numbers.

Dr. Harris has provided his slides from the lecture and answers to the problems. Members of the Metroplex Math Circle e-mail group can download these files from the group site. To join the e-mail group simply click below.

Click to join MetroplexMathCircle

Dr. Bennette Harris – Problem Set 2

Here is the continuation of Dr. Bennett Harris’ problems to warm us up before his lecture on September 27th. Congratulations to Dominic for being the first to answer the previous set of problems in the comments. Another happy discovery is the fact that WordPress, which hosts this site, supports the use of code!

Problems

A solution for each of the following should either give the correct answer, or a technique for determining the answer in reasonable time with the assistance of a calculator.

6. Crack this secret message: “uifsfaxjmmacfabmnptuaopaqsppgtaupebz”

7. Code the alphabet a=0, b=1, …, z=25, space=26. We will encrypt each letter of the alphabet by mapping it to the letter 3 farther along in the alphabet. Thus, a maps to d, b maps to e, and so forth. The message “a bat is fat” would be encrypted as “dcedwclvciodw” in this scheme. Find a mathematical function f(x) such that y=f(x) gives the correct encryption for every value x = 0,1,2,…,26. Test your function by encrypting “the toy boat floats”.

8. The purpose of these two questions is to provide points of comparison for the questions that follow:
How many particles are there in the known universe?
How many microseconds have elapsed since the beginning of the universe?

9. How long (approximately will do) would it take to calculate at 1,000,000 calculations per second? How many digits does the answer have? If p is 200 digits long, and if q is 200 digits long, about how many digits are there in pq?

10. The number – 1 is known to be prime. Estimate how long it would take a computer to demonstrate this by repeated division, at 1,000,000 divisions per second.

Dr. Bennette Harris – Problem Set 1

This Saturday’s (9/27) Math Circle lecture by Dr. Bennett Harris on “Computer Data Encryption – Decrypted” promises to be a great combination of number theory and applied math. To warm up the students, Dr. Harris forwarded some problems that I will post in two parts. Feel free to offer solutions in the comments or to just work them on your own. Full solutions will be made available at the next Math Circle.

Problems

A solution for each of the following should either give the correct answer, or a technique for determining the answer in reasonable time with the assistance of a calculator.

1. How many prime numbers are there? Prove your answer.

2. What is the largest number you must test to demonstrate that 83 is prime?

3. What is the smallest 5-digit prime? How could you find this number?

4. Is 1234567890 prime? What about 123456789?

5. Assume an alphabet with 26 letters (plus a blank space). A substitution cipher is a one-to-one mapping of this alphabet onto itself. How many such substitution ciphers are there?

Problem Solving Books

In addition to being the subject of books like Count Down, the Director of Metroplex Math Circle, Dr. Titu Andreescu is also the author of multiple books on problem solving. These books draw on his many years of experience as the director of AMC, coach of the US International Math Olympiad team and author of many contest problems.

To help the Metroplex Math Circle community we have created an Amazon List with some of Dr. Andreescu’s currently available books. In addition to Dr. Andreescu’s books for experienced problem solvers we have also included some books and resources on the list for students just starting into problem solving.

Not only does Metroplex Math Circle benefit from Dr. Andreescu himself, but many of his co-authors are also friends of MMC and frequent lecturers.

Following are the author descriptions from the book 104 Number Theory Problems: From the Training of the USA IMO Team:

About the Authors

Titu Andreescu received his Ph.D. from the West University of Timisoara, Romania. The topic of his dissertation was “Research on Diophantine Analysis and Applications.” Professor Andreescu currently teaches at The University of Texas at Dallas. He is past chairman of the USA Mathematical Olympiad, served as director of the MAA American Mathematics Competitions (1998–2003), coach of the USA International Mathematical Olympiad Team (IMO) for 10 years (1993–2002), director of the Mathematical Olympiad Summer Program (1995–2002), and leader of the USA IMO Team (1995–2002). In 2002 Titu was elected member of the IMO Advisory Board, the governing body of the world’s most prestigious mathematics competition. Titu co-founded in 2006 and continues as director of the AwesomeMath Summer Program (AMSP). He received the Edyth May Sliffe Award for Distinguished High School Mathematics Teaching from the MAA in 1994 and a “Certificate of Appreciation” from the president of the MAA in 1995 for his outstanding service as coach of the Mathematical Olympiad Summer Program in preparing the US team for its perfect performance in Hong Kong at the 1994 IMO. Titu’s contributions to numerous textbooks and problem books are recognized worldwide.

Dorin Andrica received his Ph.D. in 1992 from “Babes-Bolyai” University in Cluj-Napoca, Romania; his thesis treated critical points and applications to the geometry of differentiable submanifolds. Professor Andrica has been chairman of the Department of Geometry at “Babes-Bolyai” since 1995. He has written and contributed to numerous mathematics textbooks, problem books, articles and scientific papers at various levels. He is an invited lecturer at university conferences around the world: Austria, Bulgaria, Czech Republic, Egypt, France, Germany, Greece, Italy, the Netherlands, Portugal, Serbia, Turkey, and the USA. Dorin is a member of the Romanian Committee for the Mathematics Olympiad and is a member on the editorial boards of several international journals. Also, he is well known for his conjecture about consecutive primes called “Andrica’s Conjecture.” He has been a regular faculty member at the Canada–USA Mathcamps between 2001–2005 and at the AwesomeMath Summer Program (AMSP) since 2006.

Zuming Feng received his Ph.D. from Johns Hopkins University with emphasis on Algebraic Number Theory and Elliptic Curves. He teaches at Phillips Exeter Academy. Zuming also served as a coach of the USA IMO team (1997-2006), was the deputy leader of the USA IMO Team (2000-2002), and an assistant director of the USA Mathematical Olympiad Summer Program (1999-2002). He has been a member of the USA Mathematical Olympiad Committee since 1999, and has been the leader of the USA IMO team and the academic director of the USA Mathematical Olympiad Summer Program since 2003. Zuming is also co-founder and academic director of the AwesomeMath Summer Program (AMSP) since 2006. He received the Edyth May Sliffe Award for Distinguished High School Mathematics Teaching from the MAA in 1996 and 2002.