Sunday, January 06, 2008

Maths - Not Always About Thousands of Formulae (3)

Note: Continued from an earlier post.

We decided that five was a pretty good starting number, and then we were starting to consider our opponent's best move.

1. What happens when you [the opponent] choose 1, 3, 7 or 9? Are they good / strong moves? Can I force a win after you chose one of those numbers?

Let me list all the 15-triplets again for reference in this post:

  • 1,5,9
  • 1,6,8
  • 2,4,9
  • 2,5,8
  • 2,6,7
  • 3,4,8
  • 3,5,7
  • 4,5,6
If you choose 1, 3, 7 or 9, you only have 2 "good" triplets. For example, if you choose 1, your best triplets would be 1,5,9 and 1,6,8. However, 1,5,9 is no longer possible since I took 5 earlier. As for 1,6,8, I could very easily sabotage you by choosing either 6 or 8 in my next move.

However, if I choose 6 or 8, in your next move you can also sabotage me easily by choosing 4 or 2.

All this get very confusing, and we have yet to find any clear winning strategy here. Everything is in a mess, and inevitably we start falling back to our "maths is convoluted" assumption again.

Okay, since the choice of 1, 3, 7 or 9 doesn't lead us anywhere, let's see what happens with 2, 3, 6 or 8.

2. What happens when you choose 2, 4, 6 or 8? Are they good / strong moves? Can I force a win after you chose one of those numbers?

If you choose any of these, you have three "good" triplets. For example, if you choose 2, your "good" triplets would be 2,4,9; 2,5,8 and 2,6,7. Again, 2,5,8 is no longer possible because I had taken 5. That leaves 2,4,9 and 2,6,7 as your "good" triplets.

With this, can I still force a win?

If I choose 1, you are forced to choose 9 in your next move (or else I will win). Then I am forced to choose 4. You have 3, 6, 7, 8 as your remaining "okay" moves. Then think of what will happen for each of these options.

I will spare you the details, but if you repeat the same analysis for all future steps (game-tree analysis), you would realize that all moves will end up with a draw, i. e. no one can get a 15-triplet.

3. In the end, can my initial choice of 5 force a win?

From our analysis, unfortunately, NO.

4. If the initial choice of 5 can't force a win, does that automatically mean that other initial choice can't force a win too?

All our analysis are based on the assumption that 5 is the best first number. However, we had no absolute proof that it MUST be the best first number. So with any other first numbers, it's still likely that some force-win strategies might be hidden in there somewhere.

But up to this stage, it's getting boring and repetitive. There must be some easier and better ways of solving this problem. But how lerr?

Will leave it for next time. If you are interested, please refer to Woon Pang's answer in my previous posts for ideas. :)


crushedguava said...

As much as I love puzzles such as these, where the solution isn't set to go out of the way to trick you, but rather just requires a systematic and persistent application of logic, I find it hard to follow your explanation as I have no vested interest in the puzzle.

Perhaps, if I were to encounter a situation in an RPG game that I happen to be playing, and a monster comes out, and says I have play this game with it to get past to the next are, I would be very much more interested in the puzzle and its solution.

Interestingly enough, this exact situation DID appear in the RPG game that I am playing at the moment, where an imp appeared and presented me with a puzzle, which I had to solve to get a key, and which I'm sure is much simpler than the puzzle you set out. The game was this:

There are 11 stones, and each of us take turns picking up either 1, 2, or 3 stones. The person who picks the LAST stone LOSES. You have a choice of starting first, or you can let the imp start first.

Sounds simple enough. Is there a winning strategy for This game, and what is it?

youngyew said...

Haha yeah I fully understand what you mean in your first paragraph. In fact now that I look at my own writing, I think that I wouldn't be too interested to read it if I haven't tried the question myself.

About the vested interest, for me my interest is always to find out the solution in the end, as the satisfaction is always overwhelming.

For your stone question, you start with 2 stones (leaving 9); then no matter what your opponent chooses, leave 5 after your turn; and after that you are guaranteed a win. This is a forced-win by the first player.

crushedguava said...

That is, indeed, an unfair game, for the 2nd player. What if, hypothetically, we change the number of stones to 13? How would the mechanics of the game change then?

youngyew said...

Basically in this game, the perfect strategy is to leave 5, 9, 13, 17, 21 etc stones after your turn, regardless of the initial number of stones. The first player who's able to leave those number of stones to his opponent after his turn, and then stick to this plan for the whole game, is guaranteed a win. Unfair indeed to the second player. :)

So if the game started with 13 stones, it's best to let your opponent start first and then you leave 9 stones for him after your turn. If you decide to start first, you won't be able to leave 9 stones for your opponent (since you can either take 1, 2 or 3 stones); and if your opponent knows the strategy, he will leave you 9 stones and then control the game from there onwards.

There is a similar but much more difficult game called Nim. You can try it here: Link (pardon the irritating voice in the game)

bluez_aspic said...

re: crushed guava


crushedguava said...

What is Tales of Phantasia?