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? 

Some unsolved problems January 3, 2010

Posted by Damien Jiang in Problem-solving.
Tags: , , , , ,

Happy New Year!

Since we have been too lazy to post lately (and the so-not-lazy Akhil posts mostly elsewhere now), I’m going to post some problems that I probably should be able to solve, but haven’t.


USAMO 1973 #4 August 19, 2009

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

A fairly straightforward algebra problem. Could appear on a modern AMC-12, though the decoy answers would have to be carefully written.

USAMO 1973 #4. Determine all the roots, real or complex, of the system of simultaneous equations

\displaystyle x+y+z=3

\displaystyle x^2+y^2+z^2=3

\displaystyle x^3+y^3+z^3=3


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…)

USAMO 1973 #2 August 11, 2009

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

USAMO 1973 #2. Let {\{X_n\}} and {\{Y_n\}} denote two sequences of integers defined as follows:

\displaystyle X_0=1,\hspace{0.1cm}X_1=1,\hspace{0.1cm}X_{n+1}=X_n+2X_{n-1}\hspace{0.1cm}(n=1,2,3,...)

\displaystyle Y_0=1,\hspace{0.1cm}Y_1=7,\hspace{0.1cm}Y_{n+1}=2Y_n+3Y_{n-1}\hspace{0.1cm}(n=1,2,3,...)

Thus, the first few terms of the sequence are:

\displaystyle X:\hspace{0.1cm}1,1,3,5,11,21,...

\displaystyle Y:\hspace{0.1cm}1,7,17,55,161,487,...

Prove that, except for “1”, there is no term which occurs in both sequences. (more…)

USAMO 1973 #1 August 7, 2009

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

USAMO 1973 #1. Two points, {P} and {Q}, lie in the interior of a regular tetrahedron {ABCD}. Prove that angle {PAQ<60^{\circ}}. (more…)

USAMO 1972 #5 August 4, 2009

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

USAMO 1972 #5. A given convex pentagon {ABCDE} has the property that the area of each of the five triangles {ABC}, {BCD}, {CDE}, {DEA}, {EAB} is unity. Show that every non-congruent pentagon with the above property has the same area, and that, furthermore, there are an infinite number of such non-congruent pentagons. (more…)

USAMO 1972 #4 July 26, 2009

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

USAMO 1972 #4. Let {R} denote a non-negative rational number. Determine a fixed set of integers {a}, {b}, {c}, {d}, {e}, {f} such that, for every choice of {R},

\displaystyle |\frac{aR^2+bR+c}{dR^2+eR+f}-\sqrt[3]{2}|<|R-\sqrt[3]{2}|. (more…)

Another Integral July 25, 2009

Posted by Dennis in Problem-solving.
Tags: ,

This is a problem from the Putnam competition I saw two years ago as a freshman, and I did it during my stats class this year. It uses symmetry in a similar way to Akhil’s post.
Find {\displaystyle\int_{0}^{1}{\frac{\ln(x+1)}{x^2+1}dx}}.
Let {\tan(u)=x}, then

\displaystyle  \begin{array}{rcl}  \frac{du}{dx}=\frac{1}{1+x^2}. \end{array}


\displaystyle \begin{array}{rcl} \int_{0}^{1}{\frac{\ln(x+1)}{x^2+1}dx}=\int_{0}^{\frac{\pi}{4}}{\ln(\tan(u)+1)du}. \end{array}

Also, we have the identity

\displaystyle \begin{array}{rcl} \sin(u)+\cos(u)&=&\sqrt{2}(\sin(\frac{\pi}{4})\cos(u)+\cos(\frac{\pi}{4})\sin(u))\\&=&\sqrt{2}(\sin(u+\frac{\pi}{4})) \end{array}


\displaystyle \begin{array}{rcl} \int_{0}^{\frac{\pi}{4}}{\ln(\tan(u)+1)du}&=&\int_{0}^{\frac{\pi}{4}}{\ln(\frac{\sin(u)+\cos(u)}{\cos(u)})du}\\ &=&\int_{0}^{\frac{\pi}{4}}{\ln(\sin(u)+\cos(u))-\ln(\cos(u))du}\\ &=&\int_{0}^{\frac{\pi}{4}}{\ln(\sqrt{2}(\sin(u+\frac{\pi}{4})))-\ln(\cos(u))du}\\ &=&\int_{0}^{\frac{\pi}{4}}{\frac{\ln(2)}{2}+\ln(\cos(\frac{\pi}{4}-u))-\ln(\cos(u))du}\\ &=&\frac{\pi}{4}\frac{\ln(2)}{2}\\ &=&\frac{\pi\ln(2)}{8} \end{array}

A quick integral July 24, 2009

Posted by Akhil Mathew in Problem-solving.
Tags: , ,

The integral {I=\int_0^\pi \log \sin x dx} is normally computed (e.g. in Ahlfors’ book) to be {-\pi \log 2} using complex integration over a suitable almost-rectangular contour. There is also a simple and direct way to get the value of this integral by a substitution and elementary calculus.

First, by the substitution {x=2t} and the identity {\sin(2x)=2\sin x \cos x},

\displaystyle  I = 2 \int_0^{\pi/2} \log \sin t dt + 2 \int_0^{\pi/2} \log \cos t dt + \pi \log 2;

then using the symmetry of {\sin} and {\cos} gives:

\displaystyle  I = I + I + \pi \log 2,

whence the result. There are slight technicalities regarding the improperness of these integrals, but they can be directly justified (or one may use the Lebesgue integral).

[Edit (7/25)- Todd Trimble posted solutions to similar integrals, which use the result of this post as a lemma, here.  AM]