Open Problems

Arithmetic, Geometry, Algebra,
Calculus, Probability,
Combinatorics, Number Theory

  1. If the fraction 16/64 is reduced by "cancelling" the two 6's, we have a correct statement: 16/64=1/4. For any base d >=2, find all solutions to the equation ab/bc=a/c, where a, b, and c are distinct digits in base d, and d is a composite number. (You can show that there are no solutions if d is a prime.)
  2. For n >= 1, let f(n) be the number of 1's needed to write all the integers between 1 and n. For example, f(11)=4. A balanced number is a fixed point of f, that is, a value of n such that f(n)=n. There are 84 balanced numbers. What if we change the base to base d>=2? The largest balanced number is 1...10, where there are (d-1) 1s. Let a(d) be the number of balanced numbers in base d. Then the sequence {a(d)} is 2, 4, 8, 4, 21, 5, 45, 49, 84, ... . What is the pattern?
  3. Prove that n^2+1 unit squares in a plane cannot cover any square of side length greater than n. (The unit squares may be rotated. The interior of the large square, as well as its perimeter, must be covered.)
  4. In a 3-D Rook path, each step is a positive integer multiple of (0,0,1), (0,1,0), or (0,0,1). For example, one such Rook path is (0,0,0)-> (5,0,0)->(5,0,6)->(10,0,6)->(10,2,6). Let a(m,n,o) be the number of paths from (0,0,0) to (m,n,o). A simple recurrence is a(m,n,o)=sum_{(m',n',o')<(m,n,o)}a(m',n',o'). Let a_n=a(n,n,n), the number of paths from (0,0,0) to (n,n,n). A recurrence formula for the sequence {a_n} (called the diagonal sequence) is a_0 = 1, a_1 = 6, a_2 = 222, a_3 = 9918; 0=(2n^3 - 2n^2)a_n +(-121 n^3 + 212n^2 - 85n -6)a_{n-1} + (-475n^3 + 3462n^2 - 7853n + 5658)a_{n-2} + (1746n^3 -14580n^2 + 40662n - 37908)a_{n-3} + (-1152n^3 + 12672n^2 - 46080n + 55296)a_{n-4}, n >= 4. But this result is empirical; we don't have a proof of it. Can we prove this?
  5. Define a 2 x n array of positive integers where the first row consists of distinct positive integers arranged in increasing order, and the second row consists of any positive integers in any order. Create a new array where the first row consists of all the integers that occur in the first array, arranged in increasing order, and the second row consists of their multiplicities. Repeat the process. Prove that the process always results in a loop of 1, 2, or 3 arrays. For example, starting with the 2 x 1 array [1; 1], we eventually obtain a fixed point (loop of one array), the 2 x 4 array [1, 2, 3, 4; 2, 3, 2, 1].
  6. Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an n x n grid. The first player to write four of his/her symbols at the vertices of a square with horizontal and vertical sides is the winner. What is the smallest n such that the first player has a winning strategy?
  7. Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an n x n grid. The first player to occupy a set of n cells with no two cells in the same row or column is the winner. What is the outcome of the game given best possible player by both players?
  8. Two players Oh and Ex alternately choose points of a finite projective plane. The first player (if any) to make a line in his/her chosen points is the winner. Using the Erdos-Selfridge theorem, we can see that the game is a draw if the order of the projective plane is 7 or greater. The game is a trivial Oh win if the order is 2. Does Oh win if the order is 3, 4, or 5 (there is no plane of order 6)?
  9. What does the expression (q^n-1)(q^n-q)(q^n-q^2)(q^n-q^3)...(q^n-q^(n-1))/n! count? If q is a prime power, then this is the number of bases of an n-dimensional vector space over a field with q elements.
  10. There are two urns. One contains five white balls. The other contains four white balls and one black ball. An urn is selected at random and a ball in that urn is selected at random and removed. This procedure is repeated until one of the urns in empty. What is the probability that the black ball has not been selected? We can show that this probability is Binomial(10,5)/2^10. What is being counted?
  11. Let n be a positive integer and let z_1, ..., z_n be distinct points in the unit disk in the plane. For 1 <= i <= n, let d_i be the distance between z_i and the nearest other point z_j. Show that sum_{i=1}^n d_i^2 <= 9.
  12. Find an example of an infinite group G acting on a set X such that each non-identity element of G fixes exactly two elements of X, and some two elements of G have in common exactly one fixed point in X. (You can show that this is impossible if G is finite.)
  13. Suppose we have an 8x8 chess board. Two players alternately put queens on the chess board so that each new queen is not in range of any queen already on the board (the color of the queens is immaterial). The last player who can move wins. Who should win?