Open Problems

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

1. Let (m,n) be an ordered pair of positive integers. While m>0 and n>0, let k_1 be a random positive integer between 1 and m and k_2 a random positive integer between 1 and n. Output (k_1,k_2). Let m=m-k_1 and n=n-k_2. What is the expected number of outputs?
2. The Lucas numbers are defined by L(0)=2, L(1)=1, and L(n)=L(n-1)+L(n-2), for n >= 2. For which integers m >= 2 does the congruence L(n) = k mod m have a solution n for all residues k modulo m? Based on numerical evidence, we conjecture that this holds if and only if m is one of the following: 2, 4, 6, 7, 14, 3^t, t >= 1. For example, the Lucas sequence modulo 6 is 2, 1, 3, 4, 1, 5, 0, … and we see that we obtain all the residues modulo 6. As another example, the Lucas sequence modulo 5 is 2, 1, 3, 4, 2, 1, …, and since the sequence repeats we see that we never obtain the residue 0.
3. For n >= 0, let a(n) be the number of paths that a chess Rook can take from the origin (0,0) of a rectangular coordinate system to the point (n,n), where the Rook moves right or up at each step. For example, (0,0)-> (3,0)->(4,0)->(4,8)->(10,8)->(10,10) is a Rook path from (0,0) to (10,10). It can be shown using generating functions and analysis that the sequence {a(n)} is defined by the recurrence formula a(0)=1, a(1)=2, a(n)=((10n-6)a(n-1)-(9n-18)a(n-2))/n, for n >= 2. Can we give a counting proof of this formula?
4. 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 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?
5. 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 (if any) to occupy a set of n cells having no two cells in the same row or column is the winner. What is the outcome of the game given best possible play by both players?
6. Two players alternately put chess Queens on an nxn chess board so that each new Queen is not in range of any Queen already on the board (the colors of the Queens is unimportant). The last player who can move wins. Who should win?
7. For c>=m>=1, let P(c,m) be the statement that given any exact c-coloring of the edges of a complete countably infinite graph (that is, a coloring with c colors all of which must be used at least once), there exists an exactly m-colored countably infinite complete subgraph. Prove or disprove: P(c,m) is true if and only if m=1, m=2, or c=m.