Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Binary tic-tac-toe


  • Please log in to reply
8 replies to this topic

#1 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5891 posts
  • Gender:Male
  • Location:New York

Posted 20 February 2014 - 11:07 AM

In the all-digital future, X and O are banished from the game of tic-tac-toe.

They are replaced by 1 and 0, the the result of such a game might look like this:

 

1 | 0 | 1

- + - + -

0 | 1 | 1

- + - + -

0 | 1 | 0

 

Under the usual rules that require getting 3-in-a-row, it would be a draw.

But this is the digital age, and there are different rules for winning.

 

If we sum the eight rows of three numbers we get 2, 2, 1 (horizontally) 1, 2, 2 (vertically) and 2, 2 (diagonally).

Six of the sums are even, and two are odd.

The final parity of the board is thus even, and the game is said to have an even outcome.

If there were more odd sums than even, the game would have an odd outcome.

If there were four even (and therefore four odd) sums, the game would have a neutral outcome.

 

The game is played as follows:

 

The winner of a fair-coin toss (call him player A) chooses whether to play first or second.

The other player (call her player B) decides whether she wants an odd, even, or neutral game outcome.

 

On each turn, a player places his choice of either a 1 or a 0 on any unoccupied place on the grid.

As in normal tic-tac-toe, players alternate turns; but here on each turn a player may play either a 0 or a 1.

When the places are filled, the board is examined to determine whether it is odd, even or neutral.

 

If the final board parity matches player B's choice, player B wins; otherwise player A wins.

 

The questions to answer are:

  1. Is there an advantage to winning the coin toss?
  2. Is there a winning strategy for either player?

  • -1
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#2 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 20 February 2014 - 11:52 AM

Spoiler for

Edited by Rainman, 20 February 2014 - 11:55 AM.

  • 0

#3 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1448 posts
  • Gender:Male

Posted 28 February 2014 - 07:55 AM

I may be missing something, but by playing on the opposite side of the center square as player B, player A seems to be able to control the outcomes of four rows (both of the diagonals and the horizontal and vertical rows through the center), not six. The topmost and bottommost horizontal rows, and the leftmost and rightmost vertical rows, are not so easily determined. Player A can control four row outcomes, which is enough to prevent B from being able to win if B goes for either an even or an odd outcome, but it's not clear if A can prevent B from achieving a neutral game outcome using that strategy.

Spoiler for

  • 0

#4 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 28 February 2014 - 08:46 AM

Yep, I got it wrong.


  • 0

#5 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5891 posts
  • Gender:Male
  • Location:New York

Posted 28 February 2014 - 09:39 AM

I may be missing something, but by playing on the opposite side of the center square as player B, player A seems to be able to control the outcomes of four rows (both of the diagonals and the horizontal and vertical rows through the center), not six. The topmost and bottommost horizontal rows, and the leftmost and rightmost vertical rows, are not so easily determined. Player A can control four row outcomes, which is enough to prevent B from being able to win if B goes for either an even or an odd outcome, but it's not clear if A can prevent B from achieving a neutral game outcome using that strategy.

Spoiler for

 

Spoiler for On further review


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#6 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1448 posts
  • Gender:Male

Posted 28 February 2014 - 02:48 PM

Spoiler for The counterexample using the original strategy would be

  • 0

#7 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5891 posts
  • Gender:Male
  • Location:New York

Posted 28 February 2014 - 11:29 PM

Spoiler for The counterexample using the original strategy would be

 

 

Spoiler for OK but why would A play that way?


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#8 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1448 posts
  • Gender:Male

Posted 02 March 2014 - 05:06 PM

Spoiler for

  • 0

#9 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5891 posts
  • Gender:Male
  • Location:New York

Posted 03 March 2014 - 01:28 AM

OK, got it. I did mis-read the solution.

 

I ran across this puzzle some time ago, and wondered whether it could break the deterministic nature of 3x3 tic tac toe by giving freedom of choosing which marker to place, and found that it doesn't. Maybe ANY 3x3 game allows Player 1 to either win or at least avoid a loss.


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users