Friday, January 14, 2011

Open Problems

There are many problems in math that no one has been able to answer. A surprising number of these problems are easy to state, and even easy to play around with.Thinking about these problems can give a student more of an idea of what math really is.

I'd like to collect problems here that would be accessible to high school and community college students. James Tanton works with students on open problems, and they've gotten results. I think that requires finding little known problems. The problems I'm listing below have been worked on long enough that any new results from us amateurs are unlikely. But we can still have fun playing.

The word conjecture means something that people believe is likely to be true, but which has not been proved.

1. Goldbach's Conjecture: Every even number greater than 2 can be expressed as the sum of two primes.

2. Twin Prime Conjecture: There are an infinite number of twin primes (n and n+2).

3. Collatz Conjecture: Play this game: Start with a positive whole number, n1. If n1 is even divide by 2, if n1 is odd multiply by 3 and add 1. You now have n2. Repeat the process indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1, which gives you a loop of 1, 4, 2, 1, ...

4. The Integer Brick Problem, to find a brick size in which the 3 lengths along the sides, the 3 diagonals along the faces, and the interior diagonal are all integers, or to prove that this cannot be done.

5. Is every prime larger than 3 the average of two primes? (from James Tanton)

6. A perfect number is a number that equals the sum of all its factors (including 1, but not including itself). Are there any odd perfect numbers? (from Wikipedia's list of open problems in mathematics)

7. The Lonely runner conjecture: if k + 1 runners with pairwise distinct speeds run round a track of unit length, will every runner be "lonely" (that is, be more than a distance 1 / (k + 1) from each other runner) at some time? (same source as #6)

8. Towers of Hanoi with 4 pegs: There is a stack of n disks on a peg, with the disks decreasing in size as you move up the stack. If you are allowed to move one disk at a time from one peg to another, and cannot put a bigger disk over a smaller one, what is the least number of moves it takes to move the stack. (seen twice recently, once here)

9. The Goormaghtigh conjecture: The only numbers that can be represented as 11...1 in more than one base are 31 and 8191.  31 can be represented in base 2 as 11111 and in base 5 as 111.  8191 can be represented in base 2 as 1111111111111 and in base 90 as 111. (We don't look 11 (two digits) in this problem, as any number n will be represented as 11 in the base n-1, making it easy to find numbers with two different representations that are all 1's. For example, 13 is 11 in base 12 and is 111 in base 3.)  (thanks to Mary O'Keeffe)

10.  Legendre's conjecture: There is a prime number between n2 and (n + 1)2 for every positive integer n. (mentioned in Bob and Ellen Kaplan's book, Hidden Harmonies)

Here's a good question: Which two problems on this list go together? If one were solved the other would be too. Are the two equivalent, or could one of them be solved and still leave the other open? (thanks to Christopher Sears)

What other open problems (simple to state and to play around with) can you add to this list?

[Edit date: 1/15]

9 comments:

  1. Trisecting an angle (but I did see an interesting "hatchet proof" last summer)

    ReplyDelete
  2. I'm not sure what you mean by 'hatchet proof'.

    This is not an open question. Trisecting the angle by standard Euclidean methods (straightedge and compass) has long been known to be impossible. (The Wikipedia article says it was proved in 1837.)

    Trisecting the angle given a different set of operating instructions is possible. For instance, the origami axioms will do it. (I did this as a participant in a math circle, and loved it.)

    ReplyDelete
  3. Problem #5 is a special case of Goldbach's. I think it may be equivalent. I have a weekend's worth of induction ahead of me.

    ReplyDelete
  4. The Goormaghtigh conjecture is neat and simple to state in a way that students can understand it.

    A repunit is a number composed entirely of ones.

    The decimal number 31 can be expressed as a repunit in base 2 as 11111 and as a repunit in base 5 as 111.

    Similarly, the decimal number 8,191 can be expressed as a repunit 1111111111111 in base 2 or as a repunit in base 90 as 111.

    Strangely, enough, mathematicians have so far been unable to find any other numbers besides 31 and 8,191 that can be expressed as nontrivial repunits in more than one base!

    The Goormaghtigh conjecture can be stated in multiple ways, but the simplest and most accessible statement is that 31 and 8,191 are the only such numbers.

    (By non-trivial, I mean that the repunit representation must be at least three or more digits long. All numbers n can be stated as a two-digit repunit in base n-1, so that doesn't count.)

    ReplyDelete
  5. @Christopher, Thanks! I hadn't noticed. #5 Just deals with primes (or primes times two if you multiply both sides of the equation by 2), and Goldbach's deals with all even numbers, so I can imagine #5 being true and Goldbach's being false. Which to me means they're not exactly equivalent. Perhaps I'm missing something, though.

    @Mary, Thanks! What a weird one... I see that both numbers are one less than a power of two (2^5-1 and 2^13-1). I wonder if anyone has proved that, if there are any others, they must also be 2^n-1.

    ReplyDelete
  6. Sorry, that was a silly comment. That would amount to proving that any answer has to have one of its bases be 2, not particularly deep most likely.

    I'm including something about the relationship Christopher pointed out and the problem Mary pointed out in the post now. I'll keep editing the list as I learn of more problems.

    ReplyDelete
  7. I thought there was a way to start with problem #5 and fiddle with prime factorizations to show that Goldbach's Conjecture is equivalent. I played around with it this weekend, and I'm pretty sure that my line of reasoning won't work out.

    If somebody was able to prove #5, that would lay a foundation for a proof of Goldbach's Conjecture.

    ReplyDelete
  8. What is the minimum number of colors needed to color the real plane such that no points 1 unit away from each other have the same color?

    :) I'm at that conference we went to last year together, and a link to your blog was up on the screen for a good 30 minutes!

    ReplyDelete
  9. Wow, did they say why they had the link up? Was it one among many? I wish I were posting more lately, but after teaching all week, I'm all talked out, I guess.

    So is that an open problem?

    ReplyDelete

 
Math Blog Directory