Nim-ChompAugust 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?

A PuzzleJune 25, 2010

Posted by genericme in Uncategorized.

Consider a set of $n$ objects from which $m$ are drawn randomly at a time, with replacement.  What is $E(n, m)$, the expected number of draws I have to make to have drawn all of the objects?

I have yet to find a satisfactory closed-form expression for even $E(n, 1)$.  I obtain an ugly series in terms of Stirling numbers of the second kind.   However, I suspect that $E(n, 1)$ is asymptotically linear:

Is this a well-known problem?

Posted by Akhil Mathew in Uncategorized.

It’s been another two months already since anyone last posted here, hasn’t it?

So, first of all, Damien Jiang, Anirudha Balasubramanian, and I have each uploaded the papers resulting from our RSI projects to arXiv.  I’ve been discussing the story of my project on representation theory and the mathematics around it on my personal blog (see in particular here and here).  There are others from the program who have placed their papers on arXiv as well (but are not involved in this blog).

I’d like to congratulate my friend and fellow Rickoid Yale Fan for winning the Young Scientist award at the International Science and Engineering Fair for his project on quantum computation (which deservedly earned him the title “rock star”).  I also congratulate his classmate and fellow rock star Kevin Ellis (who did not do RSI, but whom I know from STS) for winning the (again fully deserved) award for his work on parallel computation.  There is a press release here.

RSI 2010 is starting in just a few more days.  I’m not going to have any involvement in the program myself (other than potentially proofreading drafts of kids’ papers from several hundred miles away), nor do I know much about what kinds of projects (mathematical or otherwise) will be happening there.  I think I’d be interested in being a mentor someday—maybe in six years time.  I’m going to be doing a project probably on something geometric this summer, but it remains to be seen on what.

I don’t really know what’s going to become of this blog as we all now finish high school and enter college.  It looks like most of us will be in Cambridge, MA next year; this is hardly surprising given the RSI program’s location there.  Also, just to annoy Yale, I’m going to further spread the word that he is going to Harvard.

If anyone from RSI 2010 wants to join/revive this blog, feel free to send an email to deltaepsilons [at] gmail [dot] com.

Intel day 4March 14, 2010

Posted by Akhil Mathew in General.
Tags:

I had the last day of judging today at Intel. The 40 finalists first went to the Capitol to take a bunch of pictures, then to the Einstein statue at the NAS for another one.  We then went in the project exhibition hall.  I met with seven judges, two of who were mathematicians.  In order that future generations of Intelists may face the day of judgment without crushing uncertainty in the morning, I shall briefly describe my experience.

The first two judges I had were mathematics judges.  The first one asked me what I would do if I were giving a talk about my project at a colloquium.  He asked me to explain one of my results, which I initially did incorrectly (having not looked through the older proof in quite some time) but fixed along the way.  He asked me how I had learned algebraic geometry (or, more precisely, that rather small subset I can claim to vaguely understand).   Interestingly, he referred to a specific result in my paper by number (3.10; I didn’t remember what that was for sure)—one of the differences between Intel and ISEF is that the judges read the papers.

The second mathematician asked me to give an overview of my project in detail, so I went into my usual spiel.  She asked me a few questions along the way about how the results were proved.  Finally, she asked where I was going to go to college.  I said that I didn’t know yet.   This was a somewhat longer interview.

There were others who wanted a brief overview and then left.  A computer scientist who had asked me earlier about certain algorithms and an engineer that asked about the law of atmospheres chatted with me about extensions of those problems.

The exhibits were then opened to the public.  I met a few RSI 2009 alumni from the D.C. area.  Most people were not mathematicians, which made explaining my project (on representation theory in complex rank) a somewhat difficult task, though there were some that knew, e.g. group theory.  I wasn’t envious of my neighbor Joshua Pfeffer with mobs of people craning to hear about the super Kahler-Ricci flow though owing to me extreme hoarseness despite my consuming two bottles of fluids.  Also, my parents stopped by to say hello and see the other projects.

I’m somewhat tired now, and there’s not that much more I really can say about it without going into technical details.

Intel day 3March 13, 2010

Posted by Akhil Mathew in General.
Tags:

(Today was the third day of the Intel STS competition.)

I had my third judging interview today at about 11:40 am.   The judging panel included a computer scientist who pointed to the seven wrapped chocolates on the desk and informed me that to each was assigned a number, and that I needed to discover which contained the median. I didn’t have the actual numbers, but I could compare any two.  In the end, I said something about $O(n \log n)$ sorting algorithms (e.g. heapsort).  He then asked me about counting paths from (0,0) to (m,n) where one can move either right or up on each move; I stated a recursive formula, but got the wrong closed form expression (it’s a binomial coefficient, and I said it was a power of 2).  I was then asked by the other judge about what change I would make if I had to design the human body.  I suggested eliminating cognitive biases and improving rationality but that wasn’t legal; I then suggested various ideas such as removing vestigial organs and improving our ability to type, but settled on increasing the efficiency with which energy can be extracted from food.

I then had lunch and went to the National Academy of Sciences, where we set up our projects.   My poster had developed a slight tear from being sent through the mail, but I fixed it with construction paper.

Intel STS: Liveblogging day 2March 12, 2010

Posted by Akhil Mathew in General.
Tags:

I’m going to try liveblogging (insofar as possible) a science fair.  [9:24- It’s now pretty clear that what I’m doing is more like deadblogging.  Still, it’s better than nothing, I suppose.]

(9:45) So I’m at the 2010 Intel Science Talent Search in Washington, D.C.  Presumably many of the folk that come across this blog will have heard of it; it’s a science competition for high school seniors.  There are seven people from RSI here this year.  I’ve also met many interesting people among the other finalists for the first time, all of whom seem to be rather beastly.  Everybody arrived yesterday–I took the train–but nothing competitive actually happened.  Today, we will be judged by a panel of ten or eleven scientists and mathematicians who are going to ask us general questions about science in general, and not our projects.  My first interview is in about half an hour, so I’m basically procrastinating by writing this entry, if there was anything that I could do to prepare :-).

In any case, it was pretty cool to find that I’m in a room that has a TV in the bathroom.  The hotel is ridiculously fancy.

After this, I’m going to go back to random Wikipedia surfing about diverse scientific topics.   They told us this morning that the judges want to see the scientific process rather than technical knowledge–perhaps this is a license for me to babble?  I’ve always enjoyed idle pontification.  In any case, I promise more later after my judging interview. (more…)

Is early specialization good?March 4, 2010

Posted by Akhil Mathew in General.

Thomas Sauvaget asked a question on MO on whether specializing early is a good thing.  It got into an interesting discussion, which continues on his blog.  I have placed some of my own thoughts there, so I won’t ramble here.

In an unrelated note, if you haven’t already seen it, you ought to watch the MAA’s great $\pi, e$ debate.  And that’s regardless what you think of the holiday “Pi Day”–I’m mostly in agreement with what John Armstrong has to say on this subject.  Also, cf. this MO thread for some good alternatives to memorizing digits.

Some unsolved problemsJanuary 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.

Real and Complex Analysis, by C. Apelian and S. Surace, now publishedDecember 19, 2009

Posted by Akhil Mathew in analysis, General, math education.
Tags: , ,

(This material is reposted from here.)

The book Real and Complex Analysis, by Christopher Apelian and Steve Surace, was recently released.

It’s mainly for an introductory upper-level undergraduate course in real and complex analysis, especially at small liberal-arts colleges.  In this post, I’ll describe this book and how I was involved in its production.

At the start of my freshman year, my analysis teacher, Professor Surace, asked me to check over the drafts of a book he and his colleague (and my former teacher) Prof. Apelian were working on. It was the textbook for the course. At the time, if I remember correctly, there were six chapters: on the real and complex spaces, basic topology, limits, continuity, convergence of functions, and derivatives. The complex analysis part of the book was in its infancy (e.g., there was only a rudimentary outline of one chapter, which had been written some time back and was typeset in Word—they wrote it well before before they had switched to LaTeX). (more…)

The Hahn-Banach theorem and two applicationsNovember 28, 2009

Posted by Akhil Mathew in analysis, functional analysis, MaBloWriMo.
Tags: , , , ,

I have been finishing my MaBloWriMo series on differential geometry with a proof of the Myers comparison theorem, which right now has only an outline, but will rely on the second variation formula for the energy integral.  After that, it looks like I’ll be posting somewhat more randomly.   Here I will try something different.

The Hahn-Banach theorem is a basic result in functional analysis, which simply states that one can extend a linear function from a subspace while preserving certain bounds, but whose applications are quite manifold.

Edit (12/5): This material doesn’t look so great on WordPress.  So, here’s the PDF version.  Note that the figure is omitted in the file.

The Hahn-Banach theorem

Theorem 1 (Hahn-Banach) Let ${X}$ be a vector space, ${g: X \rightarrow \mathbb{R}_{\geq 0}}$ a positive homogeneous (i.e. ${g(tx) = tg(x), t >0}$) and sublinear (i.e. ${g(x+y) \leq g(x) + g(y)}$) function.

Suppose ${Y}$ is a subspace and ${\lambda: Y \rightarrow \mathbb{R}}$ is a linear function with ${\lambda(y) \leq g(y)}$ for all ${y \in Y}$.

Then there is an extension of ${\lambda}$ to a functional ${\tilde{\lambda}: X \rightarrow \mathbb{R}}$ with

$\displaystyle \tilde{\lambda}(x) \leq g(x), \ x \in X.$

I’ll omit the proof; I want to discuss why it is so interesting.  One of its applications lies in questions of the form “are elements of this form dense in the space”? The reason is that if ${X}$ is a normed linear space and ${Y}$ a closed subspace, the quotient vector space ${X/Y}$ is a norm with the norm ${|x+Y| := \inf_{y\in Y} |x-y|.}$ (The closedness condition is necessary because otherwise there might be nonzero elements of ${X/Y}$ with zero norm.) (more…)