wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> SOS
        
(Message started by: ThudanBlunder on Jun 14^th, 2008, 1:04pm)

Title: SOS
Post by ThudanBlunder on Jun 14^th, 2008, 1:04pm

Jack and Jill play a game with a piece of paper on which is a row of n empty boxes. They take turns writing either an 'S' or an 'O' in an empty box. The winner is the one who completes an 'SOS' in consecutive boxes. For which values of n does the 2nd player (Jill) have a winning strategy?

Title: Re: SOS
Post by Frumious Bandersnatch on Jun 16^th, 2008, 11:16am

A few thoughts:

The only way to win (assuming your opponent is paying attention and trying not to lose) is [hide]by giving your opponent a board like ... S __ __ S ..., where the two blanks are the only empty boxes left.
[/hide]

Therefore, any winning strategy for the second player probably requires [hide]an even number of boxes.[/hide]

That may be necessary but it's clearly not sufficient, because in the case where n=[hide]4[/hide], Jack can just play [hide]O __ __ __[/hide] and force a draw. And if n=[hide]6[/hide], he can force a draw with [hide] __ __ __ O __ __ [/hide].

Let's see. Jill needs to start a turn with [hide]seven empty boxes in a row. That way she can play an S into a box with three empty boxes on either side, meaning that on her next turn she can always create the S __ __ S pattern. Then it's just a matter of waiting -- and not letting Jack make an SOS anywhere else.[/hide]

So maybe the answer is [hide]any even number >= 14[/hide].

Title: Re: SOS
Post by ThudanBlunder on Jun 16^th, 2008, 1:12pm

Yes Brumious Fandersnatch, that is the right idea. [hide]The S _ _ S configuration is key[/hide].

Jack wins when [hide]n is odd and at least 7[/hide]
Jill wins when [hide]n is even and at least 16[/hide]
Otherwise, [hide]including when n = 14, it is a draw[/hide].

Title: Re: SOS
Post by Hippo on Jun 17^th, 2008, 8:36am

Before reading the comments:
[hide]How the loss in 1 look like ... If there are free places only with one free neighbour and one S neighbour you cannot play O otherwise you play O on such a place. But in the mentioned situation there must be free spaces in pairs surrounded by S, therefore you cannot play S either. So the only loosing situation is with even number of free places ... therefore the parity of initial number of places determines looser / winner roles in correct play. The situation is not such easy as the "looser" may force a draw in some situations.... his goal is to prevent creation of S..S pattern.
If the "winner" starts, he can place S on 4th position to attack S..S pattern on positions 1,4 and 4,7. So for n>7, odd the first player wins.
What for the second player ... first player cannot play S in distance greater than 3 from any side (cannot play at all for n>5). So he plays O trying to prohibit S..S patterns as much as possible. Playing to the "middle" works best, preventing S..S pattern upto even n<15. For n>15 even, there remains 8 positions with no letter, place S to the 4th from the side which is not incident with O. If the S..S on this side is prevented, place S on the 7th, (which is not incident with O)...
[/hide]

As was posted by ThudanBlunder :) [hide]the case n=14 defense ......O.......-> ......O...S... -> ......O...S..O -> ......OS..S..O -> .....SOS..S..O the pattern S..S is forced, but the game is lost in one.[/hide]