Games on Graphs

The game Pong Hau K'i in Volume 2 Number 2 of MAT 007 I is a simple example of a much larger class of games played on finite graphs. Roughly speaking a graph is a set of points (called vertices) joined by lines (called edges). For what follows we will not need to give formal definitions, but for the interested reader two good introductions to graph theory are [1], [2]. We will only be concerned with finite simple graphs (finite number of vertices and edges; no edge joins a point to itself, any two points have at most one edge connecting them). Some examples of graphs:

Notice that all of these graphs are finite but #3 is not simple. Notice that graph #5 is in two "pieces". We will only be concerned with connected graphs those with only one "piece". Now for the fun and games. The simplest game is called cop and robber. Given a finite simple connected graph, the cop starts at one vertex, the robber at another. At his turn each must move along an edge to an adjacent vertex. They alternate turns. The cop tries to land on the robber (or have the robber land on him!), the robber tries to get away. The robber moves first. Now for the questions! What is the smallest graph (i.e.: smallest number of vertices) so that a single robber can always evade a single cop, no matter where they start? (Hint: 3 is too small, 4 depends on starting positions, 5 is just right.) That was easy! A tree is a special kind of graph (#4 is an example) If you don't know the definition, check [1] or [2] or ask a computer scientist. Can you prove that if the graph is a tree the cop always catches the robber? Also not hard. Now suppose that we have two cops instead of one. Both move simultaneously. Can you construct a graph so that one robber can always evade two cops? One more question, one that I don't know the answer to, so I'll offer a prize of $1 (one loony!) for the best solution by an undergraduate, time limit, 1 month. The question is, what is the smallest (ie.: fewest vertices) graph such that one robber can always evade two cops (independent of starting positions)?

References:

1. Bondy and Murty, Graph Theory with Applications, North Holland, 1976.
2. Harary, Graph Theory, Addison-Wesley, 1969.

Paradoxical Notes

This week's topic is the Banach-Tarski paradox. We expect many readers to be familiar with it so we shall only provide a brief explanation. For the uninitiated, please note it will be mind-expanding, but probably not fatal. [Ed: The 007 and its affiliates will assume no liability for damaged brains, degrees or careers if you read any further.]

The Banach-Tarski paradox states that if you take any object (say, the unit sphere) then it is possible to cut it into finitely many parts (five in fact), and put these pieces back together to get two copies identical to the original. There is no trickery here. The result is real and has been proven. It is left as an exercise for the interested reader to determine why no one has applied this theorem to their economic advantage. A simple corollary is that any nice set can be cut into finitely many pieces and reassembled into a desired number (either more or fewer) of identical copies.

The editorial board of the 007 has found two applications of this theorem. Unfortunately it is used to explain, and not to cause events.

We like to play tennis. At least, that's what we call it. We arrive at the appointed hour, and the chaotic dynamics begin. We have discovered that it helps to have lots of tennis balls. The only useful conjecture we have come up with during these sessions is:

Conjecture: If tennis is played with a sufficiently large number of tennis balls, and if you don't keep score, then it is impossible to have the same number of balls at the end.

It should be noted that even loud fluorescent orange balls can be Banach-Tarskied away. Generally, though, only the usual yellow-green ones Banach-Tarski into existence.

Proof: Meet us Thursday mornings on the court. It will be clear how to apply the paradox.

The second observation involves the formation of copy for the next issue. Invariably articles or other submissions that are supposed to appear, don't, and others (such as this one) appear in their place. The same can be said about the typographical errors, and even whole paragraphs that are just plain wrong. Mathematics has provided this insight into one of the "weird" forces of nature. The paradox is one of those driving forces which keeps the world interesting just when everything seems to be settling down into a nice understandable pattern.

As we noted above, the "paradox" has been proven; so it isn't really a paradox at all. The trouble hinges on the fact that the proof merely demonstrates that the partitions exist (isn't the axiom of choice frustrating?), but gives no recipe for cutting. We propose that the nature of the cuts is such that they are only valid if not observable (in a Quantum Mechanical sense). The interesting thing about the examples above is that the paradox exerts its influence just when the events in the world get confusing. It seems clear that if there were enough people following the tennis balls (or fewer balls), that they would not Banach-Tarski. After all, highway 401 is almost as confusing as one of our games, but cars don't Banach-Tarski because there is a driver keeping an eye on each one.

Is It Open?

Setting Things Straight

Sometimes textbook mathematics does little more than confound you with abstract notions and vague ideas. So I have compiled a list of some basic concepts sure to set anyone straight!

Groups. It is an inherent feature of groups that all its members have the ability to multiply things together. Conservative groups use the standard notion of mathematical multiplication whereby 2 * 3, say, is always 6. Then there are the Revolutionaries, who throw out all convention and embrace more radical platforms by defining multiplication to be anything they so desire. The integers, for example, could become a Revolutionary Group if they choose to define multiplication as addition instead. This could create a lot of group tension, and perhaps even a group war, as the Radicals pull away from their real roots. Incidentally, this explains why we never speak of a group of politicians, we say party. Politicians can neither add nor multiply as individuals, let alone as a group.

Sets. The notion of the mathematical set is slightly confusing to the uninitiated topologist. Set theory, however, can be made relatively simple if we consider the following analogy. A set is much like your bank account. A non-empty set, like an account, must contain something. Bank accounts can be either open or closed, as it is with sets. But here we must be careful, because sets, unlike your bank account, can be both open and closed at the same time. This is just a mathematical paradox we shouldn't have to worry too much about. We must also remember that a set that contains zero contains something, but a bank account that contains zero means that you are broke. The other thing is that sets do not charge interest; that is why topologists do not work in banks.

Subspaces. An important concept associated with vector spaces is that of rank. The rank of any space is determined by its dimension; that is, the number of linearly independent elements in the basis set. For subspaces, and more importantly, subspace messages, the rank of the transmitting party determines the priority of the message. So a Starfleet Officer of rank n, for example, will receive a subspace transmission of n dimensions, which means it is a very important message indeed. Those of infinite rank, however, are too great to be found on any starship. Hence these people are usually reserved for the Complex Plane...

A Useful Guide to Reading Math

• Recursive -- See recursive.
• Obvious -- This word means different things when used by different people. The difference is in the length of time between when someone states an "obvious" fact and when you come to realize the truth of that fact. For Prof. A., that length of time is nil. For Prof. B., it lasts until the moment right after he walks away. For Prof. C., it lasts until one week after she says it. For Prof. D., it is until right after your final exam. And for Prof. E., you'll never understand it!
• Q.E.D. -- Question every Detail/Deduction
• Proof -- A well ordered finite set of statements that is supposed to convince your wide-eyed audience (especially students) that you know something about the given proposition. The last statement is usually "Q.E.D." (and you should!)
• Poof -- is one of:
  1. A proof that sneaks up on you and hits you like an uncountable number of bricks; then gets erased off the blackboard before you absorb it.
  2. The main point of such a proof.
  3. A highly improbable construction (especially non-constructive) which gives rise to such a proof. (The rabbit gets pulled out of the hat.)
  4. Something which some students supply when asked to supply a proof, particularly on tests. Such students do not necessarily continue in mathematics.
  5. Proof by Intimidation. "You all see this, don't you!?!"
• Theorem --
  1. A comment statement in a BASIC program written by a guy named Theo.
  2. The statement of a mathematical claim, followed by a proof that supposedly pertains to the claim.
• Lemma -- A bashful theorem.

Three Guys and a Large Number

This article appears in the February 1995 issue of Math Horizons, the student magazine of the Mathematical Association of America.

In the late evening hours of April 26, 1994, it was announced that one of the most famous problems in cryptography, RSA-129, had been solved. A group of six hundred volunteers on the Internet led by Derek Atkins of MIT, Michael Graff of Ohio State University, Arjen Lenstra of MIT, and Paul Leyland of Oxford University carried out a job which required factoring a large number into two primes in order to crack a secret message and took eight months and over 5000 MIPS years, or approximately 150,000,000,000,000,000 calculations!

RSA-129 is actually a 129-digit number that is used to decrypt (or decode) the secret message by the RSA algorithm. RSA is a public-key cryptosystem and is named after the inventors of the algorithm: Ron Rivest, Adi Shamir, and Leonard Adleman.

What is a public-key cryptosystem? In the past, messages were encoded by a scheme called a secret-key cryptosystem. The sender and receiver of a message would have the same key (or password) in order to encrypt and decrypt messages. A problem of this system is that the sender and receiver must agree on this secret key without letting others find out. So in 1976, a new system called public-key cryptography was invented that took care of this problem. In this system, each person receives a pair of keys, called the public key and the private key. Each person's public key is published but the private key must be kept secret. This way, a user can encode a message using the intended recipient's public key, but the encoded message can only be decrypted by the recipient's private key.

The RSA algorithm is a simple, yet powerful, cryptosystem. It's simple in the sense that the algorithm can be easily understood by any mathematician. In fact, here's how it works:

First we translate the message into numeric form. For instance, suppose we want to send this message to your math professor: PLEASE DONT FLUNK ME. We can use a simple encoding scheme such as letting 01=A, 02=B, ..., 26=Z, and 00 be a space between words. So the numeric message becomes

1612050119050004151420000612211411001305 = t.

Actually, any text to numeral converter will do, since this is really not part of the RSA algorithm. But this means we have a secret-key cryptosystem in addition to our public-key encryption!

So how are RSA public and private keys generated?

• We take two large primes, p and q, and find their product n=pq . n is called the modulus and an example of n is RSA-129.
• We randomly choose a number, e, less than n, such that (p-1)(q-1) and e are relatively prime, i.e. gcd((p-1)(q-1),e)=1.
• We calculate the multiplicative inverse, d, where ed = 1(mod(p-1)(q-1)). For those of you not familiar with modular arithmetic, the notation a=b(mod m) means that if m is a natural number, then a and b are integers that leave the same remainder when divided by m. And finally...
• We destroy p, q, and (p-1)(q-1). The public key is the pair (n, e). The private key is d.

• For Eric to encrypt the message, he creates the ciphertext c by calculating the remainder of the division t^e by n, where e is Darcy's public key. Eric sends c to Darcy.
• For Darcy to decrypt the message, she calculates t where t is the remainder of the division c^d by n. She can then translate t into plain text by using the 01=A trick and read the message! I'll bet Eric will be real surprised when he sees his report card!

In fact, shortly after RSA was developed in 1977, Rivest, Shamir, and Adleman proposed a challenge to the scientific world to crack an encoded message given the public keys n = RSA-129 and e. In fact, they asserted that even with the best factoring methods and the fastest computers available at the time, it would take over 40 quadrillion years to solve. But with the exponentially increasing power of computers and advances in mathematical techniques in factoring large numbers -- a factoring scheme called the quadratic sieve was invented in 1981 by Dr. Carl Pomerance of the University of Georgia, the method used in factoring RSA-129 -- it would be somewhat surprising that it would only be 17 years later when the message would be cracked.

Well, enough of the theory, and let's get to the gooey stuff: the calculations by the 600 miracle workers.

The encoded message published was c = 9686961375462206147714092225435588290575999112457431987469512093081629822514570
8356931476622883989628013391990551829945157815154

with the public key pair e = 9007 and n = RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429357069352457338
97830597123563958705058989075147599290026879543541

= 3490529510847650949147849619903898133417764638493387843990820577 * 32769132993266709549961988190834461413177642967992942539798288533.

With these two primes, the private key is calculated to be d = 1066986143685780244428687713289201547807099066339378628012262244966310631259117
74470873340168597462306553968544513277109053606095.

Upon applying the decryption step, the decoded message becomes t = 200805001301070903002315180419000118050019172105011309190800151919090618010705.

Using the 01=A, 02=B trick, the decoded message reads

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE.

The definitions of the last two words are left to the reader as an exercise.

For more information about RSA and cryptography, check out the World Wide Web Virtual Library.

Dear Gwendolyn

Dear Marty, your problems are manifold. First, you have an engineer for a friend. Please correct the situation. Second, your mop will never shrink to a point in finite time (even nicely). Third, even if it does become a point, then just follow a space-filling curve when you mop, and charge them for overtime.

Dear Gwendolyn, I really don't what to make of this, but ever since I started taking this algebra course I have been having difficulties doing my math homework. It seems that everytime I sit down to do my work I feel like my head is going to explode. What is going on? Am I crazy? Sincerely yours, Vector Spaced

Dear Spaced, don't be alarmed. Apparently you have caught a mild case of Dysfunctionism, caused by cerebral-infecting organisms of genus linearum algebratus. It is a condition known only to affect undergraduates, and it generally targets math students (all of whom, incidentally, have had to take courses in linear algebra). Those who have it often complain of sudden dizziness and confusion when approaching a mathematics text of any kind, accompanied by an overwhelming sense of doom. The best solution is psychological. By deluding the brain into thinking of anything but math until the last possible moment seems to be a good strategy. For instance, try covering your textbooks. That way, you will approach your desk unaware of the algebra lying in wait and, if you choose nice pictures, you will at least have something interesting to look at.

Prof. Man-Duen Choi's Problem

New mark = min(100, old mark/0.9),

with all marks non-negative integers less than or equal to 100. What are the least upper and greatest lower bounds on the new average?

How to Date a Mathie -- A Self Help Guide

Due to an uncanny set of circumstances, I have dated three mathies, well maybe more, say, Pi mathies (What can I say -- I just love those pink ties). I can attribute my experience only to a depraved joke of God's or to strange mutations in my DNA. At any rate, I have learned much from my experience and I hope that others may benefit from my confusion. Mathies, read this! Hand it out to your boyfriends and girlfriends, and to your prospective dates. Better yet, simply pin it to a visible portion of your clothing as a warning label.

DO

DO NOT

Good luck!

About the cover:

For some strange reason, I could not locate the author of the image. Please identify yourself so credit can be given.

MAT 007 I News is published from a corner of Sidney Smith Hall at the Department of Mathematics, University of Toronto. Issues are printed by the University of Toronto Press.

Copyright © 1988-1990, 1992-1994, 1995 MAT 007 I News. All Rights Reserved.

Go back to the top of this page.

Return to the Department of Mathematics Home Page