Algorithm Problem - Two kittens - each one can meow 1,2 or 3 times. 1st kitten always starts 1st and strategy to make 2nd one always successful...

Question

Two kittens are playing a game by "meowing". Every time they take turns to meow and each can meow 1,2 or 3 times. The game starts with an input N, whichever kitten that yells the Nth (N is not divisible by 3) "meow" loses. Suppose kitten P always start, can you think of a strategy for kitten Q to guarantee success? explain the strategy and justify correctness.

Answer 1

To understand algorithms (and strategies for playing various games), first read and re-read the problem statement (or “rules”) until you understand them and can put them into your own words.  Here is how I would re-word this problem to include a winning strategy:

 “Given a number N, kitten Q must meow a series of meows that depends on kitten P’s meows such that kitten Q always makes the (N-1)th meow, then stops.   Note that this will force kitten Q to make the Nth meow,”

 

Since kitten Q has the option of 1, 2, or 3 meows, the critical events occur when the current total of meows after kitten P has finished are:

   a.   N     kitten P has just lost

   b.  (N-1)   kitten P has just forced kitten Q to make the Nth meow and to lose

   c.  (N-2)   kitten P has allowed kitten Q to meow once, forcing kitten P to lose

   d.  (N-3)   kitten P has allowed kitten Q to meow twice, forcing kitten P to lose

   e.  (N-4)   kitten P has allowed kitten Q to meow thrice, forcing kitten P to lose

 

     Note:  Since each kitten can make only 1, 2, or 3 meows, no further situations must be considered.  The algorithm simply waits for one of these events.  Also note: event [a] is the desired outcome and event [b] is the undesired outcome; events [c], [d], and [e] require actions.

 

So:

Q’s turn algorithm:

    If current total is less than (N-4), meow 1, 2, or 3 times randomly.

    If current total is (N-4), meow 3 times.

    If current total is (N-3), meow 2 times.

    If current total is (N-2), meow 1 time.

    End of kitten Q’s turn.

 Comment:  This leaves the count at (N-1), forcing kitten P to make the Nth meow.

 

Now, depending on whether readability and likeness to the actual situation are important, the algorithm may be shortened (but PLZ don’t make the logic confusing by doing this; computer memory is now in gigabytes):

 

Q’s turn algorithm

    If current total is less than (N-4), meow 1, 2, or 3 times randomly,

    Else meow ( (N – current total) - 1 ) times.

   End of kitten Q’s turn.

Comment:  This leaves the count at (N-1), forcing kitten P to make the Nth meow.