More poison chocolate

Charlie didn't like the outcome last time , so Tracy suggested playing a different version of the coin-moving game. This version is played on a 5 × 5 5 \times 5 grid with a green square in the middle and a coin in the lower right corner. The rules are as follows:

  • Charlie goes first, then Charlie and Tracy take turns moving the coin.
  • The coin can only be moved one space up, left, or diagonally up-and-left.
  • If a player moves the coin to the green square, that player must move it again.
  • The first player to move the coin to the upper left corner wins.

If both play optimally, who will always win?

Charlie Tracy Either player can win

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

9 solutions

Stephen Mellor
Jul 30, 2018

Whatever Charlie's first move, Tracy can place the coin on one of the orange squares.

Then note that landing on the green square is a bad idea, as you then have the next move. Whatever you then do, your opponent can put it either on the blue square, or one of the purple squares, which makes them win (as seen in the first problem since only either successive lefts or successive ups are allowed).

This means that Charlie must place the coin on one of the white squares which can be reached from whichever orange square it is currently at. However, Tracy can then move it to one of the purple squares, forcing a win for Tracy.

@Jeremy Galvagni your latex in the problem is a symbol "x" not "\times".

Stephen Mellor - 2 years, 10 months ago

Log in to reply

Thank you. I noticed that earlier but I guess I forgot to fix it.

Jeremy Galvagni - 2 years, 10 months ago

Hey Stephen, how did you edit the original picture to fill up the colors? Which software?

Syed Hamza Khalid - 2 years, 10 months ago

Log in to reply

I used Snipping Tool and then Microsoft Paint

Stephen Mellor - 2 years, 10 months ago

This is assuming that the player only mives towards the top left corner. If playing again from the green you start going bacwards then the path takes one more step. Either can win.

olivier ghesquiere - 2 years, 10 months ago

Log in to reply

Olivier, this is not allowed as the rules state "The coin can only be moved one space up, left, or diagonally up-and-left." So you cannot move down or right or down and right at any time.

Kenney Hill - 2 years, 10 months ago

A very clear answer, even though you do not need to move the coin to an orange square to guarantee a win. I guess it depends on the interpretation of playing optimally on whether or not the paths I took were optimal play for both parties or not.

EDIT: After looking at some other solutions I found out that I'm not a good player and the paths I chose were not optimal play. You are correct, the only sure way is to move to one of the orange squares on your first move (second move of the game).

Well done! :)

Kenney Hill - 2 years, 10 months ago

Question is Charlie then Charlie again. Believe then either can win???

Geoff Abbott - 2 years, 9 months ago

Log in to reply

This is a good point. @Jeremy Galvagni , perhaps saying "then Tracy and Charlie" in the question, ambiguity can be removed (as I'm sure you didn't mean this)

Stephen Mellor - 2 years, 9 months ago

Log in to reply

This was the problem I modified to make my problem. https://brilliant.org/problems/work-like-every-day/

I may have changed the wording from "they take turns" to "Charlie and Tracey take turns" but I doubt it. I don't remember. If a Brilliant staff member modifies a problem I have no way of knowing. Usually, they make good changes, but sometimes they confuse things.

Either way, I can't modify it now.

Jeremy Galvagni - 2 years, 9 months ago

Yep, indeed.

Zoe Codrington - 2 years, 9 months ago
Jeremy Galvagni
Jul 30, 2018

The green square doesn't help. It was a losing position before, so using it is still a losing move.

If they just keep moving diagonally, how does Tracy win?

Am I missing a scenario here?

Rvy Pandey - 2 years, 10 months ago

Log in to reply

Because they both play optimally. After the first move, Tracy would not go to the green square because that would allow Charlie to win. She would go straight up or left instead.

alex spencer - 2 years, 10 months ago

Log in to reply

Makes sense, thanks!

Rvy Pandey - 2 years, 10 months ago

I was wondering the same thing!

Princess Obuzor - 2 years, 8 months ago
Mark Hennings
Jul 31, 2018

The Sprague-Grundy function for this game can be shown graphically as

with the squares marked 0 0 being losing squares to start on. The SG value of each board position is the mex of the board positions that can be reached from that starting position ("mex" is short for minimum-excluded , so the SG value of a board position is the smallest nonnegative integer that is not on any of the board positions reachable from that position).

Tracy wins again.

Logically Tracy only plays games she can always win, so she is always the choice.

Ed Speers - 2 years, 10 months ago

If they just keep moving diagonally, how does Tracy win?

Am I missing a scenario here?

Rvy Pandey - 2 years, 10 months ago

Log in to reply

Since Charlie starts on a square labelled 0, he cannot move to a square labelled 0, so must move to a square with a nonzero score. This means that it is possible for Tracy to move to another square labelled 0. This means that either Tracy has won, or else Charlie is again faced with playing from a square labelled 0. Eventually, this means that Tracy will land on the winning square, since Charlie cannot.

Mark Hennings - 2 years, 10 months ago

Yes you're missing that they would play OPTIMALLY. Meaning they have full understanding of the game.

Shane Grant - 2 years, 8 months ago

Tracy will control the move after Charlie, so Tracy knowing that always moving diagonally will cause her to lose. She will divert from the diagonal when ever necessary. Another way to look at this, although not as elegant as the Sprague-Grundy proof, is to see how many paths have an odd number of moves and how many have an even number of moves to win and you will notice that Tracy can always force the game so that the path will contain an even number of moves so that she will win. Hope that helps.

Shannon Lieb - 2 years, 10 months ago

Charlie can win actually, it is just not an opitmal course of action

for example, if they only plays diagonally, Charlie wins

So unlike the frist problem, Charlie does have some winning moves, the only problem is that Tracy woudn't let he win on a real match.

BUT the question here is if Charlie CAN win, not if he WILL win...

Sérgio Costa - 2 years, 9 months ago

Log in to reply

The question is whether Charlie can win provided that both players play optimally . Charlie can only win if Tracy makes a mistake, in which case she will not be playing optimally.

Mark Hennings - 2 years, 9 months ago

Log in to reply

But if Charilie is always bond to lose, doesn't it mean that he will never play optimally, therefore nullfling the condition ?

Sérgio Costa - 2 years, 9 months ago

Log in to reply

@Sérgio Costa Even if Charlie plays optimally he loses!

Prem Chebrolu - 2 years, 9 months ago

Log in to reply

@Prem Chebrolu For your clarification.. you can read the first solution by @Stephen Mellor !

Prem Chebrolu - 2 years, 9 months ago
M G
Aug 7, 2018

This is the win/lose map for the optimal play, you can create it from the winning square going backward. Since Charile is forced to play a bad move, Tracy will win if she plays optimally.

This is the same as Fabricio's, except the designations are reversed. I did the same thing. It seems clearer to me. The upper left seems like a good place to be and I intuitively want it to be a W rather than a pink (L). The designation then becomes: where the coin is at the END of my turn.

Working from top left to bottom right, when I found a W there, I immediately thought Charlie would win and almost hit submit on it. Then thought a little more carefully...

Duane Tiemann - 2 years, 10 months ago
Fabricio Kolberg
Aug 7, 2018

Oh, that Tracy, always happy to fool her poor friend Charlie. He needs to be wary of mathematically savvy trolls, it's for his own good.

Either way, the following picture contains the playing board with the following coloring pattern:

  • Pink squares are "losing" squares (if the coin is in that square in the beginning your turn, then you lose).

  • Blue squares are "winning" squares (if the coin is in that square in the beginning of your turn, then you win).

The coloring rule for this diagram is pretty simple:

  • The upper left corner is always pink (if your opponent put the coin there, it's game over for you).

  • Any square from which a pink square is reachable in one move is blue (that is, you can place the coin at a losing position for your opponent).

  • Any square from which only blue squares are reachable is pink (that is, you can only place the coin at a winning position for your opponent).

With this simple rule, it is possible to color the whole board, and conclude that the game starts at a losing position for silly old Charlie . Maybe they should play something else? Looking forward to what these two will come up with next week!

Mohammad Farhat
Aug 10, 2018

Simple. Tracy only plays games which she can win.

There's a problem with your solution: what if Tracy starts feeling sorry for Charlie? Won't she eventually propose a game he can win?

Fabricio Kolberg - 2 years, 10 months ago

Log in to reply

That was just a joke. Don't take it seriously

Mohammad Farhat - 2 years, 10 months ago
Dev Null
Aug 8, 2018

Tracey, clearly. Why else would she propose the game?

Ervyn Manuyag
Aug 7, 2018

25 is an odd number so add 1 and after Charlie is Tracy

Mason Tadena
Aug 6, 2018

Whoever goes in the green loses. Tracy can either easily make the coin go to the bottom left, middle left, top right, or top middle where she would ultimately win.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...