User martin erickson - MathOverflow

Square Achievement Game on a Grid

2010-06-26T12:54:45Z

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?

Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15.

An Operation on Multisets

2010-06-26T12:39:53Z

Define a 2 x n array of positive integers where the first row consists of some 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. For example, starting with the 2 x 1 array [1; 1], the sequence is: [1; 1] -> [1; 2] -> [1, 2; 1, 1] -> [1, 2; 3, 1] -> [1, 2, 3; 2, 1, 1] -> [1, 2, 3; 3, 2, 1] -> [1, 2, 3; 2, 2, 2] -> [1, 2, 3; 1, 4, 1] -> [1, 2, 3, 4; 3, 1, 1, 1] -> [1, 2, 3, 4; 4, 1, 2, 1] -> [1, 2, 3, 4; 3, 2, 1, 2] -> [1, 2, 3, 4; 2, 3, 2, 1], and we now have a fixed point (loop of one array).

Does the process always result in a loop of 1, 2, or 3 arrays?

A Transversal Achievement Game on a Grid

2010-06-26T12:52:40Z

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 some transversal (i.e., 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?

Binary Sequences of Length 2n

2010-06-28T16:03:17Z

I had posted an urn probability problem that didn't have good motivation. I'd like to try to explain the motivation here, and reintroduce the problem.

Consider binary sequences of length $2n$. Let's say we put a marker in such a sequence as soon as we see a total of $n$ 0's or $n$ 1's, reading left to right. For example, if $n=4$, then the sequence 00101011 would receive a marker thus: 001010|11. Now write down the bits to the right of the marker. In the case of our example, this would be 11. Do this for every binary sequence of length $2n$. We observe that we have written down $2n\binom{2n}{n}$ bits, half 0's and half 1's. It is possible to prove this observation using binomial coefficient identities, but I wonder whether there is a simple bijective proof.

The previous urn problem was an equivalent probabilistic formulation of the case $n=5$.

Group Action with a Fixed-Point Property

2010-06-26T12:47:50Z

Is there 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.
(This is impossible if G is finite.)

What is Being Counted?

2010-06-26T12:49:33Z

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. The probability that the black ball has not been selected is Binomial(10,5)/2^10. The form of the answer suggests a counting solution. What is being counted?

What does the expression count?

2010-06-26T12:43:53Z

Let $q \geq 2$. What does the expression $(q^n-1)(q^n-q)(q^n-q^2)(q^n-q^3)\ldots(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.

Two-Dimensional Gobbling Algorithm

2010-06-26T12:46:46Z

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?

Note that in the one-dimensional version of the problem, starting with a single integer n, the expected number of outputs is the nth harmonic number 1+1/2+1/3+...+1/n.

A Game on a Finite Projective Plane

2010-06-26T12:42:25Z

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 5 or greater. The game is a trivial Oh win if the order is 2. Does Oh win if the order is 3 or 4?

covering a square with unit squares

2010-06-25T16:37:32Z

Can some square of side length greater than $n$ be covered by $n^2+1$ unit squares? (The unit squares may be rotated. The large square and its interior must be covered.)

Comment by Martin Erickson

2010-06-28T16:38:40Z

Ketil, we can show the result is impossible if G is finite by using Burnside's counting formula. This only applies when G is finite.

Comment by Martin Erickson

2010-06-28T16:32:48Z

Thanks, Matthew. Conway's "Look-and-say sequence" was my original motivation for this sequence operation. Yes, I have found examples with periods 1, 2, and 3. But I don't have a clear proof that the sequence always terminates in a loop.

Comment by Martin Erickson

2010-06-28T16:30:25Z

Thanks, Nick. Yes, the ordering is unimportant. I just like to write the arrays that way to keep track of what I'm doing.

Comment by Martin Erickson

2010-06-28T16:28:41Z

Thank you for your kind responses. I had noticed that the one-dimensional case is answered very simply (the formula is given by the nth harmonic number), and wondered whether one could solve the two-dimensional version of the problem. We can derive a recurrence relation. Let e(m,n) be the expected number of outputs. Then e(m,n)=1+(1/(mn))Sum[e(m,n),{j,1,m-1},{k,1,n-1}], for m,n>1, and e(m,1)=1, e(1,n)=1. I wonder whether there is an explicit formula for e(m,n).

Comment by Martin Erickson

2010-06-28T15:39:07Z

I believe that in your version of the problem, where the players are trying to form a 2x2 subrgrid in their own symbol, then the game is a draw. The second player can consider the board as tiled in a brick pattern by dominos, and complete each domino that the first player enters. This blocks the 2x2 subgrid pattern.

Comment by Martin Erickson

2010-06-28T15:31:54Z

Thank you very much for the reference, which completely answers the question.