Last week I discussed getting students involved in the frontiers of mathematical development by involving them in research where they had a chance of solving problems never before solved. However, the lure of the unsolved can be an effective hook even if the students don't work on a problem directly.

For instance, there's nothing like a million dollars to grab a student's attention.

The Millennium Problems are a set of 7 open questions in mathematics set by the Clay Foundation.* Each problem has a bounty of $1,000,000 to the solver (or solvers). The 7 problems were carefully chosen, and any problem solved would represent a giant leap in the corresponding discipline.

P vs. NP

Perhaps the most accessible of the problems is from computer science.

Consider a salesman who has a map of 80 cities he needs to visit. Each pair of cities has a distance between them. What is the shortest route the salesman can take to visit all the cities, and return where he started? Is there an algorithm to work this out quickly?

To be more specific, there are algorithms that can be run in polynomial time (P) and algorithms that can be run in non-deterministic polynomial time (NP). NP problems are much harder to solve, and a sufficient large problem (say, the problem above involving 1000 cities) might take the length of the universe to calculate. Is there some clever way to transform NP problems into P problems, so P = NP?

Most computer scientists believe P does not equal NP.** However, it is still possible for students to work on various NP problems on a smaller scale to learn about graph theory and logic. For example, the travelling salesman problem given above can be done at a small scale of only 6 cities.

There's another NP problem involving finding a group of people (out of a larger set) where everyone is friends. I have made a worksheet exploring this variation (see below).

Other Unsolved Problems

Of course, there's a whole universe of difficult open questions in mathematics outside of the 7 Millenium Problems. A few that might interest students are:

• Goldbach's conjecture: Every even number greater than 2 can be written as the sum of two primes. This problem has been around for more than 250 years.
• Sudoku givens problem: Is it possible to have a Sudoku puzzle with less than 17 "givens" (numbers in the grid at the start the puzzle) such that the solution is unique?
• Chromatic number of the plane: Color the plane so that any pair of points a distance of 1 unit apart are different colors. How many colors do you need?

* One problem (the Poincaré Conjecture) has been solved, although the prize has not yet been awarded.

** Belief does not equal truth; for a long time it was thought a polynomial time algorithm to test if a number is prime did not exist, yet one was produced in 2002.

WORKSHEET

You’re arranging housing for students in a dorm. Each room in the dorm holds two students.

You are trying to place 8 students in 4 rooms. The names of the students are
Aaron, Bell, Cory, Diego, Emilio, Frank, Gilberto, and Hector. The students have stated their preferences of who they are willing to room with.
A-B, A-C, A-F, B-H, C-D, C-F, D-E, E-F, E-G, F-H, G-H

1. Can you place all the students so they’re happy? If so, place them. If not, why not?

Room #1                         Room #2                      Room #3                  Room #4

Suppose a longer group of preferences.
A-B, A-C, A-D, A-E, A-F, A-G, A-H, B-C, B-D, B-E, B-F, B-G, B-H

2. Can you place all the students so they’re happy? If so, place them, if not, why not?
Room #1                         Room #2                      Room #3                  Room #4

3. Given an arbitrary list of students and preferences, how would you prove they can be placed so they’re all happy? How would you prove there’s no way to make them all happy?

Now a slight change to the problem. Suppose you have 4 places in a dorm but you’re not worrying about who goes in which room. However, you have to pick your 4 students out of a total set of 8 students, and all 4 students you pick have to be compatible (so any pair out of the four could be potential roommates).

4. How many ways are there to pick just 1 student out of 8?

5. How many ways are there to pick just 2 students out of 8?

6. How many ways are there to pick just 3 students out of 8?

7. How many ways are there to pick the full 4 students out of 8?

Suppose this list of student preferences:
A-C, A-E, A-D, A-F, A-G, B-E, C-E, D-E, D-F, D-H, E-F, F-G, F-H
8. Can you pick four students so they’re all compatible? If so, pick them. If not, why not?

Suppose this list of student preferences:
A-B, A-C, A-F, B-H, C-D, C-F, D-E, E-F, E-G, F-H, G-H
9. Can you pick four students so they’re all compatible? If so, pick them. If not, why not?

Million Dollar Question: (P vs. NP problem)
Come up with a method (that works no matter what the data is) to pick 100 students so they’re all compatible out of a possible set of 500.

Jason Dyer holds degrees in Fine Arts Studies and Math and teaches at Pueblo High School in Arizona. His school mascot is the Warriors and his other blog of residence is The Number Warrior.

Comments (0)

Subscribe to this comment's feed

Name

Email

Website

Title

Comment

smaller | bigger

Subscribe via email (Registered users only)

I have read and agree to the Terms of Usage.

Add Comment