Nimmerics

Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998), Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992), Database Tuning: A Principled Approach (Prentice Hall, 1992), and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer Verlag, 1997). He can be contacted at [email protected].

I was just figuring out how I could force a draw in our chess game, when the doorbell rang. It rang again almost immediately. Then again.

"Must be the Feds," Ecco said with a sigh. "No patience at all."

Ecco's 10-year-old niece Liane, who had been watching our game with an ironic smirk, said "I'll get it," and ran towards the door.

Federal agent Thomas flashed his ID badge to all three of us, took a seat without being invited, opened his briefcase, pulled out a folder, and began to speak.

"We were keeping Wundermann under observation. Our agents saw him yesterday morning. By the afternoon, he was gone. All he left was this note. The trouble is that we don't know what to make of it."

Wim Wundermann was a professional colleague of Ecco's. He had dropped out of sight a few months earlier, saying that he had discovered patterns he called "Nimmerics." Ecco told him that he should steer clear of applications to encryption.

"Well, what does the note say?" Liane asked.

Agent Thomas showed us the paper, and we all noticed that the writing was strange -- especially at the beginning of the note.

This is useful information for any Nim-Wise player. You know how to Play this Easy game of Nim Though it is not as easy as it seems.

"Oh, yes, I remember," Liane interrupted.

"You start with a bunch of stones and you can take one, two, or three of them in your turn. You win if you remove the last stone."

"Right," said Ecco, "and do you remember the winning strategy?"

Liane answered, "You try to end each turn leaving zero, four, eight, 12, 16,... (any multiple of four) stones to the other player. Then you force the number of stones to exactly four less at the end of your next turn."

"What would happen, Liane," Ecco asked, "if each player could remove one more stone than the last player? So, if the first player can remove up to three in the first move, then the second can remove up to four in the second move, and the first can remove up to five in the third move, then the second can remove up to six in the fourth move, and so on?"

"Hmmm," Liane paused for a moment. "The second player would still win if there were four stones at the beginning, but would also still win if there were five, since he'd be able to take up to four in the second move. I'll have to think about this some more."

"May I continue?" Federal agent Thomas demanded. "We are talking about the disappearance of a major national asset here and..."

"Yes, of course," Ecco apologized (though I thought I detected a trace of mockery in his voice). "Please go on."

Thomas read on, but in a louder, slower voice.

I will give you two puzzles. Suppose I present a bowl containing one $1 bill, two $2 bills, three $5 bills, and four $10 bills. Play consists of moving a single bill at a time from the bowl to the table, which has no bills initially, until the amount on the table reaches or exceeds a given target number. If a player's move makes the amount reach that target, then that player wins. If a player's move makes the amount exceed that target, however, then that player loses.

For example, if the target number is three, then the second player wins, because the first player will either exceed three dollars on his first move or will place a $1 or $2 bill on the table, in which case the second player will make the amount equal three dollars on her next move.

"Yes, but the first player usually has an advantage," Liane observed.

Thomas glared at her, but Ecco looked at her curiously.

"Oh, it just feels that way," she said with a shrug.

"It's true for Nim," she added.

Ecco nodded, but then turned his eyes to agent Thomas.

Thomas read on with even more deliberation.

Let X be the first target number 29 or greater in which the second player can force a win. Let Y be the first target number 41 or greater in which the first player can force a win. Find me at that location.

Can you find Wundermann's address at X and Y? Does either X or Y change if there are twice as many $1s, $2s, $5s, and $10s? If so, to what?

Ecco nodded his head thoughtfully, then said "Okay, so let's play Wundermann's game, Miss Feels-That-Way."

While Thomas paced the room, Ecco worked out the problem by playing the game with Liane. After he gained enough intuition, he gave Thomas the answer. "These two numbers are the X and Y you are to look for, perhaps they are street and avenue addresses. Liane has a theory about the letters."

"NWPENT," she said. "Look at the beginning of the note. Those are the weird uppercase letters. The others are there by grammar."

Federal agent Thomas stared at her as if puzzled for a moment, then his face cleared. He collected his papers, stood up, and left without a word.

A few days later, Thomas was back. "We found the place. A penthouse apartment in the Northwest district near the street corner you identified," Thomas said, nodding to Liane and Ecco. "Now, Wundermann has left a new puzzle. The guy's insane."

Consider a variation of Nim which I'll call Expanding Nim. In that variation...

Thomas paused, then said, "This new game is exactly the one Ecco asked Liane about the other day. It is the standard Nim except that, for the first move, the first player can take one, two, or three stones; in the second move, the second player can take one, two, three, or four stones; in the third move, the first player can take one, two three, four, or five stones; in the fourth move, the second player can take one, two, three, four, five, or six stones, and so on. The possibilities expand at each move, making this a pretty difficult game to play."

"Well, Liane, can you do it?" Federal agent Thomas asked.

"Sure," she answered cheerfully. "Here they are..."

Can you find Liane's solution as well as the solution to the question posed earlier in italics? If so, let me know at DrEcco@ ddj.com.

Last Month's Solutions

Ecco believes in symmetry, so his solutions were to have the spacecraft land at the following coordinates:

I don't think these are the best possible solutions, however. See if you can do better. The generalization to any number of points is an open problem so far.

DDJ