jump to navigation

Nim-Chomp August 19, 2010

Posted by lumixedia in combinatorics, math, Problem-solving.
Tags: , ,

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? 

USAMO 1973 #3 August 17, 2009

Posted by lumixedia in combinatorics, Problem-solving.
Tags: , , , ,
1 comment so far

USAMO 1973 #3. Three distinct vertices are chosen at random from the vertices of a given regular polygon of {(2n+1)} sides. If all such choices are equally likely, what is the probability that the center of the given polygon lies in the interior of the triangle determined by the three chosen random points? (more…)

A random math illiteracy moment August 9, 2009

Posted by lumixedia in combinatorics, General.
Tags: , ,

I can’t figure out how, but this memory from policy debate camp a couple years back just floated into my head and this seems like the appropriate place to recount it.

This was back when the topic for the upcoming year was Resolved: The United States federal government should substantially increase its public health assistance to Sub-Saharan Africa. For readers not familiar with policy debate, policy teams generally come up with a single plan which falls under the scope of the resolution and research it in great depth throughout the year. A plan for this resolution might look something like “The United States federal government should substantially increase funding for treatment of AIDS in Zimbabwe”. In each round, the affirmative team presents their plan and the negative team attacks it.

Besides directly arguing that the plan is a bad idea, the negative team can also argue that the plan doesn’t actually fit the resolution by some interpretation of the resolution. This is known as a topicality argument and might go something like “Your plan to treat AIDS in Zimbabwe is non-topical because the resolution implies that the increased public health assistance should go to all of Africa, not just a small subset such as a single country”. This particular example is the subsets topicality argument. (more…)

USAMO 1972 #2, #3 July 21, 2009

Posted by lumixedia in Problem-solving.
Tags: , , , , ,

I think I might as well just start going through the USAMOs in chronological/numerical order.

USAMO 1972 #2. A given tetrahedron {ABCD} is isosceles, that is {AB=CD}, {AC=BD}, {AD=BC}. Show that the faces of the tetrahedron are acute-angled triangles. (more…)

Lattice Representations of Order Ideals of Posets July 17, 2009

Posted by Martin Camacho in combinatorics.
Tags: , ,

In this post I’ll talk about the representation of order ideals of posets as distributive lattices. You can get a very good description of posets from Stanley’s Enumerative Combinatorics, Vol 1.

First, a couple definitions:

Definition 1 An order ideal of a poset {P} is a set of elements {I} such that if {x\in I} and {y\le x} then {y\in I}