Nim-Chomp August 19, 2010Posted by lumixedia in combinatorics, math, Problem-solving.
Tags: combinatorial game theory, combinatorics, rsi
Wow, I’m really not cut out for helping to maintain a blog, am I? So what finally prompted me to post was Dr. Khovanova’s description of the game of Nim-Chomp at her blog, which she suggested I respond to.
So Dr. Khovanova described Nim-Chomp to me at RSI more than a year ago, and I thought I solved it. Then a few months ago I found a flaw, thought it was hopeless, and gave up. Then a few minutes ago I realized that the flaw was in fact fixable. The point of this paragraph is that I’m not sure I’m to be trusted regarding this problem, but I’ll try.
I won’t repeat the problem statement here. Too lazy. Just read her post. Because I find it easier to think about this way, I’ll make a slight modification to the Chomp perspective on Nim-Chomp: on a given turn, each player may only eat squares from a single *column* (rather than a single *row*).
First let’s pretend the bottom left square is not actually poisoned. We can transform this easy-Nim-Chomp into regular Nim as follows: for a given position in easy-Nim-Chomp, suppose the number of squares remaining in each column is a1, a2, …, an from left to right. Let b1 = a1 – a2, b2 = a3 – a4, …, b[n/2] = (an-1 – an) or (an) depending on whether n is even or odd. Then this position is equivalent to regular Nim with piles of b1, b2, …, b[n/2]. Basically, we’re splitting the chocolate columns into pairs of adjacent columns and considering the differences between the members of each pair to be the piles of our regular game of Nim. Because the piles are in nonincreasing order, this is a well-defined transformation.
It works as follows: suppose the loser of the Nim-game (b1, b2, …, b[n/2]) eats some squares from the kth column where k is odd. This decreases the value of ak, thereby decreasing one of the Nim-piles as in a regular Nim-game, so the winner just makes the appropriate response. Instead, the loser might try to dodge by eating squares from the kth column where k is even, thus decreasing the value of ak but increasing one of the Nim-piles rather than decreasing it, which can’t be done in regular Nim. But the winner can simply decrease ak-1 by the same amount and leave the loser in the same position as before. There are a finite number of squares, so the loser can’t keep doing this. Eventually they must go back to decreasing piles, and lose.
This is how far I got at RSI. I didn’t realize the poisoned lower-left square was a significant issue, but it is. Thankfully, all it really does (I think) is turn the game into misère Nim rather than normal Nim. We make the transformation to Nim-piles in the same way as before, and the winner uses nearly the same strategy as in the previous paragraph, but they modify it to ensure that the loser is eventually faced with “bk”s which are all 0 or 1 with an odd number of 1s. (Maybe one day if I get around to writing a basic game theory post I’ll explain why this is possible. Or you can check Wikipedia. Or just think about it.) When the loser increases some bk, the winner eats squares in the corresponding column to decrease it back to 0 or 1; when the loser decreases a 1 to a 0, the winner decreases another 1 to a 0.
Eventually, the loser is forced to hand the winner a chocolate bar consisting of pairs of adjacent equal columns. At this point the winner takes a single square from any column for which this is possible, leaving a bunch of 0s with a single 1—i.e. another misère 2nd-player win. This continues until we run out of squares, at which point we conclude that the loser of the new game of misère Nim is indeed the player who consumes the poisoned square in the original game of Nim-Chomp.
Question I’m too lazy to think about right now: can we still do this or something like this if we poison not only the bottom left square of the chocolate bar, but some arbitrary section at the bottom left?
Siemens October 7, 2009Posted by Damien Jiang in Uncategorized.
Tags: papers, rsi, Siemens
Unfortunately the depth and breadth of my mathematical knowledge are not as awesome as Akhil’s. So, I’ll talk about something else related to math.
I, like probably every other contributor to this blog, submitted my research paper to the Siemens competition about a week ago. Despite the incredible amount of editing I did at RSI, I realized, to my dismay, that the bulk of the editing was still to be done.
The RSI (Mathematical) Experience August 5, 2009Posted by Akhil Mathew in General, Mathematical research.
Tags: research science institute, rsi, rsi 2009, summer programs
add a comment
The 2009 Research Science Institute ended last Friday. Since we the bloggers want to reach other high school students, I will briefly explain what the RSI experience is like. I’ll only be able really to describe the mathematics program, since it is very different from the science and engineering ones.
About Us July 10, 2009Posted by Delta Epsilons in General.
Tags: about us, introduction, math, research science institute, rsi, welcome
The Delta Epsilons
We, the Delta Epsilons, are a group of mathematically inclined high school students who met at the 2009 Research Science Institute at MIT. We started this blog to discuss mathematics and related sciences. Our interests are broad—they range from analysis to category theory to combinatorics to theoretical physics—and this blog will reflect that diversity.
First, we intend to discuss mathematical competitions. Many of us have participated in problem-solving contests such as the USAMO, which may inspire posts. Since one part of our intended audience consists of other motivated high school students, we will encourage participation in such competitions by posting information about them.
As we met at RSI, we are also interested in research. We will post about our research, both our RSI projects and others, here; we may also discuss papers we read independently. Many of our posts will also be expository, discussing known mathematical results.
Other than that, the blog will occasionally contain arbitrary posts (and, very rarely, random posts), ranging from mathematical education to philosophy and history.
In real and complex analysis, deltas and epsilons are frequently used mathematical notations to define basic constructions such as limits, continuity, and integrals. The Kronecker delta, the capital delta denoting change, and the Dirac delta point measure are further examples of the importance of the letter delta in mathematics. An epsilon was also Paul Erdős’s name for a young child. We are, of course, relatively young as mathematicians go, though we hope to prove that we are capable of providing interesting discourse to mathematicians with more experience as well.