Category: Puzzles and Games

We’ll start this installment of Beguiling Games by discussing who has a winning strategy in Splotch!  Recall the rules of the game:  players alternately color in squares in a 4 x 4 grid, with the goal of creating a specified splotch, shown below.  The splotch may be rotated and/or reflected as well.

For a more complete description together with an example of how the game is played, you can look at the previous installment of Beguiling Games.

OK, now for the solution!  It turns out that the second player can always win.  Let’s see how.  I found it easiest to think about a strategy by imagining the grid as being divided into quadrants, like this:

Now here is the important observation:  the first player who fills in a second square in any of the quadrants loses, regardless of whether the squares are adjacent or diagonally situated.  Of course there are other ways to lose, too — as with all these two-player games, there are multiple ways to analyze them.

So let’s get specific.  Suppose the first player colors in square A1 (see the figure below).  The second player then colors in the square labelled B1.

At this point, the red squares indicate all the places the first player cannot play without losing the next turn.  So the first player must color in one of the two empty squares, after which the second player will color in the other one.  So after two turns for each player, the board now looks like this:

So no matter what square the first player colors in next, one of the quadrants will contain two filled-in squares, and so the second player will win on the next move.

A similar strategy may be used no matter where the first player begins.  Consider the first few moves in the following game.  The first player colors in the square A1, and the second player colors in B1.

Again, the first player must avoid the red squares, or else the second player would win on the next turn.  Whichever square the first player colors in next, the second player can always play “two away.”  The result will be 1) the first player will not be able to win on the next turn, and 2) one square in every quadrant will be colored in.  This means that the first player is forced to put a second square in one of the quadrants on the next move, meaning that the second player will win on the turn after that.

This is the simplest strategy I found for the second player.  I would be happy to hear if some reader found an even simpler way to describe a winning strategy!

What about using other splotches?  If the splotch contains too many squares, it is possible to force a draw.  For example, given the splotch below, either player may force a draw simply by coloring in the four corners on their first four moves.

Interestingly, it is difficult to come up with a splotch where the first player has a winning strategy (other than a splotch which is just a single square, of course).  The more squares included in the splotch, the more difficult the analysis.  But for simpler splotches, it seems a clever division of the board allows the second player to win.

For example, consider the following square splotch.

Now divide the board into the following 2 x 1 regions, or dominoes:

Player two has a simple winning strategy.  Whenever the first player fills in a square, the second player fills in the other square of the domino.  It should be clear that the second player can never lose this way.  The first player will eventually have to fill in a square directly above or below a filled-in domino, and when this happens, the second player wins on the next move.

A complete analysis of Splotch! is likely beyond reach.  Just counting the number of possible splotches (up to rotation and reflection) would be a challenging task unless you wrote a computer program to exhaustively find them.  Without rotations and reflections, there are 2¹⁶ = 65,536 possible subsets of 16 squares, and hence 65,535 splotches (since a splotch must include at least one square).  So a computer program would be able to find them all relatively quickly.  The interested reader is welcome to undertake such a task….

Here is another simple two-player game for you to think about, which I call Scruffle.  It is played on a typical 3 x 3 Tic-Tac-Toe grid.  Players alternate playing either a 1, 2, or 3 anywhere in the grid.  A player wins when a number they place creates a column, row, or diagonal which contains a 1, 2, and 3 in any order.

There is one additional constraint:  only three of each number may be placed in the grid.  So once three 1’s (for example) are placed in the grid, no player may place another 1 anywhere in the grid.  This is not an arbitrary constraint — you can show that the game cannot end in a draw with this condition.  See if you can show this!

For the first puzzle, show that the first player has a winning strategy.  This is not difficult; the simplest strategy I found involves the first player’s second turn involving playing the same number they played on the first turn.

A slightly more challenging puzzle is to require the first player to play a different number than the number they played on their first move.  Does the first player still have a winning strategy?  I’ll give you the solution in the next installment of Beguiling Games!

First, we’ll look at the game I left you with in the last installment of Beguiling Games.  These were the rules of yet another variation of Tic-Tac-Toe:  if during the game either play gets three-in-a-row, then X wins.  If at the end, no one has three in a row, then O wins.  Does X have a winning strategy?  Does O?  Why?

We’ll show that X has a winning strategy.  As with usual Tic-Tac-Toe, X starts at the center.  If O goes in any square which is not a corner, then X will win as a result of the winning strategy in Tic-Tac-Toe.  So all that’s left to do is look at the case when O goes in a corner.  Let’s suppose it’s the upper right corner.

Then X goes in the lower right corner.  O must block, or else X will get three-in-a-row and win (since X wins if either player gets three-in-a-row).  So now, the board looks like this:

Take a moment to see if you can figure out X’s winning strategy.  Do you see it?  All X needs to do is place in the center of the bottom row.

Look at the top row.  Someone eventually has to place an X or O in this location.  No matter which one, a three-in-a-row will be created, and X will win!  So in this version of Tic-Tac-Toe, X has a winning strategy.

Today’s game will involve a different dynamic — cards and logic.  But first, let me give a little bit of context.  I have often used the book Problem Solving in Recreational Mathematics by Averbach and Chien when I’ve taught an introduction to proofs course.  There are many interesting problems in this book, and the chapter on logic has several problems involving Truthtellers and Liars.

So you have to solve problems by figuring out who are the Truthtellers and who are the Liars.  I like to use these problems to get students writing arguments in complete sentences since not only are they fun to work out, but they don’t involve notation.  Using notation correctly is another issue entirely, and I prefer to deal with that later on in the course.

As before, there’s a story to go along with the game….

Lucas, Mordecai, Nancy, and Ophelia decided that enough was enough, and so ended their Saturday afternoon’s cramming for the National Spelling Bee.  Wondering what they might do to pass the time, Lucas suggested, “Let’s play Nuh-Uh!”  Everyone enthusiastically agreed.

And so a game of Nuh-Uh! — whose creators, incidentally claim that it is the only game on the market which “Tortures your Mind, Warps your Character, and Impoverishes your Soul — all at the Same Time!” — commenced.

So Lucas shuffled the deck of eight cards; four of the cards had the word Truthteller on them, and four had the word Liar.  Dealing from the left, Lucas first dealt a card to Mordecai, then one to Nancy, one to Ophelia, and then finally one to himself.  Cards are dealt face down so a player can only see his or her card.

Per the rules of Nuh-Uh!, Lucas, then Mordecai, Nancy, and finally Ophelia made the statement “I am a Truthteller.”  Of course, such a statement was consistent with each player’s card, regardless of what was written on it.  Thus ended the first round.

In subsequent rounds, each player passes his or her card to the player on the left, and makes a statement consistent with the new card.  Thus, if Lucas passed Mordecai a card with Liar written on it, Mordecai would have to make a statement which is false.  The statement a player makes is based on the knowledge of the cards he or she has seen, and any other information which may be deduced from the statements of the previous players.

The same player begins each round of making statements.  So Lucas began each round in this game.  Once the game is over, the deal passes to the left, so Mordecai would deal and begin each round with a statement.

After a player makes a statement, players may, beginning with the player on the left of the one who just spoke, “Declare” — that is, say what card each of the players held during the first round.  The declaring player then looks at the cards held by the players to decide if he or she has won.  If an error is made in declaring, the player drops out and play continues; otherwise the cards are turned over and the deal passes to the next player on the left.

So the players passed their cards to the left, and thus the second round of making statements began.  Lucas started off with “Ophelia told the truth in the first round.”  After a polite few seconds of pause to give someone a chance to declare, Mordecai said, “Lucas also told the truth in the first round.”

Another brief pause ensued before Nancy stated, “There is at least one liar at the table.”  Note:  there are four Truthteller and four Liar cards, so it is possible that all players were dealt a Truthteller card.

After Nancy made her statement, one of the players had enough information to declare and win the game.  Which player declared?

Yes, there are enough clues to solve this!  But a word of caution — the solution to the puzzle only involves answering the question, “Which player declared?”  There may not be enough information to give a more complete answer….

Good luck!  In the next installment of Beguiling Games, I’ll give the solution to this logic puzzle, and give a geometrical two-player game to analyze as well.  Happy solving!

It has been some time since I’ve posted any puzzles or games.  In going through some boxes of folders in my office, I came across some fun puzzles I created for a class whose focus was proofs and written solutions to problems.  I’d like to share one this week.

For the assignments, I sometimes wrote stories around the puzzles.  So here is one such story.  The date on the assignment, if you’re interested in such things, is January 16, 2003.  (I assume that you are familiar with the game Tic-Tac-Toe, as well as the fact that if both players play intelligently, the game ends in a draw.)  I called the game “Nic-Nac-No.”

Betty and Clyde, after their favorite breakfast of blueberry pancakes one sunny Saturday morning, began a Tic-Tac-Toe tournament.  They were reasonably bright children — taking turns going first, the initial 73 games ended in a draw.

“Just once, Clyde, couldn’t you try putting your O first on a side instead of in a corner?” prodded Betty.  “That way, it wouldn’t be the same boring game every time.”

“Well, it’s my turn to go first this time,” said Clyde, putting an X in the center.  “OK, now you show me how you want me to play so I can do it that way next time.”

“Oh, shut up, Clyde,” sighed Betty, putting her O in the upper left corner.  And so game #74 ended in a draw.

“Hey, I’ve got an idea!” exclaimed Clyde.  “Let’s make up different rules.  How about this:  the first one who gets three-in-a-row loses.  Whaddya think, Betty?”

“That’s so random, Clyde,” said Betty, secretly excited by the suggestion.

“No, it’s not.  And besides,” reasoned Clyde, “it’s got to be better than playing another game of Tic-Tac-Toe since you won’t ever try anything different.”

“OK, potato brain.  Let’s try.  You go first.”

“Great!” exclaimed Clyde, until he realized Betty was trying to outmaneuver him.  He just realized that it you’re trying to avoid three-in-a-row, the fewer squares you own, the better.

Assuming Betty and Clyde play optimally, will the game be a win for Betty, a win for Clyde, or a draw?

I should remark that the idea of a misere game — where you turn the winning condition into a losing condition — is not original with me.  But most students have not considered this type of game, so misere versions of games often make for engaging problems.

Before I discuss the solution, you might want to try it out for yourself!  There are likely many strategies possible to produce the desired result; I’ll just show you the ones I thought were the most straightforward.

In my solution, Betty and Clyde use different strategies, but the end result is the same:  the game must end in a draw.  Let’s look at what strategies they might use.

It turns out that if Clyde starts in the center, he can use a strategy where he does not lose.  It’s fairly simple:  always play opposite Betty.  Thus, when Betty plays a corner/side, Clyde takes the opposite corner/side.

Why can’t Clyde lose?  First, it should be clear that Clyde can never make a three-in-a-row that passes through the center.  Since he always plays opposite Betty, any line of three passing through the center must contain two X’s and one O (recall Clyde started with an X in the center), and so is not a three-in-a-row.

What about a three-in-a-row along a side?  Since Clyde plays opposite Betty, if he ever placed an X to make three-in-a-row along a side, that would mean Betty already had three O’s in a row on the opposite side, and would have already lost!  So it’s impossible for Clyde to lose this way.

Since any three-in-a-row must pass through the center or be along a side, this means that Clyde — if he plays intelligently — can never lose Nic-Nac-No.

Now let’s look a non-losing strategy for Betty.  There is no guarantee she will be able to take the center square on her first move, so we’ve got to consider something different.  And we can’t just rely on playing opposite Clyde, since there is no opposite move if the takes the center first.  Moreover, it may be the case that Clyde uses some other strategy than the one I mentioned, so we can’t even assume that he does take the center on his first move!

To see a strategy for Betty, consider the following diagram:

Betty’s strategy is simple:  place an O in one of the squares marked A, one marked B, one marked C, and one marked D.

Note that this is always possible.  Even if Clyde does not play in the center on his first move, he can only occupy one square labelled A, B, C, or D.  Then Betty places her O on the other square with the same letter.  If Clyde does begin in the center, then Betty has her choice of first move.

Since it is always possible — and since Betty only has four moves — these comprise all of Betty’s moves.  But note that since Betty never has an O on two of the same letter, she can never get three-in-a-row on a side.  Further, since Betty’s strategy never involves a move in the center, she can never get three-in-a-row in a line going through the center square.  This means that Betty can never lose!

So if the two players play their best games, then Nic-Nac-No ends up in a draw.  And while these strategies do indeed work, I would welcome someone to find simpler strategies.

I’ll leave you with another version of Tic-Tac-Toe to think about.  Here are the rules:  if during the game either play gets three-in-a-row, then X wins.  If at the end, no one has three in a row, then O wins.  Does X have a winning strategy?  Does O?  Note that in this game, there cannot be a draw!  I’ll give you the answer in my next installment of Beguiling Games….