Dollar Nim

The following post was featured at the NYTimes Numberplay blog during the week of August 8‑15, 2011.

One-Pile Nim (a.k.a., Static Nim) is a game in which there is a pile of n objects, and each player can take up to k objects on her turn. The player who removes the last object wins. For example, on the TV show Survivor: Thailand in October 2002, the contestants were given an “immunity challenge” in which there were 21 flags, and a team could remove 1, 2, or 3 flags on a turn. (Using the notation above, n = 21 and k = 3.) Avinash Dixit claims that “the actual players [on Survivor: Thailand] got almost all of their moves wrong,” but the strategy for winning this game is not terribly difficult to figure out. If you’re not familiar with the game, you might enjoy determining the strategy on your own, so I won’t spoil your fun.

While riding back from a camping trip yesterday, my wife was keeping my sons amused by playing mental math games with them. However, she was using mostly drill-and-kill exercises, where she would state an expression like 21 – 6, and one of them would shout, “15!” Before I was able to suggest that she play a game that involved more strategy and less rote mathematics, she offered the following.

• Start with $1, or with 100¢, if you prefer.
• On alternating turns, players can remove any coin they like. (Well, technically, players remove a number of cents equal to the value of one of the four common U.S. coins — quarter, dime, nickel, penny — but such an overly complicated statement of the rules would have confused my sons.)
• The player who reduces the value to 0¢ wins.

That is, n = 100, and a player must choose to remove a value from the set {1, 5, 10, 25}.

I was duly impressed by my wife’s creation. (By “my wife’s creation,” I mean to refer to the game she made up, not to my sons, though the moniker would be equally applicable to the latter, and I must admit that I am often duly impressed by my sons, too.) It was a version of Nim that I had never seen before, and the optimal strategy was not obvious to me. Moreover, it had the characteristics of activities that I love to use with young kids: it causes them to practice some useful basic skill (in this case, calculating change for a dollar) for the purpose of trying to win a strategy game with more sophisticated mathematics.

My two sons, my wife, and I played Dollar Nim several times. During our third game, my wife took a dime to leave me with 29¢. “Daddy’s going to win,” Alex declared. Sure enough, I took a quarter to leave 4¢, and the outcome was decided. Both Alex and Eli had realized that if one of us was able to reduce the amount to 4¢, that person would win — everyone would be forced to take a penny.

Analyzing this game for two players is not terribly difficult, though once I had done it, I was intrigued by the patterns that appear in the optimal strategy. Analyzing the game for four players is a bit more difficult.

In the post on the NYTimes NumberPlay blog, Pradeep Mutalik offered the following extension question:

Since Dollar Nim is played with real money, it makes sense for the participants to keep the change they remove. This confers a reward for removing larger denominations. To offset this, the winner must be given an extra monetary reward. What should be the minimum prize money for the two-player game so that no matter what happens, the winner comes out ahead?

I’ll leave it as an exercise for the reader to determine the optimal strategy for the two- and four-player versions of this game, as well as to determine the answer to Pradeep’s question.

[Update, 6/30/11] The sequence of “unsafe” values for two-player Dollar Nim is now listed as A192333 in the Online Encyclopedia of Integer Sequences.

Advertisements

What’s So Funny? Oh, Nothing

If Charles Seife can write a book about nothing, and Jerry Seinfeld can have a show about nothing, then certainly I can create a blog post about nothing.

The following quote is attributed to Les Dawson:

There is a remote tribe that worships the number zero.
Is nothing sacred?

Here are some other jokes about nothing.

What do you get when you cross a pigeon and a zero?
A flying none!

Why was the number zero fired?
Because he added no value to his company.

Black holes are where God divided by zero.

Finally, here’s a longer joke about nothing that did not receive the approval of PETA.

A scientist is attempting to determine the relationship between the number of legs a frog has and how far it can jump. The scientist sets a frog on the ground and yells, “Jump, frog!” The frog launches itself a good distance. In his notebook, the scientist writes, “Frog with 4 legs: 6 feet.”

The scientist then removes the frog’s front legs and again yells, “Jump, frog!” Though hobbled, the frog still puts forth a reasonable effort. In his notebook, the scientist writes, “Frog with 2 legs: 2 feet.”

The scientist then removes the frog’s back legs and again yells, “Jump, frog!” Not surprisingly, the frog does not move. Again, the scientist yells, “Jump, frog!” And again, the frog does not move. In his notebook, the scientist writes, “Frog with 0 legs: Inconclusive results. The frog has become deaf.”

No animals were harmed in the telling of this joke.

Retail Tales

In tough economic times, lots of folks are counting quarters and pinching pennies. To attract new customers, retailers are offering significant discounts.

• A local bookstore is having a sale: All Math Titles, 1/3 Off. So I picked up a copy of Gödel, Escher.
• Skate Charm Insurance is offering fire-and-theft policies at rock-bottom prices. When asked how they could offer them so cheap, the actuaries responded, “Who would steal a burnt car?”
• Grocery stores in Northern Virginia are promoting lite beer as a good deal, because it has 20% fewer letters than light beer.
• A local gas station recently switched to metric, and I somehow feel better paying $1 per liter instead of $3.78 per gallon.

Nobody likes change, except a kid with a piggy bank.

What coin doubles in value when half is removed?
A half dollar.

Doc: Give me an update on the boy who swallowed four quarters.
Nurse: No change yet.

In the shameless plug department: NCTM members get a 25% discount off the retail price of Math Jokes 4 Mathy Folks at NCTM conferences, and everyone else can save 24% by buying from Amazon.

Interview: Beth Skipper, Beth’s Bookshelf

Although Beth Skipper doesn’t know if there is a particular math joke that kids like best, she does know that the cornier the joke, the better. She recently used an elementary joke as the title of a post on Beth’s Bookshelf, a blog that connects children’s literature and math concepts with teaching strategies.

The post What Ten Things Can You Always Count On? Your Fingers! referenced books containing math jokes, riddles and puns, including Riddle-Iculous Math by Joan Holub and Arithme-Tickle by J. Patrick Lewis.

Beth is the editor of Teaching Children Mathematics, a journal for elementary teachers published by the National Council of Teachers of Mathematics. Though she jokes that she is a crime-fighting superhero when not in the office, the truth is that she dedicates much of her free time to creating content for her blog. “Staying abreast of new titles as they are published is an ongoing challenge,” she noted, and she spends a fair amount of time monitoring announcements of new releases from publishers and scanning books that Amazon recommends. She also pores over fan mail. “I love it when my readers send me an e‑mail about a new book that they’ve come across,” she said.

I recently interviewed Beth to find out more about Beth’s Bookshelf.

Okay, an obligatory first question: What is your favorite math joke?

I like visual jokes. There is a shirt on Mental Floss that cracks me up. The text is “Please Excuse My Dear Aunt Sally,” the classic mnemonic device to help remember the order of operations, and the text is juxtaposed with an image of a woman that appears with her hair in curlers and a cigarette hanging out the corner of her mouth. Doesn’t everyone have a crazy, old “Aunt Sally” hidden somewhere amongst the branches of their family tree?

Why did you start blogging?

When I deliver professional development to teachers, I always include examples of children’s literature that are effective tools for teaching various math concepts. I don’t just give the audience a list of titles; I also try to include related teaching tips. Invariably, I get asked for more titles and tips that connect to mathematical ideas beyond the scope of the presentation. Following a recent event, I decided to search for sources that I could share. While I discovered many sites that post extensive lists of books, the sites did not go the next step and include teaching suggestions or links to related resources. I realized I could meet a need and share what I know about math and literature via a blog.

Who are your favorite children’s book authors?

In no particular order: Jon Scieszka, Dr. Seuss, Maurice Sendak, A. A. Milne, Shel Silverstein, Beatrix Potter, …

There are so many.

Which children’s book is your personal favorite?

My all-time favorites are Alice in Wonderland and Through the Looking Glass by Lewis Carroll.

When you were in the classroom, what is the best tip you received?

Always be prepared, but don’t let those ‘teachable moments’ slip away.

What is your best tip for an elementary teacher who wants to integrate math and literature?

Follow my blog, of course! 

Who are the most interesting people you’ve met while working on your blog?

I have been fortunate to meet authors Greg Tang (The Grapes of Math) and Joseph D’Agnese (Blockhead: The Life of Fibonacci).

If folks are only able to read one item that you’re written, which one would you want them to read? 

[Ed. Note: Shameless plug approaching.] It would have to be the one that included Math Jokes 4 Mathy Folks.

And what about you? When not reading book for kids, which books do you like to read? Any favorite authors?

I’m very eclectic and usually juggle reading several different books at one time. For example, I just finished The Inner Circle by Brad Meltzer, and I am in the middle of The Help by Kathryn Stockett. Yesterday, I began reading Learning and Leading with Habits of Mind by Arthur L. Costa and Bena Kallick.

Father’s Day Reflections (and Other Transformations)

I just got a new stepladder. Don’t get me wrong, it’s a fine stepladder. I just wish I had gotten to know my real ladder.

I had the privilege of knowing my real father.

At age 15, my father faked a birth certificate and joined the Navy. When he was 18, he received a dishonorable discharge — after allowing him to fight in Japan during the last two years of World War II, the Navy finally learned that my dad was under age when he enlisted. So, what did he do? He joined the Army. Before he was 21, he had been to each of the 50 states and had traveled around the world 4 times.

My father had only a sixth-grade education, but he believed in the power of school and learning. It was not easy to get my dad to part with his money. When I was in third grade, my teacher asked me, “If you have two dollars, and you ask your father for another three dollars, how much will you have?”

“I’d have two dollars,” I told her.

“Young man,” she said, “you don’t know your arithmetic.”

“No, Mrs. Wargo,” I said, “you don’t know my father!”

But he often gave me $20 for a good report card, and I was the first kid in my school to have a Commodore 64 with a disk drive. When I graduated high school, my family was subsisting on my father’s disability pension, and I considered working for a year to save money before enrolling in college. “You’re too damned smart,” he said. “Send in the forms. We’ll make it work.”

My father passed away in December 1994. The last words he said to me were, “You’re my pride and joy.” Father’s Day is always a little rough for me, but it’s a good time to reflect. I continually ask myself, “Am I a man that my father would be proud of?”

Are you kidding? I have to believe my father is smiling down from Heaven, saying, “That’s my boy! Yeah, that geeky one there! He’s the author of a math joke book and math joke blog, ya know.”

For all you math dads (and sons, too), here’s some humor for today:

Son: Dad, can you do my homework for me?
Dad: I’m sorry, son, it wouldn’t be right.
Son: That’s okay. Can you try anyway?

I spent today with my twin four-year-old sons, hiking, doing KenKen (more on that later), playing the anagram game, and helping them figure out how the number of “cheers” we do with our glasses at the dinner table is related to the triangular numbers. What a great day. Happy Father’s Day!

The Gender Gap — Even in Online Dating

Women have it rough. The following is a typical — and valid — lament of most women:

I want to add to my income,
subtract from my weight,
divide and conquer,
and try like hell not to multiply.

As if it isn’t bad enough that the average female makes only 75.7% of her male counterpart (source). Now this.

According to OkTrends, the blog that provides dating research based on data from OkCupid.com, a profile about 130 words is fine for a man, but a woman will do better if she creates a profile that is closer to 800 words in length. And a woman should try to sound less intelligent — while there is no difference in the number of responses a man will get if his messages are written at a 4th-grade or 10th-grade level, the number of responses a woman gets will drop precipitously if her messages are written at a college level. What’s more, the analysts actually display the following advice for women:

If someone doesn’t think you’re hot, the next best thing for them to think is that you’re ugly.

The mathematics behind this statement is fascinating. The number of messages a woman receives can be estimated by the following formula:

M = 0.4m₁ – .5m₂ – .1m₄ + .9m₅ + k,

where M is the number of messages received, m_n is the number of men who rated this woman n stars (on a scale of 1–5), and k is a constant.

Now take a look at that formula. The .9 coefficient for m₅ implies that a woman will receive approximately one message for each five-star rating that she receives, but notice that the .4 coefficient for m₁ implies that each one-star rating will also garner some messages. On the other hand, two- and four-star ratings actually decrease the number of messages she receives. (Since m₃ is not included in the formula, three-star ratings apparently have little effect on the number of messages.)

Fascinating, no?

But a little game theory might help to explain this. Suppose you’re really diggin’ a woman’s profile, but most men give her a one-star rating. Well, that’s good news for you — it means less competition. On the other hand, a four-star rating may incorrectly imply that a woman is in high demand, so a typical guy — who thinks she’s cute (4 stars) but not hot (5 stars) — may not be willing to throw caution to the wind for a woman with whom he suspects he has little chance. (Sure, he may have even less chance with a five-star hottie, but it’s worth a try because she’s so hot!)

But, buck up, ladies. Despite all this depressing data, there is a silver lining: messages of just 50 words from a woman are most effective for soliciting a response from a guy, but a guy will have better luck with messages that are closer to 200 words in length. So, women may have to type more to create their profile, but at least they can type less when trying to make a connection.

All this objectication of women reminds me of a middle-aged mathematician I knew. When he walked into the house one afternoon, the following conversation occurred.

“I went to the doctor today, honey,” his wife said.

“Oh. How’d it go?” the mathematician asked.

“Well, he said that I have the spine of a 40-year-old,” she said.

“Oh,” he replied.

“And he said that I have the bones of a 30-year-old,” she continued.

“Hmm,” he replied again.

“And he said that I have the heart of a 20-year-old,” she said.

“Really?” asked the mathematician. He took all of this as unnecessary bragging, so finally he asked, “And did he say anything about your 55-year-old ass?”

“Actually, no,” she said. “Your name never came up.”

Conversation with a Statistician

Yesterday, I ran into a friend who’s a statistician. When I asked, “How’s your husband?” she responded, “Compared to whom?”

We chatted for a while, and she updated me on some recent research. Among the recent discoveries that she shared…

• Birthdays and cigarettes both improve health. Recent research has shown that people who celebrate the most birthdays live longest, and smokers are less likely to die of age-related illnesses.
• A team of researchers has discovered that marriage is the leading cause of divorce. There is a signficant correlation between those who get married and those who get divorced. It is also well known that 50% of marriages end in divorce… which means that if you don’t file for divorce, your wife will.
• It was recently discovered that 83.638867% of statistics have an unjustified level of precision, and 78.46% of all statistics are made up on the spot.

She also relayed this recent incident at the Census Bureau.

Checking some questionnaires, a census clerk was amazed to note that one of them listed 121 in the space for “Age of Mother, if Living” and 125 in the space for “Age of Father, if Living.”

Incredulously, the clerk said to the survey taker, “Both of your parents are alive and over 120 years old?”

“Well, no,” replied the survey taker, “but they would be — if living!”