Dennis is a professor of computer science at New York University. His latest books include Dr. Ecco's Cyberpuzzles: 36 Puzzles for Hackers and Other Mathematical Detectives (W.W. Norton, 2002) and Database Tuning: Principles, Experiments, and Troubleshooting Techniques (Morgan Kaufman, 2002). He can be contacted at DrEccoddj.com.
Baskerhound was on his way. Ecco's 10-year-old nephew Tyler skipped basketball practice to be sure to be there. Liane also found an armchair nearby to strum her guitar. What was it about this kidnapper that attracted people?
To Ecco, at least, it was the problems Baskerhound posed. As usual, they were shrouded in mystery.
"I can't tell you the real source for this game," Baskerhound began as he sat down in the most comfortable chair, an unlit Cuban cigar in his mouth. "But it may feel familiar if you've been reading between the lines in the news.
"The principle of escalation dominance is that whatever mischief the bad guys can do to the good ones, the good guys can do more to the bad guys. (This may obscure relative goodness, but we'll leave that to one side for the moment.)
"In our rendition, escalation dominance is played on a square checkerboard (though the square board may vary in size) having alternating red and black squares. So red squares are connected to one another by diagonals and similarly for black ones.
"The bad guys are the Red team. Their pieces (also colored red) have values 1 through n. The good guys are the Black team and they have black pieces with values k+1 to k+n. Assume that we choose n so that 2n is a square (for example, n=2,8,18,...). Red moves first and places a piece on an empty red square, then Black places a piece on an empty black square, and so on. Your goal is to choose k to be as small as possible while guaranteeing that Black wins. Winning can mean two things.
"In the Any Neighbor version of the game, Black wins if every red piece is next to (on a horizontally or vertically neighboring square) some black piece having a higher number. For a warm-up, consider a 2×2 square. n is 2, so Red has pieces with the values 1 and 2. What does k have to be? (Solution to warm-up: k=1 suffices, since that would give Black a 3, which would be next to both Reds; see Figure 1.) Now, here are my questions.
"1. Is there a k value that works for any arbitrary size under the Any Neighbor version? If so, what is the smallest such k? If not, how does k relate to n, assuming we want the smallest possible k? (Of course, k=n will always work. We want the smallest possible k.)
"Now, suppose that we change the rules a bit so that every red piece must have higher valued black pieces on at least half of its sides (so one for the corners and two for other squares). We call this the "Half Neighbors" version.
"2. Is there a k value that works for any arbitrary size under the Half Neighbors version, assuming that Red must place all his pieces down before Black places any pieces down? If so, what is the smallest such k? If not, how does k relate to n, assuming we want the smallest possible k?
"3. How does your answer to #2 change if Red and Black alternate moves with Red taking the first move?"
Ecco does not know how much better Red can do, but would recommend a strategy where Red starts off with small values.
When discussing your solutions to this puzzle in a few months, I will point to the best web sites proposed by readers that give the smallest k for the n=18 game and one that actually plays the game (the version of the game where players alternate moves) for Black while permitting a human player to play for Red using a browser. The game has to announce a k and then either meet that k or beat it if the Red player plays foolishly.
DDJ
