User martin erickson - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T16:35:04Z http://mathoverflow.net/feeds/user/7086 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29608/square-achievement-game-on-a-grid Square Achievement Game on a Grid Martin Erickson 2010-06-26T12:54:45Z 2010-07-28T12:06:01Z <p>Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an n x n grid.<br> 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?</p> <p>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.</p> http://mathoverflow.net/questions/29601/an-operation-on-multisets An Operation on Multisets Martin Erickson 2010-06-26T12:39:53Z 2010-07-20T13:51:29Z <p>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.<br> 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).</p> <p>Does the process always result in a loop of 1, 2, or 3 arrays?</p> http://mathoverflow.net/questions/29607/a-transversal-achievement-game-on-a-grid A Transversal Achievement Game on a Grid Martin Erickson 2010-06-26T12:52:40Z 2010-06-30T16:35:29Z <p>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?</p> http://mathoverflow.net/questions/29807/binary-sequences-of-length-2n Binary Sequences of Length 2n Martin Erickson 2010-06-28T16:03:17Z 2010-06-29T12:25:33Z <p>I had posted an <a href="http://mathoverflow.net/questions/29606/what-is-being-counted-closed" rel="nofollow">urn probability problem</a> that didn't have good motivation. I'd like to try to explain the motivation here, and reintroduce the problem.</p> <p>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. </p> <p>The previous urn problem was an equivalent probabilistic formulation of the case \$n=5\$.</p> http://mathoverflow.net/questions/29605/group-action-with-a-fixed-point-property Group Action with a Fixed-Point Property Martin Erickson 2010-06-26T12:47:50Z 2010-06-28T21:55:28Z <p>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.<br> (This is impossible if G is finite.)</p> http://mathoverflow.net/questions/29606/what-is-being-counted What is Being Counted? Martin Erickson 2010-06-26T12:49:33Z 2010-06-28T15:22:00Z <p>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?</p> http://mathoverflow.net/questions/29603/what-does-the-expression-count What does the expression count? Martin Erickson 2010-06-26T12:43:53Z 2010-06-28T15:07:31Z <p>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.</p> http://mathoverflow.net/questions/29604/two-dimensional-gobbling-algorithm Two-Dimensional Gobbling Algorithm Martin Erickson 2010-06-26T12:46:46Z 2010-06-26T20:41:49Z <p>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?</p> <p>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.</p> http://mathoverflow.net/questions/29602/a-game-on-a-finite-projective-plane A Game on a Finite Projective Plane Martin Erickson 2010-06-26T12:42:25Z 2010-06-26T13:28:24Z <p>Two players Oh and Ex alternately choose points of a finite projective plane.<br> The first player (if any) to make a line in his/her chosen points is the winner.<br> 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?</p> http://mathoverflow.net/questions/29528/covering-a-square-with-unit-squares covering a square with unit squares Martin Erickson 2010-06-25T16:37:32Z 2010-06-26T11:54:28Z <p>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.)</p> http://mathoverflow.net/questions/29605/group-action-with-a-fixed-point-property Comment by Martin Erickson Martin Erickson 2010-06-28T16:38:40Z 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. http://mathoverflow.net/questions/29601/an-operation-on-multisets/29696#29696 Comment by Martin Erickson Martin Erickson 2010-06-28T16:32:48Z 2010-06-28T16:32:48Z Thanks, Matthew. Conway's &quot;Look-and-say sequence&quot; 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. http://mathoverflow.net/questions/29601/an-operation-on-multisets/29686#29686 Comment by Martin Erickson Martin Erickson 2010-06-28T16:30:25Z 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. http://mathoverflow.net/questions/29604/two-dimensional-gobbling-algorithm Comment by Martin Erickson Martin Erickson 2010-06-28T16:28:41Z 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&gt;1, and e(m,1)=1, e(1,n)=1. I wonder whether there is an explicit formula for e(m,n). http://mathoverflow.net/questions/29608/square-achievement-game-on-a-grid/29669#29669 Comment by Martin Erickson Martin Erickson 2010-06-28T15:39:07Z 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. http://mathoverflow.net/questions/29602/a-game-on-a-finite-projective-plane/29610#29610 Comment by Martin Erickson Martin Erickson 2010-06-28T15:31:54Z 2010-06-28T15:31:54Z Thank you very much for the reference, which completely answers the question.